Most (teorija grafov)

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 s 6 mostovi (označenimi z rdečo)
Neusmerjeni graf brez mostov

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

  • Weisstein, Eric Wolfgang. »Graph Bridge«. MathWorld.