Глава 6. Введение в теорию графов. Алгоритмы на графах

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

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

• Определение. Конечным графом называется тройка где X — конечное множество вершин; -конечное множество ребер (дуг); отношение инцидентности; Отношение инцидентности является трехместным отношением где которое может либо выполняться (быть истинным), либо не выполняться (быть ложным) и удовлетворяет свойствам:

1) - ребро всегда соединяет пару вершин.

2) - ребро и соответствует не более чем одной паре вершин х, у.

• Графическое представление графов.

(см. скан)

Рис. 6.1. Графы с тремя вершинами и двумя ребрами

• Определение. называются изоморфными если существуют два взаимно однозначных соответствия сохраняющие отношение инцидентности: Из определения следует, что изоморфные графы можно одинаково изображать графически и отличаться они будут только метками вершин (рис. 6.2).

• Определение. Граф называется ориентированным (орграф), если каждое его ребро ориентировано: Иногда удобно преобразовать неориентированный граф в ориентированный — заменой каждого неориентированного ребра парой ориентированных ребер с противоположной ориентацией.

• Определение. Подграфом графа называется такой граф что Обозначают

• Определение. Граф называется псевдографом, если в нем допускаются петли и кратные ребра, т. е. две вершины могут быть соединены более чем одним ребром. Псевдограф без петель называется мулътиграфом (рис. 6.3).

Рис. 6.2. Три изоморфных графа

Рис. 6.3. Псевдограф (слева) и мультиграф (справа)

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

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

Рис. 6.4. Полные неориентированные графы • Определение. Дополнением простого графа называется граф имеющий те же вершины, а его ребра являются дополнением до полного графа (рис. 6.5).

Рис. 6.5. Исходный граф и дополнительный

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

Рис. 6.6. Граф плоский, а граф неплоский

• Определение. Если вершины х и у соединены ребром и, то говорят, что вершины х, у смежные, а ребро и инцидентно вершинам Два ребра называются смежными, если они имеют общую вершину.

• Определение. Степенью вершины графа называется количество ребер, инцидентных данной вершине. Вершина графа, имеющая степень 0, называется изолированной, а если степень ее равна 1, то такая вершина называется висячей.

• Определение. Граф называется помеченным (или перенумерованным), если его вершины отличаются друг от друга какими-либо пометками (рис. 6.7).

Рис. 6.7. Граф помеченный, а граф непомеченный

• Определение. Путь (маршрут) на графе определяется последовательностью вершин и ребер где Ребро и, соединяет вершину с вершиной т.е. выполняется отношение инцидентности

Маршрут называется цепью, если все его ребра различные.

• Маршрут называется замкнутым, если .

• Замкнутая цепь называется циклом.

• Цепь называется простой, если не содержит одинаковых вершин.

• Простая замкнутая цепь называется простым циклом.

• Гамильтоновой цепью называется простая цепь, содержащая все вершины графа.

• Гамилътоновым циклом называется простой цикл, содержащий все вершины графа.

• Определение. Граф называется связным, если для всех существует путь из вершины х в вершину у (вершины связаны маршрутом). Связный ориентированный граф называется сильно связным. Орграф называется слабо связным, если соответствующий ему неориентированный граф (игнорируется ориентация ребер) связный (рис. 6.8).

Рис. 6.8. - слабо связный, сильно связный

• Определение. Связный неориентированный ациклический граф называется деревом, множество деревьев называется лесом.

Рис. 6.9. - дерево, не дерево

Большинство задач на графах касается определения компонент связности, поиска маршрутов, расстояний и т.п. Далее будут рассмотрены решения подобных вопросов. Однако при решении реальных задач соответствующие им графы весьма велики, и анализ возможен лишь с привлечением современной вычислительной техники. Поэтому конечной целью рассмотрения каждой из задач будет являться описание и реализация практического алгоритма решения данной задачи на ЭВМ.