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\}$ $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