Модуль 4. Основы Теории графОв (2 кредита) Комплексная цель и задачи изучения модуля

Цель Модуля 4 – дать представление о фундаментальных понятиях, базовых принципах и законах одного из важнейших разделов дискретной математики − теории графов, рассмотреть постановку основных задач и проблем, изучить вопросы методологии решаемой проблемы.

В результате освоения Модуля 4 студент должен быть готов продемонстрировать следующие компетенции и уровень подготовки:

1. знание основных понятий теории графов;

2. умение оценивать и определять временную сложность алгоритмов решения задач на графах;

3. знание основных определений и понятий теории графов;

4. умение составлять формализованное описание и математическую постановку основных задач на графах;

5. знание основных тождеств, теорем и законов теории графов;

6. практические навыки использования основных графовых алгоритмов для решения различных оптимизационных задач.

Самостоятельная работа предусматривает проработку лекций (1,2 часа в неделю), тестирование, а также изучение литературы, формулировку цели работы, объекта и задач исследования, методов, источников и средств библиографического поиска, использованных для достижения поставленной цели.

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

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

М. Клайн

Глава 15. Введение в теорию графов

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

Цели

Освоив эту главу, студенты должны:

• знать способы задания графов;

• уметь выполнять операции над графами;

• уметь строить матрицы инцидентности, смежности и списки, а также переходить от одной формы представления графа к другой;

• уметь строить платоновы графы;

• определять для любого вида графа его двойственный;

• знать определение нечеткого графа и различать нечеткие неориентированные графы первого и второго рода;

• строить подграфы и суграфы на смешанном графе, мультиграфе;

• определять маршруты, цепи, циклы в произвольном графе;

• определять компоненты связности графа;

• выполнять разбиение графа;

• определять точки сочленения и мосты в графе;

• определять кратчайшие пути в графе на основе алгоритмов Дейкстры и Форда.

15.1. Способы задания графов и виды графов

15.1.1. Способы задания графов

При изучении взаимосвязи между объектами (взаимоотношений людей в коллективах, связей в ЭВА, в молекулах, микросхемах и т.п.) исследуемый объект обозначается точками и соединяющими их линиями. Такое изображение ввиду наглядности позволяет определять наиболее существенные связи, находить оптимальное решение задачи, определять ошибки в рассуждениях и т.д. Описание, состоящее из точек и соединяющих их линий, оказывается удобной моделью любого объекта, в связи с чем представляет интерес исследование самого этого объекта.

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

Понятие графа опирается на понятие множества. Графом можно назвать объект, состоящий из двух множеств: точек и линий, которые находятся между собой в некотором отношении. Множество точек графа обозначается X = {x₁, x₂, …, x_n}, |X| = n и называется множеством вершин. Множество линий, соединяющих любые пары вершин, (x_i, x_j)  X называется множеством ребер или дуг и обозначается U = {u₁, u₂, …, u_m}, |U| = m.

Граф, у которого все вершины “помечены” целыми числами от 1 до n, называется помеченным. Числа 1, 2, …, n называют метками графа и обозначают вершины графа G через 1, 2, …, i, …, n или x₁, x₂, …, x_i, …, x_n, или x(1), x(2), …, x(i), …, x(n). Причем все вышеуказанные записи являются равносильными. Заметим, что для реальных задач необходима нумерация элементов. Поэтому в дальнейшем будем рассматривать помеченные графы. Аналогичным образом помечаются ребра.

Тогда графом можно считать математический объект, который обозначается G = (X ,U) и состоит из множества вершин и множества ребер или дуг, находящихся между собой в некотором отношении.

В общем случае множество линий, соединяющих любые пары вершин U, можно представить в виде U =   , где  ─ подмножество неориентированных линий, для которых несуществен порядок соединения вершин. Подмножество называется подмножеством ребер. Причем каждое ребро u_i  определяется неупорядоченной парой вершин x_k, y_l, которые оно соединяет. Записывается u_i = (x_k, y_l) или u_i = (y_l, x_k).

─ подмножество ориентированных линий, для которых существен порядок соединения вершин. Подмножество называется подмножеством дуг. Причем каждая дуга u_i  определяется упорядоченной парой (кортежем длины два) вершин x_k, y_l, которые u_i соединяет. Записывается u_i = <x_k, y_l>. Заметим, что u_i = <x_k, y_l> и u_j = <y_l, x_k> ─ это различные дуги в графе G.

