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

1.

2. Домашнее задание

«Применение графа»

3. ВСПОМНИМ…

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

4. Кенигсбергские мосты

5. Кенигсбергские мосты

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

6. Представим задачу в виде графа,где вершины – острова и берега (A,B,C,D), а ребра – мосты

С
Д
А
В
Важно, является ли число мостов, ведущих к этим отдельным
участкам, четным или нечетным.
Так, в нашем случае к участку A ведут пять мостов, а к
остальным – по три моста.

7.

3
С
5
Д
А
В
3
Какие вершины четные, а какие нечетные?
Подпишем степени вершин в кружочках.
Нечетные вершины: А, B, C, D.
3

8.

Эйлеров граф
Если граф имеет цикл, содержащий все ребра
графа по одному разу (Эйлерова линия),то
такой граф называется эйлеровым
графом
Условия существования Эйлеровой линии:
-граф связный
-все вершины четные
Другими словами, эйлеров граф – это
граф,который можно нарисовать одним
росчерком

9. Алгоритм решения задач

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

10. Достроить графы до Эйлеровых

Б
А
В
А
Б
Д
Г
В
А
Б
Г
В
А
Б
Г
В

11. Задача о 15 мостах

В некоторой местности через протоки переброшено 15 мостов.
E
D
С
А
В
F

12. Построим граф, где вершины – острова и берега, а ребра – мосты.

Построим граф, где вершины – острова и берега, а
5
ребра – мосты.
E
3
D
8
С
4
4
В
А
6
F
Нечетные вершины: D, E.
ВЫВОД: Так как количество нечетных вершин = 2, то обход
возможен.
Его Начало может быть в местности D, а Конец в местности E.

13.

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