Эйлеровы графы.

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

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

Т

A

C

D

B

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

Давно известны развлечения, в которых требуется обрисовать некоторую фигуру, не прерывая и не повторяя линии.

Сабли Магомета:

Эйлер сформулировал общую задачу, касающуюся графов: в каких случаях в конечном графе можно найти такой цикл, в котором каждое ребро графа участвовало бы один раз?

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

Ответ состоит в следующем:

конечный граф G является эйлеровым графом тогда и только тогда, когда:

1) граф G связан

2) степень всех его вершин четна.

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

Теорема. Пусть G - конечный связный граф с k вершинами нечетной степени. Тогда минимальное число непересекающихся по ребрам цепей, покрывающих G равно 1/2k.

Аналогичные результаты можно получить для ориентированных графов.

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

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

Гамильтоновы циклы.

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

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

Задача коммивояжера.

Формулировка задачи. Имеется m городов и известна стоимость проезда из одного города в другой. Комивояжер должен выехать из одного города, побывать в каждом городе ровно 1 раз и вернуться в исходный город. Общая стоимость проезда должна быть минимальной.

Формулировка в терминах теории графов. Есть ориентированный граф, каждая пара вершин соединена двумя дугами (i, j) и (j, i). l(i, j) - длина каждой дуги (стоимость проезда). Найти цикл проходящий ровно 1 раз через все (гамильтонов цикл) минимальной длины.

Если дороги из i в j нет (ден дуги), то l(i, j)=.

Для решения задачи граф задается в виде матрицы длины дуг размерности mm. Каждой дуге ставится в соответствии элемент матрицы.

	1	…	k	…	j
1	
i j k ……		
			
i			l(i, k)		l(i, j)
:
k					

Алгоритм решения.

	1	2	3	4	5	6	7	8
1		5	3	2	4	5	2	7
2	7		1	6	7	8	9	6
3	3	2		3	2	4	5	7
4	4	6	2		1	3	6	2
5	4	5	1	2		4	2	3
6	3	8	9	6	4		1	5
7	1	6	6	4	2	1		0
8	7	8	7	2	8	3	0	

1. Оценим снизу величину минимальной стоимости проезда по гамильтонову циклу (дешевле, чем эта оценка, проезда мы уже не полчим). Для этого из каждой строчки матрицы А вычтем минимальный элемент этой строчки.

Затем туже операцию проделаем со столбцами. Сумма всех вычтенных чисел дает искомую оценку.

	1	2	3	4	5	6	7	8
1		3	1	0	4	3	0	5
2	6		0	5	6	7	8	5
3	1	0		1	0	2	3	5
4	3	5	1		0	2	5	1
5	3	4	0	1		3	1	2
6	2	7	8	5	3		0	4
7	1	6	6	4	2	1		0
8	7	8	7	2	8	3	0	

	1	2	3	4	5	6	7	8
1		3	1	0	4	2	0	5
2	5		0	5	6	6	8	5
3	0	0		1	0	1	3	5
4	2	5	1		0	1	5	1
5	2	4	0	1		2	1	2
6	1	7	8	5	3		0	4
7	0	6	6	4	2	0		0
8	6	8	7	2	8	2	0	

2. Множество, всех вариантов образов городов разбивает на 2 размножества. Для этого выберем одну из дуг графа (ноль матрицы А) и в качестве одного подмножества рассмотрим все пути содержащии эту дугу, а в качестве другого - все пути, не содержащие эту дугу.

Среди всех нулей матрицы выбираем тот, который имеет наибольшую оценку. Оценка нуля, находящегося на месте (i₀, j₀) вычисляется по формуле: .

Берем строчку и столбец, на пересечении которых стоит 0 и выбираем min элемент в строчке и min элемент в столбце и вычисляем их сумму. Из полученных сумм выбираем максимальную и выделяем соответствующий нулевой элемент. У нас - (2,3) имеет максимальную оценку C₂₃=5.

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

при добавлении дуг нужно исключать все дуги, приводящие к циклу, проходящему не через все вершины. Например добавляя сразу (2,3) мы должны исключить дугу (3,2) то есть место (3,2) 