Similar presentations:
Информационные модели на графах
1.
Информационные модели на графах2.
Что такое граф?Граф это множество точек или вершин
и множество линий или ребер,
соединяющих между собой все или
часть этих точек. Граф является
информационной моделью некоторого
объекта или системы объектов.
3.
Какие виды графов вам известны ?ГРАФЫ
ориентированные неориентированные
дуги
рёбр
а
4.
Что такое взвешенный граф ?Взвешенный граф — граф, каждому
ребру или вершине которого
поставлено в соответствие некое
значение (вес).
5.
Тема урока: Пути в графах6.
В таблице представлено расстояние междунаселенными пунктами. Определить кратчайшее
расстояние между пунктами A и E.
A
A
B
C
D
E
2
10
8
16
9
1
B
2
C
10
9
D
8
1
E
16
3
3
4
4
11
11
7.
Как преобразоватьинформацию,
представленную в
табличной форме в граф
Как определить все пути в
графе
Определить кратчайший
путь
Цели
…
8.
Еще раз проанализируем таблицу.Такую таблицу называют весовой матрицей.
Какие особенности в таблице вы заметили?
A
B C D E
A
2 10 8 16
B 2
9 1
C 10 9
3 4
D 8 1 3
11
E 16
4 11
9.
Части таблицы, разделённыедиагональю – симметричны, т.е.
содержат одни и те же данные.
Следовательно, можно
рассматривать данные любой
половины таблицы, разделенной
диагональю.
10.
Теперь приступим к построению графаA
A
B
C
D
E
2
10
8
16
9
1
B
2
C
10
9
D
8
1
E
16
3
3
4
4
11
11
11.
Проверим правильность построенияA
A
B
C
D
E
2
10
8
16
9
1
B
2
C
10
9
D
8
1
E
16
3
3
4
2
A
10
4
11
11
B
9
8
16
1
D
3
C
4
E
11
12.
Определим все пути в графе и расстояние,пройденное на этом пути (вес-расстояние в км.)
Будем делать обход по
графу в алфавитном
порядке, т.е. сначала
все пути через АВ, АС,
AD
и т.д. – 25 км
1.ABCDE
2.ABCE – 15 км
3.ABDCE – 10 км
4.ACBDE – 31 км
5.ACDE – 24 км
6.ACE – 14 км
7.ADCE – 15 км
8.ADE – 19 км
9.AE – 16 км
2
A
B
9
8
10
16
1
D
3
C
4
E
11
13.
Кратчайший путь в данном графе :ABDCE – 10 км
A
A
B
C
D
E
2
10
8
16
9
1
B
2
C
10
9
D
8
1
E
16
3
3
4
2
A
10
4
11
11
B
9
8
16
1
D
3
C
4
E
11
14.
Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строки столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями.
Если пересечение строки и столбца пусто, то станции не являются соседними.
Укажите таблицу, для которой выполняется условие: “Минимальная стоимость проезда
из А в B не больше 6”.
Стоимость проезда по маршруту складывается из стоимостей проезда между
соответствующими соседними станциями.
2)
1)
A
B C
A
3
B
4
C
3
D
1
Е
C
D
Е
A
3
1
1
2
B
4
2
C
3
D
1
Е
1
D Е
A
1
4
2
2
A
B
2
2
1
D
4
C
B
4
E
C
D Е
A
3
1
B
4
C
3
D
1
Е
2
1
2
D
4
1
1 2
B
C
A
1
B
2
C
4
4
1
1
4
2
4
1
2
A
B
B
1
1
4
C
D Е
1
Е
2
3
E
A
D
1
3
4
C
B
A
B
1
4)
A
2
A
3
E
3)
E
4
C
2
4
D
D
AC C B - 7
AC C B - 7
AC C B - 7
AD DC CB - 9
AC CE EB - 7
AE EC CB - 7
AC CE EB - 6
AD DC CE EB - 8
15.
Поиск количества путей1
2
3
5
4
7
8
6
9
На рисунке изображена
схема местности.
Передвигаться из пункта в
пункт можно только в
направлении стрелок. В
каждом пункте можно
бывать не более одного
раза. Сколькими
способами можно попасть
из пункта 1 в пункт 9? У
какого из путей
наименьшая длина? У
какого наибольшая длина?
16.
1Решение задачи
2
3
5
4
6
1
5
4
5
7
9
7
8
8
9
8
9
7
7
2
9
8
9
9
5
8
97
8
1
ярус
3
9
8
9
Кратчайший путь: 1 5 9. Его длинна 2.
8
2
ярус
6
9
9
8
9
3
ярус
5
9
7
Длина наиболее продолжительного пути 7: 1 2 3 6 5 7 8 9.
Число путей 14
9
8
9
4
ярус
5
ярус
6
7ярус
ярус
17.
Задача 1На рисунке — схема дорог, связывающих города
А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно
двигаться только в одном направлении, указанном
стрелкой. Сколько существует различных путей из
пункта А в пункт К, не проходящих через пункт В?
18.
Решение:А
Д
Ж
Г
Е
И
К
К
К
И
К
К
Ответ: 5 путей
19.
Задача 2На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К.
По каждой дороге можно двигаться только в одном направлении,
указанном стрелкой. Сколько существует различных путей из
города А в город К?
20.
Решение задачиНачнем с конца. В точку К можно попасть двумя способами: из точки Д и
из точки Е.
В точку Д можно попасть из точек Б и В. А в точку Е из точек В и Г и т.д.
Ход рассуждения отображен на схематичном рисунке.
Из рисунка видно, что у нас получилось различных 8 путей от начального
пункта А до конечного пункта К.
Ответ: 8
21.
Самостоятельная работа22.
Вариант 2Вариант 1
Постройте граф и определите
длину кратчайшего пути между
пунктом A и F. Передвигаться
можно только по дороге,
протяженность
которых
указана в таблицы
A
A
B
2
C
5
D
B
C
2
5
2
2
E
F
7
1
5
1
1
E
F
D
1
7
5
2
2
Постройте граф и определите
длину кратчайшего пути между
пунктом A и E. Передвигаться
можно только по дороге,
протяженность
которых
указана в таблицы
A
A
B
4
C
1
D
E
B
C
4
1
2
2
3
D
3
2
2
2
E
2
3
3
23.
Вариант 1На рисунке — схема дорог, связывающих города А, Б, В, Г, Д,
Е, Ж, И, К, Л. По каждой дороге можно двигаться только в
одном направлении, указанном стрелкой. Сколько
существует различных путей из пункта А в пункт Л,
проходящих через пункт Е? Постройте дерево.
Вариант 2
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д,
Е, Ж, И, К. По каждой дороге можно двигаться только в
одном направлении, указанном стрелкой. Сколько
существует различных путей из города А в город К, не
проходящих через пункт В? Постройте дерево.
24.
Вариант 1Вариант 2