Путь в графе. Эйлеров путь

1.

Путь в графе.
Эйлеров путь

2.

Архипелаг Натуральный состоит из 10
островов, пронумерованных натуральными
числами от 1 до 10. Между двумя островами
есть паромная связь, если сумма их номеров
делится на 4.
Как можно добраться с
острова 1 на остров 9?
Предложите все возможные
варианты.
Как можно записывать
маршрут, по которому
будем идти?

3.

Путь в графе – последовательность рёбер, по
которым можно «пройти» из одной вершины
графа в другую.
Если существует путь, который ведёт из одной
вершины в другую, то такие вершины
называются связанными.
Если в графе две любые вершины соединены
путём, то такой граф называется связным.

4.

Цепь – путь в графе, у которого вершины не
повторяются. Также цепью называется граф, у
которого вершины последовательно
соединены рёбрами.

5.

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

6.

Эйлеров путь – путь,
который проходит
через все рёбра
связного графа по
одному разу.

7.

Задача
Найдите эйлеров путь в графе.
Чтобы эйлеров путь существовал, должны выполняться два условия:
во-первых, граф должен быть связным. Во-вторых, в графе все вершины
(кроме, возможно, двух) должны быть чётной степени.

8.

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