Most (teorija grafov)

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Graf s 6 mostovi (označenimi z rdečo)
Neusmerjeni graf brez mostov

Móst (tudi prerézna povezáva) je v teoriji grafov povezava, ki, če jo odstranimo iz grafa, poveča število njegovih povezanih komponent. Po ostranitvi mostu postane graf nepovezan. Velja enakovredno - povezava je most, če in samo če ni v kakšnem ciklu grafa.

Graf je brez mostov, če ne vsebuje mostov. Lahko se vidi, da je to enakovredno 2-povezavno-povezanosti vsake netrivialne komponente. V drevesu je vsaka povezava most.

Zunanje povezave[uredi | uredi kodo]