TechCodeview

Šiame straipsnyje aptarsime besitęsiantį medį ir minimalų besitęsiantį medį. Tačiau prieš pereidami tiesiai link besitęsiančio medžio, pirmiausia pažiūrėkime trumpą grafiko ir jo tipų aprašymą.

Grafikas

Grafą galima apibrėžti kaip viršūnių ir briaunų grupę, jungiančią šias viršūnes. Grafikų tipai pateikiami taip:

Nenukreiptas grafikas:Nenukreiptas grafikas – tai grafikas, kurio visos briaunos nerodo į kokią nors konkrečią kryptį, t.y., jos nėra vienakryptės; jie yra dvikrypčiai. Jis taip pat gali būti apibrėžtas kaip grafas su V viršūnių rinkiniu ir E briaunų rinkiniu, kiekviena briauna jungianti dvi skirtingas viršūnes.Susietas grafikas:Sujungtas grafikas yra grafikas, kuriame kelias visada egzistuoja nuo viršūnės iki bet kurios kitos viršūnės. Grafas yra sujungtas, jei galime pasiekti bet kurią viršūnę iš bet kurios kitos viršūnės sekdami briaunas bet kuria kryptimi.Nukreiptas grafikas:Nukreipti grafikai taip pat žinomi kaip digrafai. Grafas yra nukreiptas grafikas (arba digrafas), jei visos briaunos, esančios tarp bet kurių grafo viršūnių ar mazgų, yra nukreiptos arba turi apibrėžtą kryptį.

Dabar pereikime prie temos, apimančios medį.

Kas yra besitęsiantis medis?

Apimamasis medis gali būti apibrėžtas kaip neorientuoto sujungto grafo pografas. Ji apima visas viršūnes ir mažiausią įmanomą briaunų skaičių. Jei kuri nors viršūnė praleista, tai nėra besitęsiantis medis. Apimamasis medis yra grafiko poaibis, neturintis ciklų ir jo taip pat negalima atjungti.

Apimamasis medis susideda iš (n-1) briaunų, kur 'n' yra viršūnių (arba mazgų) skaičius. Tvirtinimo medžio kraštams gali būti priskirti svoriai arba ne. Visi galimi apimantys medžiai, sukurti iš duoto grafo G, turėtų vienodą viršūnių skaičių, tačiau aprėpiamojo medžio briaunų skaičius būtų lygus viršūnių skaičiui duotame grafe atėmus 1.

Pilnas neorientuotas grafikas gali turėti n^n-2 besitęsiančių medžių skaičius kur n yra grafiko viršūnių skaičius. Tarkime, jei n = 5 , būtų didžiausias galimų besitęsiančių medžių skaičius 5^5-2= 125.

Tvirtinimo medžio taikymas

Iš esmės aprėptinis medis naudojamas norint rasti minimalų kelią, kuriuo būtų galima sujungti visus grafiko mazgus. Kai kurios įprastos besitęsiančio medžio taikymo sritys yra išvardytos taip:

• Klasterio analizė
• Civilinių tinklų planavimas
• Kompiuterių tinklo maršruto parinkimo protokolas

Dabar pateikdami pavyzdį supraskime besitęsiantį medį.

Plintančio medžio pavyzdys

Tarkime, kad grafikas yra -

Kaip aptarta aukščiau, apimančiame medyje yra toks pat viršūnių skaičius kaip ir grafe, viršūnių skaičius aukščiau pateiktame grafike yra 5; todėl apimančiame medyje bus 5 viršūnės. Apimamojo medžio briaunos bus lygios grafo viršūnių skaičiui atėmus 1. Taigi, aprėpiančiame medyje bus 4 briaunos.

Kai kurie galimi apimantys medžiai, kurie bus sukurti pagal aukščiau pateiktą diagramą, yra pateikti taip:

Tvirtinimo medžio savybės

Kai kurios besitęsiančio medžio savybės pateikiamos taip:

• Gali būti daugiau nei vienas sujungto grafo G apimantis medis.
• Apimamas medis neturi jokių ciklų ar kilpos.
• Plintantis medis yra minimaliai prijungtas, taigi, pašalinus vieną briauną iš medžio, grafikas bus atjungtas.
• Plintantis medis yra maksimaliai aciklinis, taigi pridėjus vieną kraštą prie medžio atsiras kilpa.
• Gali būti maksimumas n^n-2 apimančių medžių, kuriuos galima sukurti iš viso grafiko, skaičius.
• Turi besitęsiantį medį n-1 briaunos, kur „n“ yra mazgų skaičius.
• Jei grafikas yra pilnas grafikas, tai apimantį medį galima sudaryti pašalinus maksimalias (e-n+1) briaunas, kur „e“ yra briaunų skaičius, o „n“ yra viršūnių skaičius.

Taigi, apimantis medis yra sujungto grafo G poaibis, o atjungto grafo apimamojo medžio nėra.

Mažiausias besitęsiantis medis

Mažiausias apimantis medis gali būti apibrėžtas kaip apimantis medis, kuriame briaunos svorių suma yra minimali. Tvirtinimo medžio svoris yra svorių, pateiktų besitęsiančio medžio kraštams, suma. Realiame pasaulyje šis svoris gali būti laikomas atstumu, eismo apkrova, spūstimi arba bet kokia atsitiktine verte.

Mažiausio besitęsiančio medžio pavyzdys

Supraskime minimalų besitęsiantį medį naudodami pavyzdį.

Aukščiau pateikto grafiko kraštinių suma yra 16. Dabar kai kurie galimi apimantys medžiai, sukurti iš aukščiau pateikto grafiko, yra -

Taigi, mažiausias apimantis medis, pasirinktas iš aukščiau pateiktų apimančių medžių duotam svertiniam grafikui, yra -

Mažiausiai besitęsiančio medžio taikymas

Mažiausio besitęsiančio medžio taikymai pateikiami taip:

• Minimalus tarpatraminis medis gali būti naudojamas projektuojant vandens tiekimo tinklus, telekomunikacijų tinklus ir elektros tinklus.
• Jis gali būti naudojamas ieškant kelių žemėlapyje.

Algoritmai, skirti minimaliam apimančiam medžiui

Minimalų apimantį medį galima rasti iš svertinio grafiko, naudojant toliau pateiktus algoritmus -

• Primo algoritmas
• Kruskal algoritmas

Pažiūrėkime trumpą abiejų aukščiau išvardytų algoritmų aprašymą.

Primo algoritmas - Tai gobšus algoritmas, kuris prasideda nuo tuščio besitęsiančio medžio. Jis naudojamas norint rasti mažiausią apimantį medį iš grafiko. Šis algoritmas suranda briaunų poaibį, apimantį kiekvieną grafo viršūnę, kad būtų galima sumažinti briaunų svorių sumą.

paleisti scenarijus Linux sistemoje

Norėdami sužinoti daugiau apie prim algoritmą, galite spustelėti toliau esančią nuorodą - https://www.javatpoint.com/prim-algorithm

Kruskal algoritmas - Šis algoritmas taip pat naudojamas susieto svertinio grafiko minimaliam apimančiam medžiui rasti. Kruskal algoritmas taip pat vadovaujasi gobštu požiūriu, kuris kiekviename etape randa optimalų sprendimą, o ne sutelkia dėmesį į visuotinį optimalumą.

Norėdami sužinoti daugiau apie prim algoritmą, galite spustelėti toliau esančią nuorodą - https://www.javatpoint.com/kruskal-algorithm

Taigi, viskas apie straipsnį. Tikimės, kad straipsnis bus jums naudingas ir informatyvus. Čia mes aptarėme apimantį medį ir minimalų apimantį medį kartu su jų savybėmis, pavyzdžiais ir pritaikymais.