Материал: Дискретная математика. учебное пособие. Собенина О.В

В результате работы алгоритма определены гамильтоновы пути ₁=[a,b,e,c,d,f], ₂=[a,b,e,d,f,c] и контуры [a,b,e,c,d,f,a], [a,b,e,d,f,c,a].

4.12.3. Алгебраический метод выделения гамильтоновых путей и контуров

Замечание. «Внутреннее произведение вершин» пути [x₁,…,x_k] определяется как формальное выражение вида x₂x₃…x_k-1, не содержащее две концевые вершины x₁ и x_k.

Шаг 1. G – данный орграф на n вершинах; А – матрица смежности с нулевыми элементами на диагонали; – модифицированная матрица смежности, в которой b_ij=bij)=x_j, если существует дуга из x_i в x_j и 0 в противном случае. Положить k=1,  ^k=A.

Шаг 2. Положить k=k+1. Найти P ^k=BP ^k-1.

Шаг 3. Если k=n, то диагональные элементы матрицы P ⁿ дают внутренние произведения вершин, которые соответствуют гамильтоновым контурам графа. Получить гамильтоновы контуры. Останов. Иначе перейти к шагу 4.

Шаг 4. Сделать все пути простыми, обнулив в матрице P^k все диагональные элементы, которые содержат сомножителями вершины, соответствующие данной строке. Перейти к шагу 5.

Шаг 5. Если k=n-1, то элементы матрицы P^k дают внутренние произведения вершин, которые соответствуют гамильтоновым путям графа G. Получить гамильтоновы пути. Перейти к шагу 2.

П ример. Рассмотрим граф, изображенный на рис. 4.44.

Рис. 4.44

Матрица смежности А этого графа имеет вид

a b c d e

a 0 1 0 1 0

A = b 0 0 0 1 1

c 0 1 0 0 1

d 0 0 1 0 0

e 1 0 1 0 0

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

a b c d e

a 0 b 0 d 0

b 0 0 0 d e

B = c 0 b 0 0 e

d 0 0 c 0 0

e a 0 c 0 0

Положим P₁=A. Матрица P₂’=B₁ получается равной

a b c d e

a 0 0 d b b

b e 0 d+e 0 0

P₂’ = c e 0 e b b

d 0 c 0 0 c

e 0 a+c 0 a c

Матрица P₂ почти такая же, как P₂’, только подчеркнутые элементы в P₂’ надо заменить нулями. Матрица P₃’=BP₂ равна

a b c d e

a be dc bd+be 0 dc

b 0 dc+ea+ec 0 ea dc

P₃’= c be ea+ec bd+be ea 0

d ce 0 0 cb cb

e ce 0 ad ab+cb ab+cb

Матрица Р₃ получается из P₃’ после замены подчеркнутых элементов нулями. Матрица Р₄’=BP₃

a b c d e

a dce 0 0 bea bdc+dcb

b dce 0 ead eab+ecb dcb

P₄’= c 0 0 ead bea+eab+ecb bdc

d cbe cea 0 cea 0

e cbe adc+cea abd+abe cea adc

Гамильтоновы пути можно определить по матрице Р₄, которая имеет вид

a b c d e

a 0 0 0 0 bdc+cdb

b dce 0 ead 0 0

P₄= c 0 0 0 bea+eab 0

d cbe cea 0 0 0

e 0 adc abd 0 0

Гамильтоновы пути abdce и adcbe, соответствующие элементу (1,5) матрицы Р₄ дают гамильтоновы контуры abdcea и adcbea, если добавить замыкающую дугу (е,а). Все другие гамильтоновы пути в Р₄ приводят к тем же самым контурам, и потому в графе G есть только два таких контура.

Пример. Математическая постановка задачи нахождения оптимальной последовательности выпуска изделий.

