Spójna składowa grafu

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ż

• graf spójny
• teoria grafów
• składowa zbioru
• składowa silnie spójna