Most (teória grafov)

Most grafu je taká hrana, ktorá nepatrí do žiadnej kružnice. Teda každá hrana acyklického grafu je mostom, ale most sa môže objaviť aj v grafoch obsahujúcich kružnicu. Príkladom je graf  na obrázku, v ktorom sú hrany  obsiahnuté v kružnici a teda nie sú mostami. Naproti tomu hrana  nepatrí do žiadnej kružnice a teda ide o most.


 Veta 
Ak z grafu vynecháme most, zväčší sa počet jeho komponentov o jednotku. Dôkaz vety vyplýva priamo z definície mostu. Most hrá medzi hranami podobnú úlohu ako artikulácia medzi vrcholmi.

 Literatúra 
 Znám, Š: Kombinatorika a teória grafov. Bratislava, Matematicko-fyzikálna fakulta Univerzity Komenského. 1982, s. 42

Kategória:Teória grafov