Back

ⓘ Razapinjuće stablo




Razapinjuće stablo
                                     

ⓘ Razapinjuće stablo

U matematičkom polju teorije grafova razapinjuće stablo T povezanog, neusmerenog grafa je drvo koje se sastoji od svih vrhova i nekih grana od G. Neformalno, razapinjuće stablo od G predstavlja odabir grana od G koje formiraju drvo koje obuhvata svaki vrh. To znači, svaki vrh postoji u drvetu, ali bez ciklova. S druge strane, svaki most od G mora pripadati T.

Razapinjuće stablo povezanog grafa G se takode može definisati kao maksimalan set grana od G koje ne sadrže ciklove, ili kao minimalan set grana koje sadrže sve vrhove.

U odredenim poljima teorije grafova često je korisno pronaći minimalno razapinjuće stablo opterećenog grafa. Drugi problemi optimizacije razapinjućeg drveća su takode proučavani, uključujući i maksimalno razapinjuće drvo, minimalno drvo koje obuhvata najmanje k vrhova, minimalno razapinjuće drvo sa najviše k grana po vrhu stepenom ograničeno razapinjuće drvo, razapinjuće drvo sa najvećim brojem listova usko povezano sa najmanjim dominirajućim skupom, razapinjuće drvo sa najmanje listova usko povezano sa Problemom Hamiltovog puta, razapinjuće drvo minimalnog prečnika, i razapinjuće drvo minimalne dilatacije.

                                     

1. Osnovni ciklusi

Dodajući samo jednu granu u razapinjuće stablo će stvoriti cikl; takav cikl se naziva osnovni cikl. Postoji poseban fundamentalni cikl za svaku ivicu; tako, postoji 1-1 korespondencija izmedu osnovnih ciklova i grana koje nisu u razapinjućem stablu. Za povezan graf sa V vrhova, bilo koje razapinjuće drvo će imati V -1 grana, i tako, graf od E grana će imati E - V +1 osnovnih ciklova. Za bilo koje dato razapinjuće stablo ovi ciklovi će formirati bazu za prostor ciklova.

Sličan pojmu osnovnog cikla je pojam osnovni podskup. Brisanjem samo jedne grane razapinjućeg stabla, vrhovi će biti particionisani u dva disjunktna podskupa. Osnovni podskup je definisan kao skup grana koje moraju biti uklonjene iz grafa G da bi se ostvarila ista particija. Tako, postoji tačno V -1 osnovnih podskupova grafa, po jedan za svaku granu razapinjućeg stabla.

Dualnost izmedu osnovnih podskupova i osnovnih ciklova je uvedena uz napomenu da se grane cikla koje nisu u razapinjućem stablu mogu pojaviti samo u podskupovima na drugim granama cikla; i obrnuto: grane podskupa se mogu pojaviti samo u onim ciklovima koji sadrže odgovarajuću granu podskupa.

                                     

2. Razapinjuće šume

Razapinjuća šuma je tip podgrafa koji generalizuje koncept razapinjućeg drveta. Kako god, postoje dve definicije u zajedničkoj upotrebi. Jedna je da je razapinjuća šuma podgraf koji sadrži razapinjuće drvo u svakoj povezanoj komponenti grafa. Ekvivalentno, to je maksimalan slobodan cikl podgrafa. Ova definicija je zajednička u kompjuterskoj nauci i optimizaciji. To je takode definicija koja se koristi kada se diskutuju minimalne razapinjuće šume, generalizacija koja se odnosi na nepovezane grafove koji obuhvataju minimum razapinjućeg drveća. Druga definicija, zajednička u teoriji grafova, je da je razapinjuća šuma bilo koji podgraf koji je oboje - šuma ne sadrži ciklove i razapinjući sadrži svaki čvor.

                                     

3. Brojanje razapinjućih stabala

Broj tG razapinjućih stabala povezanog grafa je dobro proučena invarijanta. U nekim slučajevima, lako je izračunati tG direktno. Na primer, ako je G drvo samo po sebi, tG =1, a ako je G cikličan graf C n {\displaystyle C_{n}} sa n vrhova, onda je tG = n. Za bilo koji graf G, broj tG se može izračunati koristeći Kirkhovu matrica-drvo teoremu.

