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

Садржај обрисан Садржај додат
Нема описа измене
Нема описа измене
Ред 4:
Za protokol korišćen u sprečavanju prosledjivanja petlje na LAN.
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.