Most (teória grafov)

z Wikipédie, slobodnej encyklopédie
Jump to navigation Jump to search

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.

Graf G

Veta[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

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