Граф G називається зв'язковим. якщо для будь-якої пари різних вершин цього графа існує ланцюг. з'єднує ці вершини.
Якщо для графа G можна вказати пару різних вершин. які б не з'єднувалися ланцюгом (простий ланцюгом), то граф називається незв'язних.
Найпростіший приклад незв'язною графа - граф, що містить ізольовану вершину, найпростіший приклад зв'язкового графа - будь-який повний граф Кn.
Теорема незв'язності графів
Граф є незв'язним тоді і тільки тоді, коли безліч його вершин V можна розбити на два непустих підмножини V1 і V2 так, щоб будь-який ребро графа з'єднувала вершини з одного підмножини.
Доведення .
Нехай G (V, E) - незв'язних граф. Зафіксуємо деяку вершину v графа і позначимо через V1 безліч. що складається з вершини v і всіх тих вершин з V, які з'єднані ланцюгами з вершиною v. Безліч V1 не порожньо (воно містить, але принаймні, вершину v) і не збігається з безліччю V (при V1 = V граф G (V, E) - зв'язний, тому що між його будь-якими двома різними вершинами існує ланцюг, що проходить через v). Розглянемо додаток V2 = V \ V1.
Безліч V2 - не порожньо, і ніяке ребро графа G (V, E) не з'єднує жодну вершину з V1 ні з однією вершиною з V2. Тому побудовані безлічі V1 і V2 утворюють шукане розбиття множини V.
Назад, нехай існує розбиття V1∪ V2. безлічі V, яке задовольняє условіютеореми.
Доведемо, що тоді граф G (V, E) незв'язних. Візьмемо довільну пару вершин v ∈ V1 і w∈ V2. з різних підмножин і припустимо, що існує ланцюг, що з'єднує ці вершини. Така ланцюг включає ребро, кінці якого належать різним підмножини, що суперечить умові. Теорема доведена.
Вершина w графа називається досяжною з вершини v, якщо або w = v, або існує ланцюг з початком v і кінцем w.
Слідство з теореми
Для того щоб граф G був зв'язковим необхідно і достатньо, щоб в ньому з будь-якої фіксованої вершини були досяжні всі інші вершини цього графа.
властивості графів
1 ° .Каждая вершина графа входить в одну і тільки в одну компоненту зв'язності.
2 ° .Будь кінцевий граф має кінцеве число компонент зв'язності.
3 ° .Граф, що складається з єдиною компоненти зв'язності, є зв'язковим.
4 ° .Каждая компонента зв'язності графа є його подграфом.
5 ° .Для будь-якого графа або він сам, або його доповнення є зв'язковим.
докази властивостей
Доведемо властивості 4 ° і 5 °.
4 °. Нехай G1 (V1, E1) - деяка компонента зв'язності графа G (V, E). Розглянемо безліч вершин V2 = V \ V1 графа G, що не входять в компоненту G1 (V1, E1). Якщо видалити кожну вершину з V2 разом з усіма інцидентними їй ребрами, отримаємо підграф графа G (V, E) збігається з компонентою зв'язності G1 (V1, E1).
5 °. Нехай G (V, E) деякий граф порядку n, а G = (V, E) - його доповнення до графа Кn. Коли граф G зв'язний, твердження очевидно. Нехай G незв'язних граф G1 (V1, E1) - одна з його компонент зв'язності і V2 = V \ V1. Тоді для будь-яких вершин v ∈ V1. w ∈ V2 -, в доповненні G існує ребро vw ∈ E. Значить, будь-яка вершина з V2 з'єднана з будь-вершиною з V1 ребром, що належить E. а будь-які дві вершини з V1 з'єднані ланцюгом довжини 2, обидва ланки якої також лежать в E. Тому граф G зв'язний.