Graf spójny

Szablon:Dopracować Graf spójny – graf, w którym każdą parę wierzchołków łączy pewna ścieżka. Graf nieposiadający powyższej własności to graf niespójnySzablon:Fakt.

Warunkiem koniecznym, by graf skierowany był spójny, jest spójność jego grafu podstawowego (tego samego grafu bez kierunków na krawędziach).

Spójne składowe

Maksymalny, w sensie inkluzji, spójny podgraf grafu nazywa się spójną składową. Liczba spójnych składowych grafu G oznacza się przez $\omega (G).$

Inaczej, spójną składową grafu G jest jego spójny podgraf nie zawarty w większym podgrafie spójnym grafu G.

Nieformalnie, spójna składowa grafu jest to taki podgraf, który można ‘wydzielić’ z całego grafu bez usuwania krawędzi. Graf spójny ma jedną spójna składową. Dla przykładu, w lesie spójnymi składowymi są drzewa. Spójna składowa to fragment grafu, który nie jest połączony z innym fragmentem.

$1⩽\omega (G)⩽|G(V)|$

• $\omega (G)=1$ oznacza, że graf G jest spójny,
• $\omega (G)=|G(V)|$ oznacza, że G składa się z $|G(V)|$ izolowanych wierzchołków.

Wierzchołek v nazywa się rozspajającym graf G (przegubem lub punktem artykulacji w grafie G), jeżeli usunięcie v z G (wraz z przyległymi do niego krawędziami) powoduje zwiększenie $\omega (G)$ (czyli jeśli po usunięciu v wraz z przyległymi do niego krawędziami, graf G ma więcej składowych niż wcześniej).

Przykład

Graf spójny

Graf ten jest spójny, więc zgodnie z definicją ma jedną spójną składową.

Po usunięciu krawędzi 2-3 i 4-5 graf ten nie jest już spójny, składa się wtedy z dwóch oddzielnych zbiorów wierzchołków:

$V_1=\{1,2,5\}$

$V_2=\{3,4,6\}$

Każdy z tych zbiorów jest spójną składową grafu, a więc łącznie cały graf posiada dwie spójne składowe – $\omega (G)=2.$

Zobacz też

• graf k-spójny
• most
• przegub
• przestrzeń spójna
• relacja spójna