Razapinjuće stablo — разлика између измена

 

U [[matematika|matematičkom]] polju [[teorija grafova|teorije grafova]] '''razapinjuće stablo''' ''T'' povezanog, [[graf|neusmerenog grafa]] je [[stablo|drvo]] koje se sastoji od svih vrhova i nekih (ili možda čak i svih) [[graf|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''.

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 [[Problem Hamiltonovog puta|Problemom Hamiltovog puta]]), razapinjuće drvo minimalnog prečnika, i razapinjuće drvo minimalne dilatacije.

 

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 korespodencija 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.

 

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ć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 - [[stablo|šuma]] (ne sadrži ciklove) i razapinjući (sadrži svaki čvor).

 

 

[[Image:Cayley's formula 2-4.svg|thumb|Kajlejeva formula broji broj razapinjućih stabala u kompletnom grafu. Postoji:

 

 

 

<math>4^{4-2}=16</math> stabala u <math>K_4</math>.]]

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.

 

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ća|verovatnoći]] i [[matematička fizika|matematičkoj fizici]].

 

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

 

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.

 

[[Minimalno razapinjuće stablo]]