Razapinjuće stablo — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
Нема описа измене |
||
Ред 2:
==Razapinjuće stablo==
U [[matematika|matematičkom]] polju [[teorija grafova|teorije grafova]] '''razapinjuće drvo''' 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 drvo 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 povezanog grafa G se takodje 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 odredjenim poljima teorije grafova cesto je korisno pronaci [[minimalno razapinjuće stablo]] opterećenog grafa. Drugi problemi optimizacije razapinjućeg drveća su takodje 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 stvoriti cikl; takav cikl se naziva '''osnovni cikl'''. Postoji poseban fundamentalni cikl za svaku ivicu; tako, postoji 1-1 korespodencija izmedju osnovnih cikala 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.
Dualnost izmedju 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.
Ред 19:
==Brojanje razapinjućih stabala==
Broj t(G) razapinjućih stabala povezanog grafa je dobro proučena invarijanta. U nekim slucajevima, lako je izracunati 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.
| |||