Spójnością grafu lub spójnością wierzchołkową grafu nazywamy taką liczbę, że usunięcie z grafu pewnych
wierzchołków spowoduje, że graf przestanie być spójny lub zredukuje go do jednego wierzchołka, ale usunięcie dowolnych
wierzchołków zawsze pozostawi graf spójny.
(Wierzchołki usuwamy wraz z dochodzącymi do nich krawędziami.)Spójność grafu
oznaczamy
.
??? Czy istnieje graf 3-regularny o spójności 1?
Wszystkie prawa zastrzeżone © 2000 Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej