Эйлеров граф

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

2. Историческая справка

Швейцарский (швейцарским, немецким и российским
ученым, так как он работал в разных странах)
математик Леонард Эйлер в статье о решении
знаменитой задачи о кёнигсбергских мостах,
датированной 1736 годом, первым применил идеи теории
графов при доказательстве некоторых утверждений.
Именно он считается отцом теории графов, открывшим
понятие графа, а 1736 - год рождения теории графов.

3. Задача о Кенигсбергских мостах

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

4.

Я здесь
уже
был!
дальше

5. Задача о Кенигсбергских мостах

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

6. Одним росчерком

Граф, который можно нарисовать, не отрывая
карандаша от бумаги, называется эйлеровым.
Решая задачу О кенигсбергских мостах, Эйлер
сформулировал свойства графа:
Невозможно начертить граф с нечетным числом
нечетных вершин.
дальше

7.

Если все вершины
графа четные, то можно не
отрывая карандаш от бумаги
(«одним росчерком»), проводя
по каждому ребру только один
раз, начертить этот граф.
Движение можно начать с
любой вершины и закончить
его в той же вершине.
дальше

8. Задача №1

Дана проволока длиной 12 см. Можно ли сложить из нее каркас куба с ребром
в 1 см?
Проволоку нельзя резать.
Решение: У куба 12 рёбер по 1 см, а у нас есть ровно 12 см проволоки.
Значит, делать двойные рёбра нельзя, иначе нам не хватит проволоки.
Каркас куба можно изобразить в виде графа (см. рис.) Если бы каркас
можно было сложить из проволоки, не разрезая её, то и граф можно
было бы нарисовать, не отрывая карандаша от бумаги (рисуя рёбра в
том порядке, в котором мы делаем их из проволоки). А это невозможно
в силу предыдущей задачи: ведь у этого графа целых восемь вершин
степени 3.

9. Задача №2

Дан план квартиры: комнаты и двери. Можно ли обойти квартиру так, чтобы через
каждую дверь пройти ровно по одному разу?
Решение: Комната — вершина, двери — ребра. Тогда степени
вершин: 5, 5, 5, 4, 4. Есть еще одна вершина - наружное
пространство. Туда выходит 9 дверей - 9 ребер. Это еще одна
вершина, со степенью 9. Больше двух вершин не чётные, значит
нельзя.

10.

11. Задача №4 Какие фигуры можно нарисовать одним росчерком?

12. Задача №5

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

13. Задача №5

Почтальон Печкин разнес
почту во все дома деревни,
после чего зашел с
посылкой к дяде Федору. На
рисунке показаны все
тропинки, по которым
проходил Печкин, причем,
как оказалось, ни по одной
из них он не проходил
дважды. Каков мог быть
маршрут почтальона
Печкина? В каком доме
живет дядя Федор?
Ответ: Тропинки образуют сеть с двумя нечетными узлами — у почты и дома № 5.
Начало маршрута на почте, а конец у дома №5 — там живет дядя Федор.

14.

Спасибо за внимание!!!