Связность в неориентированных графах

Определение. Неориентированный граф G связен, если существует хотя бы один маршрут в G между каждой парой вершин i и j.

Определение. Подграфом графаG(V,E) называется граф, все вершины которого принадлежатV(G), а все ребра принадлежатE(G).

Определение. Максимальный связный подграф графа G называется связной компонентой графа G.Замечание:Максимальный не в смысле количества ребер, а в смысле нерасширяемости.

Например, на рисунке 19 изображен несвязный граф с тремя компонентами связности.

Заметим, что каждая компонента связности неориентированного графа представляет собой неориентированный граф, а значит, для нее выполняется лемма о рукопожатиях.

Связность ориентированных графов

Определение. Ориентированный граф G связен, если неориентированный граф, получающийся из G путем удаления ориентации ребер, является связным.

Определение. Ориентированный графсильно связен, если для каждой пары вершинiиjсуществует по крайней мере один путь изiвjи по крайней мере один путь изjвi.

Определение. Максимальный сильно связный подграф орграфа называетсясильно связной компонентой.

На рисунках 20 – 222 изображены несвязный, связный, но не сильно и сильносвязный графы соответственно.

Циклы

Эйлеров цикл

Определение.Эйлеров цикл— цикл, который проходит ровно один раз по каждому ребру (дуге) графа.

Определение. Если граф имеет цикл, содержащий все ребра (дуги) графа по одному разу, то граф называется эйлеровым.

Не все графы имеют эйлеровы циклы, но если эйлеров цикл существует, то это означает, что, следуя вдоль этого цикла, можно нарисовать граф на бумаге, не отрывая от нее карандаша.

Граф, изображенный на рисунке 23 является эйлеровым. Задача о Кенегсбергских мостах, рассмотренная выше предполагает нахождение эйлерова цикла в мультиграфе.

Теорема.Связный неориентированный граф G содержит эйлеров цикл тогда и только тогда, когда все вершины в нем имеют четную степень.

Доказательство.

1. Докажем прямую теорему.

Пусть граф Gсодержит эйлеров цикл, значит, существует цикл, проходящий по всем ребрам графа ровно по одному разу. Будем идти по циклу, и считать степени вершин. Т.к. проходя через вершину каждый раз, прибавляем к её степени 2, то степени всех вершин четны.

2. Докажем обратную теорему (способ доказательства – конструктивный, то есть дает алгоритм построения эйлерова цикла).

Пусть все вершины графа имеют четную степень. Будем строить эйлеров цикл, начиная с некоторой вершины v₀, при этом пройденные ребра будем удалять. Так как все вершины имеют четную степень, то, попав в какую-либо вершину, обязательно найдем ребро, по которому можно из неё выйти. Таким образом, обязательно вернемся в вершинуv₀, получив при этом некоторый цикл Р. Если при этом все ребра графа участвуют в цикле, то теорема доказана.

В противном случае, так как граф связен, обязательно найдется ребро не входящее в цикл, но инцидентное какой-либо вершине цикла. Обозначим эту вершину v₁. Будем строить цикл начиная с вершиныv₁. Из аналогичных соображений мы обязательно вернемся в вершинуv₁, получив цикл Р1. Если при этом все ребра графа присутствуют в циклах Р и Р1, то циклv₁Рv₁Р1v₁содержит все ребра графа по одному разу, то есть является эйлеровым, следовательно, теорема доказана. В противном случае продолжаем аналогичные рассуждения. Так как ребер в графе конечное количество построение цикла обязательно закончится.

Теорема.Связный орграф является эйлеровым тогда и только тогда, когда полустепень исхода каждой вершины равна полустепени ее захода.

Доказательство аналогично случаю неориентированного графа.