Информационные модели на графах

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