Spójna składowa grafu

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Definicja intuicyjna:

Spójna składowa to fragment grafu, który nie jest połączony z innym fragmentem. Graf spójny składa się z jednej spójnej składowej, grafy niespójne mają ich więcej.

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

Innymi słowy 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.

Graf ten jest spójny, więc zgodnie z definicją ma jedną spójną składową.
Graf ten nie jest spójny, składa się 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.

Zobacz też[edytuj | edytuj kod]