Graf spójny

Wikipedia:Weryfikowalność
 Ten artykuł od 2012-06 wymaga zweryfikowania podanych informacji.
Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Graf spójny – graf, w którym każdą parę wierzchołków łączy pewna ścieżka[1]. Graf nieposiadający powyższej własności to graf niespójny[potrzebny przypis].

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

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 ω ( G ) . {\displaystyle \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 ⩽ ω ( G ) ⩽ | G ( V ) | {\displaystyle 1\leqslant \omega (G)\leqslant |G(V)|}

  • ω ( G ) = 1 {\displaystyle \omega (G)=1} oznacza, że graf G jest spójny,
  • ω ( G ) = | G ( V ) | {\displaystyle \omega (G)=|G(V)|} oznacza, że G składa się z | G ( V ) | {\displaystyle |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 ω ( G ) {\displaystyle \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 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 } {\displaystyle V_{1}=\{1,2,5\}}
V 2 = { 3 , 4 , 6 } {\displaystyle 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 – ω ( G ) = 2. {\displaystyle \omega (G)=2.}

Zobacz też

Przypisy

  1. ↑ a b graf, [w:] Encyklopedia PWN [dostęp 2022-03-10] .