─ подмножество линий, каждая из которых выходит и входит в одну и ту же соответствующую этой линии вершину. Называется подмножеством петель. Каждая петля u_i  может определяться упорядоченной или неупорядоченной парой, например вида u_i = <x_k, x_k>, u_i = (x_k, x_k).

Граф G = (X, U), у которого , ,  , называется смешанным. На рис. 15.1 показан смешанный граф G. Здесь |X| = 6, |U| = 13; U =    ; = {u₃, u₄, u₇, u₉, u₁₀, u₁₁}; = {u₁, u₂, u₈, u₁₂, u₁₃}; = {u₅, u₆}.

Рис. 15.1. Смешанный граф G

Граф G = (X, U), у которого U = , а = , называется ориентированным, или орграфом. Орграф будем обозначать D = (X, U) или G = {X, }.

Заметим, что подмножество петель можно рассматривать как ориентированные, так и неориентированные ребра. Обычно всегда оговаривают, когда рассматривается граф с петлями. Граф G, у которого U = , называется неориентированным графом, или неорграфом. Графы, не содержащие петель и кратных ребер, называются простыми.

Рассмотрим сначала неорграфы с петлями и без петель, которые будем называть графами. Граф G, у которого существует хотя бы одна пара вершин, соединяемых m ребрами u_i  U, называется мультиграфом, а максимальное m ─ мультичислом графа G (m  {2, 3, …}). Ребра, соединяющие одну и ту же пару вершин, называются кратными. На рис. 15.2 показан пример мультиграфа (m = 4).

Рис. 15.2. Мультиграф G

Если ребро u_k  U графа G = (X, U) соединяет вершины x_i, x_j  X, т.е. u_k = (x_i, x_j), то говорят, что ребро u_k – инцидентно вершинам x_i, x_j. Верно и обратное, вершины x_i, x_j инцидентны ребру u_k. Любые две вершины x_i, x_j  X графа G называются смежными, если существует соединяющее эти вершины ребро u_k  U, т.е. u_k = (x_i, x_j). Если два ребра u_k, u_i  U инцидентны одной и той же вершине, то они также называются смежными.

Основными способами задания графа G = (X, U) являются геометрический, аналитический и матричный. Основой геометрического способа задания графа является рисунок, дающий изображение графа. Изображение графа в виде рисунка обладает наглядностью, раскрывает содержательный смысл представляемого объекта, но не формально.

Рассмотрим аналитический способ задания графа. Согласно Н. Бурбаки, граф записывается как G  B = X × X. К. Берж предлагает задавать граф как соответствие Г между подмножествами множества вершин. При этом граф можно задать в виде G = (X, Г), где Г  X  X, Г = {Гx₁, Гx₂, …, Гx_n}. Здесь Г ─ это отображение множества Х в множество Х. Например, пусть задан граф G = (X, Г) (рис. 15.3). Тогда |X| = 6, X = {x₁, x₂, …, x₆}, Г = {Гx₁, Гx₂, …, Гx₆}, Гx₁ = {x₂, x₅, x₆}, Гx₂ = {x₁, x₃, x₅, x₆}, Гx₃ = {x₂, x₄}, Гx₄ = {x₅, x₆}, Гx₅ = {x₁, x₂, x₄}, Гx₆ = {x₁, x₂, x₄}.

Учитывая вышесказанное, граф часто рассматривают как пару G = (X, Г), образованную множеством X и отображением Г множества X в себя.

Отметим, что для однозначного задания графов достаточно использовать Гx₁, Гx₂, …, Гx_n-1 отображений. В этом случае элементы x_i, определяющие Гx_i, не включают в отображение Гx_i+1; в отображение Гx_i+2 не включают элементы x_i, x_i+1 и т.д. Соответственно в последнее отображение Гx_n-1 не включают элементы x₁, x₂, …, x_n-2. Тогда рассматриваемый граф G (рис. 15.3), может быть задан следующим образом: Гx₁ = {x₂, x₅, x₆}, Гx₂ = {x₃, x₅, x₆}, Гx₃ = {x₄}, Гx₄ = {x₅, x₆}, Гx₅ = .

Рис. 15.3. Граф G

Такое представление графа позволяет экономить память ЭВМ и исключать избыточную информацию при представлении графа аналитическим способом.

Большинство задач информатики удобно решать при использовании матричного задания графов. Квадратная таблица R = ||r_i,j||_nxn называется матрицей смежности, если ее элементы образуются по правилу:

Заметим, что для мультиграфа

