Википедија

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

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Нема описа измене
Нема описа измене
Ред 7:
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 cestočesto je korisno pronacipronać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 najvise ''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.
 
==Osnovni ciklusi==
Dodajući samo jednu granu u razapinjuće stablo ceće stvoriti cikl; takav cikl se naziva '''osnovni cikl'''. Postoji poseban fundamentalni cikl za svaku ivicu; tako, postoji 1-1 korespodencija između osnovnih cikalaciklova 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 tacno ''V''-1 osnovnih podskupova grafa, po jedan za svaku granu razapinjućeg stabla.
Ред 29:
<math>4^{4-2}=16</math> stabala u <math>K_4</math>.]]
 
Broj ''t(G)'' razapinjućih stabala povezanog grafa je dobro proučena invarijanta. U nekim slucajevimaslučajevima, lako je izracunatiizračunati ''t(G)'' direktno. Na primer, ako je ''G'' drvo samo po sebi, ''t(G)''=1, a ako je ''G'' cikličan graf <math>C_n</math> 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 [[kompletan graf|kompletnom grafu]] <math>K_n</math> sa ''n'' vrhova. Formula kaze da <math>t(K_n)=n^{n-2}</math>. Drugi nacin iskaživanjaiskazivanja Kajlejeve formule je da postoji tacnotačno <math>n^{n-2}</math> 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 <math>K_{p,q}</math> tada je <math>t(G)=p^{q-1}q^{p-1}</math>, dok je ''G'' ''n''-dimenzioni hiperkockasti graf <math>Q_n</math>, tada je <math>t(G)=2^{2^n-n-1}\prod_{k=2}^n k^{{n\choose k}}</math>. Ove formule su takođe posledice matrica-drvo teoreme.
Ред 38:
 
==Homogena razapinjuća stabla==
Razapinjuće stablo izabrano nasumično od svih razapinjucih stabala sa jednakom verovatnocomverovatnoć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]].
 
==Algoritmi==
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 sirinuš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 RazapinjuceRazapinjuće Drvo Protokol, korišćen od strane "OSI link layer"-[[Sloj veze|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==
Преузето из „https://sr.wikipedia.org/wiki/Razapinjuće_stablo”