Введем некоторые обозначения. Пусть {a₁…a_L} - множество всевозможных последовательностей выпуска изделия L модификаций; - количество оборудования в группе , где =1,…,N; - время, необходимое на переналадку единицы оборудования -ой группы при переходе с выпуска i-ой модификации на выпуск j-ой модификации.

Пусть G - ориентированный граф, вершины которого представляют изделия, а существование дуги (х_i, х_i) означает, что изделие j может следовать за изделием i без перенастройки оборудования. Тогда, если в этом графе есть гамильтонов цикл (ориентированный цикл, проходящий через каждую вершину графа), то существует последовательность выпуска изделий, не требующая перенастройки оборудования. Если не существует циклической последовательности выпуска изделий, не требующей перенастройки оборудования, то задача сводится к нахождению последовательности выпуска изделий, требующих наименьших затрат на перенастройку оборудования.

Пусть х_ij =1, если после изделия i-ой модификации выпускается изделие j-ой модификации; х_ij=0, если после изделия i-ой модификации изделие j-ой модификации не выпускается.

С так введенными переменными ставим задачу:

Минимизировать функцию

(1)

при условиях

, , . (2)

В качестве дополнительных ограничений необходимо наложить условие «петель», для устранения подконтуров в задаче

(3)

Задача (1)-(3) полностью аналогична классической задаче коммивояжера:

(4)

при условиях

, , . (5)

условие «петель»

(6)

В задаче коммивояжера (4)-(6) ищется оптимальная последовательность обхода «городов», а в задаче (1)-(3) оптимальная последовательность выпуска изделий. В задаче (4)-(6) матрица D с элементами является матрица расстояний между N «городами», этой матрице соответствует матрица В в задаче (1)-(3) с элементами , которая является матрицей времени переналадки оборудования

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

4.13. Плоские и планарные графы

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

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

П римеры плоских графов (рис. 4.45).

а б

Рис. 4.45. Плоские графы

Любой граф, изоморфный плоскому графу, будем называть планарным. Граф на рис. 4.46 является планарным, так как он изоморфен графу на рис. 4.45.б.

Рис.4.46

Очевидны следующие утверждения:

1. всякий подграф планарного графа планарен;

2. граф планарен тогда и только тогда, когда каждая его связная компонента – планарный граф.

О планарных графах говорят, что они укладываются на плоскости (имеют плоскую укладку).

4.13.1. Формула Эйлера

Область, ограниченная ребрами в плоском графе, и не содержащая внутри себя вершин и ребер, называется гранью графа. Внешняя часть плоскости также образует грань. На рис. 4.47 изображен граф с 3 гранями.

Будем использовать следующие обозначения: n, m, f – соответственно число вершин, ребер и граней плоского графа.

Рис. 4.47

Теорема 4.13.1. (Теорема Эйлера, 1758 г.). Для всякого связного плоского графа верно равенство

n–m+f=2, (4.6)

которое называется формулой Эйлера.

Доказательство. G – связный плоских n-вершинный граф. Рассмотрим некоторый остов Т этого графа. Очевидно, что дерево Т имеет одну грань (внешнюю) и n вершин. В то же время известно, что число ребер дерева Т равно n–1. Поэтому для графа Т формула (4.6) верна. Теперь будем поочередно добавлять к Т недостающие ребра графа G. При этом на каждом шаге число вершин не меняется, а число ребер и число граней увеличивается на единицу. Следовательно формула (4.6) будет верна для всякого графа, получающегося в результате таких операций, а потому она верна и для графа G, которым заканчивается вся эта процедура.

Из теоремы Эйлера вытекают следующие следствия.

Следствие 4.13.1. Число граней любой плоской укладки связного планарного графа постоянно и равно m–n+2.

Другими словами, число f не зависит от способа укладки этого графа на плоскости.

Следствие 4.13.2. Для связного планарного графа m 3n-6 при n3.

Формула Эйлера позволяет доказать непланарность некоторых графов.

Графом K₅ называется граф с 5 вершинами, в котором каждая пара вершин соединена ребром.