Очевидно, что для рассматриваемых неорграфов r_i,j = r_j,i и для задания графа можно использовать треугольную матрицу R. Для графа без петель r_i,i = 0, для графа с петлями r_i,i  0. Для графа G (см. рис. 15.3) треугольная матрица смежности имеет вид

	x1	x2	x3	x4	x5	x6
x1	0	1	0	0	1	1	.
x2		0	1	0	1	1
R = x3			0	1	0	0
x4				0	1	1
x5					0	0
x6						0

Строки и столбцы матрицы R соответствуют вершинам графа G. На пересечении x_i строки и x_j столбца ставится элемент r_i,j, соответствующий числу ребер, соединяющих вершины x_i и x_j. Заметим, что строки и столбцы матрицы R также можно нумеровать числами натурального ряда, соответствующими индексам помеченных вершин графа. Петли в графе изображаются элементами r_i,j, расположенными по главной диагонали матрицы R.

Преимущество использования матриц смежности – это простота и формальность преобразований над графами.

Основной недостаток применения матрицы смежности заключается в том, что она занимает в ЭВМ память объемом |X|² даже тогда, когда граф содержит только |X| ребер. Устранением этого недостатка является представление графа в виде списков. Списком смежности для вершины x_i является совокупность всех вершин, смежных с x_i. Представление графа в виде списков смежности требует памяти ЭВМ порядка |X| + |U|. В основном таким представлением графа пользуются, когда |U| << |X|². Для графа G (см. рис. 15.3) список смежности имеет следующий вид:

x1	x2	x5	x6	0
x2	x1	x3	x5	x6	,
RL = x3	x2	x4	0	0
x4	x3	x5	x6	0
x5	x1	x2	x4	0
x6	x1	x2	x4	0

а для треугольной матрицы

x1	x2	x5	x6	1	2	5	6
x2	x3	x5	x6	2	3	5	6	.
RL= x3	x4	0	0	или RL=3	4	0	0
x4	x5	x6	0	4	5	6	0
x5	0	0	0	5	0	0	0
x6	0	0	0	6	0	0	0

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

Прямоугольная таблица вида I = ||i_k,l||_nm называется матрицей инцидентности, если ее элементы образуются по правилу:

Матрица инцидентности для G (см. рис. 1.3) имеет вид

	u1	u2	u3	u4	u5	u6	u7	u8	u9
x1	1	1	0	0	0	0	1	0	0	.
x2	1	0	1	1	0	0	0	1	0
I = x3	0	0	0	1	1	0	0	0	0
x4	0	0	0	0	1	1	0	0	1
x5	0	1	1	0	0	1	0	0	0
x6	0	0	0	0	0	0	1	1	1

Строки матрицы I соответствуют вершинам графа, столбцы – ребрам, а элемент i_k,l указывает на инцидентность вершины x_k и ребра u_l. В каждом столбце матрицы I расположено по две единицы, так как каждое ребро соединяет ровно две вершины. При наличии в графе петель соответствующие им столбцы в матрице I будут иметь по одной единице, так как петля соединяет только одну вершину графа.

А. Кофман предлагает задавать булеву матрицу как шахматную доску. Заштрихованным клеткам в булевой матрице соответствуют нули, а незаштрихованным – единицы или наоборот. Такую булеву матрицу называют сотами, так как в различных задачах на графах необходимо размещать объекты по ячейкам, объединенным в соты.

Известно, что число ячеек в матрице (сотах) размером m × n равно 2^mn. Соты порядка n содержат n² ячеек. Тогда число ячеек матрицы с k запретными элементами (соответствующие элементы булевой матрицы – нули) равно

.

Предполагается, что выполняются следующие условия:

• соты (матрица) имеют порядок n;

• в каждой ячейке матрицы располагается не более одного объекта (т.е. ноль или единица).

В этом случае ячейки матрицы разбиваются на два подмножества:

• ячейки, обладающие неким свойством;

• ячейки, не обладающие этим свойством.

Тогда, согласно А. Кофману, говорят, что граф (рис. 15.4)

Рис. 15.4. Граф G

может быть реализован в виде матрицы:

,

где закрашенным элементам матрицы соответствуют ребра графа G.

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

Кёниг и К. Берж под графом понимают разбиение теоретико-множественного произведения некоторого счетного множества на себя, на две части.

Графы иногда представляют в латинской матрице. Для графа G (рис. 15.4) такое представление имеет вид

.

Латинская матрица удобна для задания как ориентированных, так и неориентированных графов (неорграфов). Причем, в неорграфах значение элемента матрицы i, j = j, i ( в ориентированных графах наоборот, i, j  j, i).