Алгоритмы на графах

Введение в теорию графов

Среди дисциплин и методов дискретной математики теория графов и особенно алгоритмы на графах находят наиболее широкое применение в программировании. Дело в том, что теория графов дает очень удобный язык для описания программных моделей. Особенно важно наличие наглядной графической интерпретации понятия графа. Картинки позволяют сразу «усмотреть» суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовые доказательства и сложные формулы.

Начало теории графов относят к 1736 г., когда Л. Эйлер решил задачу о Кениксбергскихмостах. Около 100 лет это был единственный результат теории графов. В задаче о Кениксбергских мостах (см. рис. 1) необходимо было определить можно ли, начав с некоторой точки, совершить прогулку и вернуться в исходную точку, пройдя по каждому мосту ровно один раз.

В 1930 году К. Куратовским была решена задача о трех домах и трех колодцах, сформулированная следующим образом: «Имеются три дома и три колодца. Жители домов поссорились и решили проложить дороги к своим колодцам так, чтобы они не пересекались. Возможно ли это?»

Почти 100 лет не была доказана теорема о раскраске карты: «Любую карту на плоскости можно раскрасить четырьмя красками так, чтобы никакие две соседние области не были закрашены одним цветом.»

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

На рисунках 2 и 3 изображены участок электрической цепи и часть карты дорог. Ясно, что оба эти рисунка могут быть представлены одной и той же диаграммой из точек и линий, изображенной на рисунке 4

Основные определения

Определение. Определимграф как совокупность двух множеств непустого множества V (множество вершин) и множества E неупорядоченных и упорядоченных пар вершин из V.

Определение. Неупорядоченная пара вершин называетсяребром, а упорядоченная пара -дугой.

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

Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам. В трехмерном пространстве любой граф можно представить, таким образом, что линии (ребра) не будут пересекаться. Вершины графа на рисунке выделяют обычно кружочками или квадратиками, так как не всегда точки пересечения ребер являются вершинами графа.

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

На рисунках 6 и 7 изображены ориентированный и смешанный графы, соответственно.

Обозначения

Множество вершин будем обозначать большой латинской буквой V. Элементы этого множества (вершины) – маленькими латинскими буквами vс индексом. Множество ребер (дуг) обозначим большой латинской буквой Е, а сами ребра (дуги) - маленькими латинскими буквами е с индексом. Граф G с множеством вершин V и множеством ребер Е будем обозначать G(V,E). Количество вершин (мощность множества V) будем обозначать |V|, количество ребер (дуг) – |E|.

Для графа, изображенного на рисунке 1.5

V={v₁, v₂, v3, v₄, v₅, }, |V|=5,

E={e₁, e₂, e₃, e₄, e₅, e₆, e₇, e₈ }, |E|=8.

Определение. Вершины, соединенные ребром (дугой), называютсясмежными. Ребра (дуги), имеющие общую вершину, также называются смежными.

Определение. Ребро и любая из его двух вершин называютсяинцидентными.

Определение. Степень вершиныв неориентированном графе - число ребер, концом которых является эта вершина. Будем обозначать степень i-той вершины через deg v_i.

Например, для графа, изображенного на рисунке 5:

• вершины v₁ и v₂ смежны, а вершины v₄ и v₂ не смежны.

• ребро е₁ инцидентно вершинам v₁ и v₂

• степень первой вершины равна 4 (deg v₁=4).

Определение. Пустьvвершина орграфаDназовемполустепенью исходаvчисло дуг орграфаD, имеющих вид (v,w); аналогичнополустепенью заходаvназовем число дуг вида (w,v).

Будем обозначать полустепень захода i-той вершины через deg⁺ v_i, полустепень исхода i-той вершины через deg^- v_i.

Например, для графа, изображенного на рисунке 6 deg⁺ v₁=3, deg^- v₁=1.

Определение. Если два ребра инцидентны одной и той же паре вершин, они называютсякратными.

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

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

Определение. Ребро (дуга) называется петлей, если начало и конец его (её) совпадают.

Определение.Граф содержащий петли называется псевдографом

Рис. 9

На рисунке 9 изображен мульти-псевдограф.

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

Теорема. (Лемма о рукопожатиях). В простом графе сумма степеней всех его вершин – число четное, равное удвоенному числу ребер графа.

Доказательство. Очевидно, что каждое ребро вносит 2 в сумму степеней вершин.

Теорема. Число нечетных вершин простого графа четно.

Доказательство. Предположим противное: существует графG, имеющий нечетное количество вершин нечетной степени. Подсчитаем сумму степеней всех вершин – она будет нечетной, что противоречит лемме о рукопожатиях.

Орлемма о рукопожатии. Сумма полустепеней захода всех вершин орграфа равна сумме полустепеней исхода всех вершин.

Доказательство. Каждая дуга “участвует” в каждой сумме ровно один раз.

Примеры графов

Определение.Регулярный граф – граф, у которого все вершины имеют одну и ту же степень.

На рисунке 10 изображен регулярный граф со степенью регулярности 2. На рисунке 11 – регулярный граф со степенью регулярности 3. Граф, изображенный на рисунке 11 называют графом Петерсона, он интересен тем, что любые две его вершины соединены маршрутом, проходящим не более чем по двум ребрам.

Определение. Граф называетсяполным, если каждые две его различные вершины соединены одним и только одним ребром.

Полный граф с nвершинами обозначается К_n. На рисунке 12 изображены полные графы на 2, 3 и 5 вершинах.

Определение. Двудольный граф-это граф G(V,E), такой что множество V разбито на два непересекающихся множества V₁ и V₂(,), причем всякое ребро из E соединяет вершину из V₁ с вершиной из V_2. Множества V₁ и V₂ называются долями двудольного графа. Если двудольный граф содержит все ребра, соединяющий множества V₁ и V₂, то он называется полным двудольным графом.

Полный двудольный граф с m вершинами в одной доле и n вершинами в другой обозначается К_mn. На рисунке 13 изображен полный двудольный граф К₃₃

Способы описания графа.

При решении задач на компьютере граф должен быть представлен дискретным способом. Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Выбор наилучшего представления определяется требованиями задачи. При решении конкретных задач используются, как правило, некоторые комбинации или модификации указанных представлений.