Моделирование на графах

Моделирование на графах

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 представлена схема дорог, связывающих города А, В, С, D, Е, F, G.
По каждой дороге можно двигаться только в одном направлении,
указанном стрелкой. Сколько разных путей существует из города А в город G?

Постройте дерево и подсчитайте число дорог из города А в город G самостоятельно.

Решение

Ответ: 7 дорог

21.11.2022

Матвеева Инга Михайловна

9

Между населёнными пунктами 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

Определите кратчайший путь между пунктами A и D.

дерево возможных маршрутов

21.11.2022

Матвеева Инга Михайловна

11

Сколько существует различных путей из А в К?

21.11.2022

Матвеева Инга Михайловна

12

Самостоятельная работа

21.11.2022

Матвеева Инга Михайловна

13

21.11.2022

Матвеева Инга Михайловна

14

Определите кратчайший путь между пунктами A и E.

21.11.2022

Матвеева Инга Михайловна

15

Сколько существует различных путей из А в Ж?

Ж

А

Б

В

Г

Д

Е

21.11.2022

Матвеева Инга Михайловна

16

21.11.2022

Матвеева Инга Михайловна

17