Kajlejeva formula je formula za broj razapinjućih stabala u kompletnom grafu K n {\displaystyle K_{n}} sa n vrhova. Formula kaže da t K n = n − 2 {\displaystyle tK_{n}=n^{n-2}}. Drugi način iskazivanja Kajlejeve formule je da postoji tačno n − 2 {\displaystyle n^{n-2}} obeleženih stabala sa n vrhova. Kajlejeva formula može biti dokazana koristeći Kirkhovu matrica-drvo teoremu ili preko Pruferovog koda.

Ako je G potpun dvostrani graf K p, q {\displaystyle K_{p,q}} tada je t G = p q − 1 q p − 1 {\displaystyle tG=p^{q-1}q^{p-1}}, dok je G n -dimenzioni hiperkockasti graf Q n {\displaystyle Q_{n}}, tada je t G = 2 n − n − 1 ∏ k = 2 n k n k {\displaystyle tG=2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}}. Ove formule su takode posledice matrica-drvo teoreme.

Ako je G multigraf i je ivica od G, onda broj tG razapinjućih stabala zadovoljava brisanje-kontrakcija rekurenciju tG=tG-e+tG/e, gde je G-e multigraf dobijen brisanjem e i G/je kontrakcija od G po e, gde mnoštvo grana koje se javljaju iz ove kontrakcije nisu izbrisane.



                                     

4. Homogena razapinjuća stabla

Razapinjuće stablo izabrano nasumično od svih razapinjucih stabala sa jednakom verovatnoćom se naziva homogeno razapinjuće drvo UST/HRS. Ovaj model je obimno istraživan u verovatnoći i matematičkoj fizici.

                                     

5. Algoritmi

Klasični algoritam razapinjućeg stabla, pretraga u dubinu DFS - depth-first search, je nastao zahvaljujući Robertu Tardžanu. Drugi, važan algoritam je baziran na pretrazi u širinu BFS - breadth-first search.

Paralelni algoritmi tipično zauzimaju drugačiji pristup od DFS i BFS. Halperin i Zwick su dizajnirali optimalno nasumični paralelan algoritam koji radi u logaritamskom vremenu, Olog n, sa velikom verovatnoćom za EREW PRAM. Shiloach-Vishkin algoritam, nastao zahvaljujući Yossi Shiloach i Uzi Vishkin je osnovni za mnoge paralelne implementacije. Za Bader i Kongov algoritam je pokazano da radi najbrže u praksi na raznovrsnim grafovima.

Najčešće distribuiran algoritam je Razapinjuće Drvo Protokol, korišćen od strane "OSI link layer"-Sloj veze uredaja kako bi stvorili razapinjuće drvo koje koristi već postojeće veze kao izvorne grafove u želji da izbegnu oluje pri emitovanju.

                                     
  • Euklidovo minimalno razapinjuće stablo Euclidean minimum spanning tree - EMST je minimalno razapinjuće stablo skupa od n tačaka u ravni ili uopštenije
  • Минимално разапињуће стабло је разапињуће стабло неког повезаног, тежинског и неусмереног графа које садржи све чворове тог графа, а збир тежина његових
  • Протокол разапињућег стабла СТП је мрежни протокол који обезбеђује луп - фри топологију за било коју повезану локалну мрежу. Основна функција СТП је да
  • algoritam rešava ovaj problem imolicitnim stvaranjem razapinjućeg stabla grafa. Razapinjuće stablo je stablo koje uključuje svaki čvor osnovnog grafa jednom
  • праволинијско минимално разапињуће стабло ПМРС у скупу од н тачака у раван или уопштеније у ℝд је минимално разапињуће стабло где је тежина ивица између
  • dodajte ga u S 7 Dodaj granu najmanje težine u S od T 8 T je minimalno razapinjuće stablo od G. Kao i u Kruškalovom algoritmu, praćenje komponente T može se
  • Крускалов алгоритам је похлепни алгоритам који проналази минимално разапињућe стабло за повезани тежински граф. Ово значи да проналази подскуп грана које
  • Minimalno stablo je razapinjuće stablo na potpunom podgrafu metričkog zatvaranja koje sadrži samo granične tačke i ivice koje ih spajaju. Ovakvo stablo je 2
  • графова која налази минимално разапињуће стабло за повезани тежински граф. То значи да налази подскуп грана које формирају стабло које укључује све чворове
  • najmanji zajednički predak Dekartovog stabla Jednom kad je minimalno razapinjuće stablo sortirano, Dekartovo stablo se može konstruisati za linearno vreme
  • je sadržana u jednom od razapinjućih stabala od F. Ovo lomi razapinjuće stablo na dva stabla ali je moguće da postoji druga grana koja ih povezuje. Izazov