Моделирование на графах 21.11.2022
Моделирование на графах
21.11.2022
Матвеева Инга Михайловна
1
Системный подход Граф – это набор вершин и соединяющих их ребер
Системный подход
Граф – это набор вершин и соединяющих их ребер.
1
2
3
4
5
вершина
ребро
23
18
20
15
14
5
вес ребра (взвешенный граф)
ориентированный граф (орграф) –ребра имеют направление
21.11.2022
Матвеева Инга Михайловна
2
Родоначальником теории графов принято считать математика
Родоначальником теории графов принято считать математика Леонарда Эйлера(1707-1783). Он предложил изящное решение знаменитой задачи о 7 Кенигсбергских мостах в 1736 году, а также придумал общий метод решения подобных задач.
По легенде один из жителей Кенигсберга спросил у своего товарища, сможет ли он пройти во всем мостам, связывающим островки на реке Преголь и вернуться в ту же самую точку, побывав на каждом мосту ровно один раз ?
21.11.2022
Матвеева Инга Михайловна
3
Решить на практике эту задачу никто из жителей не смог
Решить на практике эту задачу никто из жителей не смог. Покорилась она лишь Эйлеру, в то время работавшему в Петербурге. Легендарный математик не только расставил все точки над i, но и разработал общий принцип решения таких задач.
Эйлер схематически изобразил структуру, которую образуют мосты и назвал её "графом". Точки на нём он назвал "вершинами", а соединяющие их линии - "ребрами".
Ключевая догадка Эйлера состояла в том, чтобы подсчитать, сколько ребер выходит из каждой вершины. На нашем рисунке:
из 1-ой - выходит три ребра;
из 2-ой - пять ребер;
из 3-ой - три ребра;
из 4-ой - три ребра.
Все четыре вершины графа оказались "нечетными".
21.11.2022
Матвеева Инга Михайловна
4
Немного поэкспериментировав, Эйлер вывел четыре основных правила для решения таких задач:
Немного поэкспериментировав, Эйлер вывел четыре основных правила для решения таких задач:
Число нечетных вершин графа всегда чётно. Невозможно начертить граф, который имел бы нечетное число нечетных вершин (можете попробовать на досуге).
2. Если у графа все вершины четные, то его можно начертить одним росчерком пера, причем неважно, где начинать.
3. Если у графа две нечетные вершины, то его можно начертить одним росчерком пера, но начинать надо в одной из нечетных вершин, а закончить в другой.
4. Граф с более чем двумя нечетными вершинами построить одним росчерком пера невозможно.
Вы уже догадались, что задача о мостах Кёнигсберга решений не имеет, ведь в ней целых четыре нечетных вершины!
21.11.2022
Матвеева Инга Михайловна
5
Одной из разновидностей графа является дерево
Одной из разновидностей графа является дерево.
Дерево — это совокупность элементов (вершин), в которой выделен один элемент (корень), а остальные элементы разбиты на непересекающиеся множества (поддеревья). Каждое поддерево является деревом, а его корень является потомком корня дерева, т. е. все элементы связаны между собой отношением «предок — потомок». В результате образуется иерархическая структура вершин.
Частным случаем дерева является бинарное дерево, в котором каждая вершина может иметь не более двух потомков.
Деревья используются для представления родственных связей (генеалогическое дерево), для определения выигрышной стратегии в играх и т. д.
Ещё одной знакомой вам структурой данных являются таблицы, состоящие из строк и граф (столбцов, колонок), пересечение которых образуют ячейки. Таблицы применяют для наглядности и удобства сравнения показателей.
Построим таблицу, соответствующую неориентированному графу, отражающему схему дорог между некоторыми населёнными пунктами.
21.11.2022
Матвеева Инга Михайловна
6
Строки и столбцы таблицы будут соответствовать вершинам графа
Строки и столбцы таблицы будут соответствовать вершинам графа. Если две
вершины являются смежными (соединены ребром), то в ячейку на пересечении
соответствующих столбца и строки будем записывать вес этого ребра.
В противном случае (вершины не являются смежными) в ячейку будем записывать 0.
Получится таблица типа «объект — объект».
Такую таблицу называют матрицей смежности. Часто в матрицах смежности вместо нуля ставят знак минус, что обеспечивает большую наглядность.
Матрица смежности неориентированного графа симметрична
относительно главной диагонали, идущей от левого верхнего угла к
правому нижнему углу. У матрицы смежности ориентированного графа
такая симметрия отсутствует.
21.11.2022
Матвеева Инга Михайловна
7
Найдём кратчайший путь от вершины
Найдём кратчайший путь от вершины А до вершины F в графе, приведённом
на рисунке 3.7.
Составим матрицу смежности,
соответствующую
данному ориентированному
графу:
По матрице смежности построим полное дерево перебора решений
Пример
На рисунке 2 видно, что кратчайший путь из вершины А в вершину F равен 17 и имеет вид A-B-E-F.
1
2
21.11.2022
Матвеева Инга Михайловна
8
Пример 3 На рисунке 3.9 представлена схема дорог, связывающих города
Пример 3 На рисунке 3.9 представлена схема дорог, связывающих города А, В, С, D, Е, F, G.
По каждой дороге можно двигаться только в одном направлении,
указанном стрелкой. Сколько разных путей существует из города А в город G?
Постройте дерево и подсчитайте число дорог из города А в город G самостоятельно.
Решение
Ответ: 7 дорог
21.11.2022
Матвеева Инга Михайловна
9
Между населёнными пунктами A, B,
Между населёнными пунктами A, B, C, D, E, F, Z построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами A и Z (при условии, что передвигаться можно только по построенным дорогам).
Выберите правильный ответ:
1) 13 2) 16 3) 19 4) 21
При решении этой задачи тоже не следует полагаться на простой визуальный анализ таблицы. Чтобы избежать ошибок, построим дерево с корнем в вершине A и листьями в вершине Z. При этом нам не нужно выписывать все ветки. Второй путь из A в С (AC=6) длиннее первого (ABC=5), значит и весь маршрут через него будет длиннее.
Второй путь из C в E (CE=10) длиннее первого (CDE=6), значит и весь маршрут через него будет длиннее.
Нам остается сложить длины всех отрезков и выбрать маршрут с наименьшей длиной.
Это верхняя ветка дерева с длиной 16.
Ответ: 2
Пример 4
21.11.2022
Матвеева Инга Михайловна
10
Пример 5 Кратчайшие пути A B C
Пример 5 Кратчайшие пути
A | B | C | D | E | |
A | 2 | 4 | 6 | ||
B | 2 | 1 | |||
C | 4 | 1 | 5 | 1 | |
D | 5 | 3 | |||
E | 6 | 1 | 3 | ||
Определите кратчайший путь между пунктами A и D.
дерево возможных маршрутов
21.11.2022
Матвеева Инга Михайловна
11
Пример 6 Количество путей Сколько существует различных путей из
Пример 6 Количество путей
Сколько существует различных путей из А в К?
Графический способ. Начнем с конца. В точку К можно попасть двумя способами: из точки Д и из точки Е. |
В точку Д можно попасть из точек Б и В. А в точку Е из точек В и Г и т.д. Ход рассуждения отображен на схематичном рисунке. |
Из рисунка видно, что у нас получилось различных 8 путей от начального пункта А до конечного пункта К. |
Ответ: 8 |
21.11.2022
Матвеева Инга Михайловна
12
Самостоятельная работа 21.11.2022
Самостоятельная работа
21.11.2022
Матвеева Инга Михайловна
13
Заполните таблицу A B C D A B C
1) Заполните таблицу
A | B | C | D | |
A | ||||
B | ||||
C | ||||
D | ||||
A | B | C | D | |
A | ||||
B | ||||
C | ||||
D | ||||
21.11.2022
Матвеева Инга Михайловна
14
A B C D E A 2 4 B 2 1 7 C 4 1 3 5
2)
A | B | C | D | E | |
A | 2 | 4 | |||
B | 2 | 1 | 7 | ||
C | 4 | 1 | 3 | 5 | |
D | 3 | 3 | |||
E | 7 | 5 | 3 | ||
Определите кратчайший путь между пунктами A и E.
21.11.2022
Матвеева Инга Михайловна
15
Количество путей Сколько существует различных путей из
3)Количество путей
Сколько существует различных путей из А в Ж?
Ж
А
Б
В
Г
Д
Е
21.11.2022
Матвеева Инга Михайловна
16
Спасибо за внимание 21.11.2022
Спасибо за внимание
21.11.2022
Матвеева Инга Михайловна
17
© ООО «Знанио»
С вами с 2009 года.
