Связность графов

Связность

Граф 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 связен.