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

1 Решение задач с помощью графов

2 Кенигсбергские мосты Можно ли обойти все Кенигсбергские мосты, проходя только один раз через каждый из этих мостов?

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

4 Алгоритм решения задач 1. Нарисовать граф, где вершины – острова и берега, а ребра – мосты. 2. Определить степень каждой вершины и подписать возле нее. 3. Посчитать количество нечетных вершин. 4. Обход возможен: a. ЕСЛИ все вершины – четные, и его можно начать с любого участка. b. ЕСЛИ 2 вершины – нечетные, но его нужно начать с одной из нечетных местностей. 5. Обход невозможен, если нечетных вершин больше Сделать ВЫВОД. 7. Указать Начало и Конец пути.

5 Задание: Достроить графы до Эйлеровых А А А Б Б Б В В В Г Г Д АБ ВГ

6 Задача о 15 мостах

7 Домашнее задание Можно ли фигуры, изображенные на рисунках, нарисовать одним росчерком? (решить с помощью графа)