Graf spójny – graf, w którym każdą parę wierzchołków łączy pewna ścieżka.
Ten artykuł od 2012-06 wymaga zweryfikowania podanych informacji. |
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).
Maksymalny, w sensie inkluzji, spójny podgraf grafu nazywa się spójną składową. Liczba spójnych składowych grafu G oznacza się przez
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.
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 (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).
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:
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 –
This article uses material from the Wikipedia Polski article Graf spójny, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Treść udostępniana na licencji CC BY-SA 4.0, jeśli nie podano inaczej. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Polski (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.