Razapinjuće stablo — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
Нема описа измене |
||
Ред 3:
[[File:4x4 grid spanning tree.svg|thumb|Razapinjuće drvo (plave teske grane) rešetke grafa]]
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''.
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.
| |||