Razapinjuće stablo

U matematičkom polju teorije grafova razapinjuće stablo T povezanog, neusmerenog grafa je stablo koje se sastoji od svih vrhova i nekih (ili možda čak i svih) 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 (ili petlji). S druge strane, svaki most od G mora pripadati T.

Razapinjuće drvo (plave teske grane) rešetke grafa

Razapinjuće stablo povezanog grafa G se takođe 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 određenim poljima teorije grafova često je korisno pronaći minimalno razapinjuće stablo opterećenog grafa. Drugi problemi optimizacije razapinjućeg drveća su takođe 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.

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 između 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 između 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.

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 takođe 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).

Brojanje razapinjućih stabala

Kajlejeva formula broji broj razapinjućih stabala u kompletnom grafu. Postoji: $2^{2-2}=1$ stabala u $K_{2}$,
$3^{3-2}=3$ stabala u $K_{3}$, i
$4^{4-2}=16$ stabala u $K_{4}$.

Broj t(G) razapinjućih stabala povezanog grafa je dobro proučena invarijanta. U nekim slučajevima, lako je izračunati t(G) direktno. Na primer, ako je G drvo samo po sebi, t(G)=1, a ako je G cikličan graf $C_{n}$ sa n vrhova, onda je t(G) = n. Za bilo koji graf G, broj t(G) 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}$ sa n vrhova. Formula kaže da $t(K_{n})=n^{n-2}$. Drugi način iskazivanja Kajlejeve formule je da postoji tačno $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}$ tada je $t(G)=p^{q-1}q^{p-1}$, dok je G n-dimenzioni hiperkockasti graf $Q_{n}$, tada je $t(G)=2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}$. Ove formule su takođe posledice matrica-drvo teoreme.

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

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.

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, O(log 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 uređaja kako bi stvorili razapinjuće drvo koje koristi već postojeće veze kao izvorne grafove u želji da izbegnu oluje pri emitovanju.

Takođe pogledaj

Minimalno razapinjuće stablo