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''.▼
[[File:4x4 grid spanning tree.svg|thumb|Razapinjuce drvo (plave teske grane) resetke grafa]]
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 [[matematika|matematičkom]] polju [[teorija grafova|teorije grafova]] '''razapinjuće
▲Razapinjuće
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.
| |||