Неориентированный граф Задачи на кратчайшее расстояние

Графы
I. два варианта значения слова “граф”:
1) удобная форма описания структур типа дорожной сети или сети передачи данных;
2) математический объект G := (V, E), где V — это непустое множество вершин, а E — множество ребер (пар вершин).
Для описания графа часто используют квадратную таблицу, которая описывает все возможные связи между узлами (без учета дублирования).
Если, например, на пересечении строки A и столбца B записано число 1, это означает, что есть ребро, соединяющее вершины A и B; число 0 в этой ячейке означает, что такого ребра нет. Такую таблицу называют матрицей смежности.

А2 и А13 на графы
Единица на главной диагонали (выделенной зеленым цветом) показывает, что в графе есть петля —ребро, которое начинается и заканчивается в одной
и той же вершине.
Неориентированный граф — ребра не имеют направления и каждое из них учтено в матрице смежности дважды.
“Длину” связей между вершинами называют “весом”.
Весовая матрица

А2 и А13 на графы

Задача на «кратчайшее расстояние»
ДЕМО 2013

Способ 1. Построение графа.
А2. Задача на «кратчайшее расстояние»
способы решения
1. Анализ весовой матрицы и количества ребер.
AB=3, BC=7, BD=4, BE=7, CE=5, DE=2, EF=3
2. Построение графа.
3. Перебор путей из A в F.
ABCEF=3+7+5+3=18
ABDEF=3+4+2+3=12
ABEF=3+7+3=13
(лексикографический порядок)

Способ 2. Построение дерева возможных путей
А2. Задача на «кратчайшее расстояние»
способы решения
1. Определение вершины.
2. Построение графа.
3. Ответ ABDEF=12
E,2

А2. Задача на «кратчайшее расстояние»
способы решения
Способ 3. Перебор возможных путей без построения дерева
1. Все ребра от вершины A.
AB=3
2. Все ребра из B (3 ребра).
ABC=3+7=10
ABD=3+4=7
ABE=3+7=10
3. Все ребра из вершин С, D, E (3 ребра).
ABCD=10+2=12
ABDE=7+2=9
ABEF=10+3=13 – цель достигнута
4. Все ребра из вершин D,E (4 ребра).
ABCDE=12+2=14
ABDEF=9+3=12 – цель достигнута
5. Ребра из вершины E (5 ребер)
ABCDEF=14+3=17 – цель д-а
Можно было не рассматривать,
см. п.4. очевидно.

А2. Задача на «кратчайшее расстояние»
способы решения
Способ 4. Использование алгоритма Дейкстры.
Описание в статье К.Полякова на сайте
http://kpolyakov.narod.ru/download/inf-2012-03b.pdf

Способ 1.
Построение графа.
Демо 2015, №5. Задача на «кратчайшее расстояние»
Анализ весовой матрицы
и количества ребер.
AB=5, АD=12, AG=25,
BD=8,
CD=2, CE=4, CF=5, CG=10,
EG=5,
FG=5
2. Построение графа.
3. Перебор путей

Способ 1. Построение графа.
Демо 2015, №5. Задача на «кратчайшее расстояние»
1. Анализ весовой матрицы и количества ребер.
AB=5, АD=12, AG=25,
BD=8,
CD=2, CE=4, CF=5, CG=10,
EG=5,
FG=5
3. Перебор путей:
3.1
ABD=5+8=13
AD=12
AG=25
3.2
DCEG=2+4+5=11
DCG=2+10=12
DCFG=2+5+5=12
2. Построение графа.
3.3
AD+DCEG=12+11=23
ADCEG

Способ 2.
Построение дерева
Возможных путей
Демо 2015, №5. Задача на «кратчайшее расстояние»
1. Определение вершины
2. Построение графа.
3. Перебор путей:
AD12C2E4G5=12+2+4+5=23
AD12C2F5G5=12+2+5+5=24
AD12C2G10=12+2+10=24
AG25=25

Задача на «кратчайшее расстояние»
тренировочные задачи

Задача на «кратчайшее расстояние»

Задача на «кратчайшее расстояние»
тренировочные задачи