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ójna składowa grafu nieskierowanego G – 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 } {\displaystyle V_{1}=\{1,2,5\}}
V 2 = { 3 , 4 , 6 } {\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.

Zobacz też