Graf spójny

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
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


Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny


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ójnygraf spełniający warunek, że dla każdej pary wierzchołków istnieje ścieżka, która je łączy.

Graf nie posiadają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).

Maksymalny, w sensie inkluzji, spójny podgraf grafu nazywamy 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 \le \omega(G) \le |G(V)|

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[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]