Graf spójny

Ten artykuł od 2012-06 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła, najlepiej 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. 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.

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka stopień grafu dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu – wszerz – w głąb najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem marszrutyzacji problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego kod Prüfera

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.

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 ${\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.

${\displaystyle 1\leqslant \omega (G)\leqslant |G(V)|}$

• ${\displaystyle \omega (G)=1}$ oznacza, że graf G jest spójny,
• ${\displaystyle \omega (G)=|G(V)|}$ oznacza, że G składa się z ${\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 ${\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 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:

${\displaystyle V_{1}=\{1,2,5\}}$

${\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 – ${\displaystyle \omega (G)=2.}$

Zobacz też

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

Przypisy