Most (teoria grafów)

Most – krawędź grafu spójnego, której usunięcie z grafu rozspójnia go. Według innej definicji mostem jest krawędź, której usunięcie zwiększa liczbę spójnych składowych grafu[1].

Mosty grafu
Mosty grafu

Właściwości edytuj

  • Jeśli e jest mostem grafu płaskiego G, to e leży na brzegu dokładnie jednej ściany G.

Zobacz też edytuj

Przypisy edytuj

  1. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 10. ISBN 0-387-95014-1.