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

Август 24, 2022

Главная
Математика
Информационные модели на графах

Содержание

2. Что такое граф? Граф это множество точек или вершин и множество линий или ребер, соединяющих между
3. Какие виды графов вам известны ? ГРАФЫ ориентированные неориентированные дуги рёбра
4. Что такое взвешенный граф ? Взвешенный граф — граф, каждому ребру или вершине которого поставлено в
5. Тема урока: Пути в графах
6. В таблице представлено расстояние между населенными пунктами. Определить кратчайшее расстояние между пунктами A и E.
7. Цели… Как преобразовать информацию, представленную в табличной форме в граф Как определить все пути в графе
8. Еще раз проанализируем таблицу. Такую таблицу называют весовой матрицей. Какие особенности в таблице вы заметили?
9. Части таблицы, разделённые диагональю – симметричны, т.е. содержат одни и те же данные. Следовательно, можно рассматривать
10. Теперь приступим к построению графа
11. Проверим правильность построения A B C E D 2 9 8 10 16 11 3 1
12. Определим все пути в графе и расстояние, пройденное на этом пути (вес-расстояние в км.) A B
13. Кратчайший путь в данном графе : ABDCE – 10 км A B C E D 2
14. Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость
15. Поиск количества путей На рисунке изображена схема местности. Передвигаться из пункта в пункт можно только в
16. Решение задачи Кратчайший путь: 1 5 9. Его длинна 2. Длина наиболее продолжительного пути 7: 1
17. Задача 1 На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж,
18. Решение: А Ответ: 5 путей
19. Задача 2 На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К.
20. Решение задачи Начнем с конца. В точку К можно попасть двумя способами: из точки Д и
21. Самостоятельная работа
22. Вариант 1 Постройте граф и определите длину кратчайшего пути между пунктом A и F. Передвигаться можно
23. Вариант 1 На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж,
25. Скачать презентацию

Слайд 2

Что такое граф?
Граф это множество точек или вершин и множество линий

или ребер, соединяющих между собой все или часть этих точек. Граф является информационной моделью некоторого объекта или системы объектов.

Слайд 3

Какие виды графов вам известны ?
ГРАФЫ
ориентированные
неориентированные
дуги
рёбра

Слайд 4

Что такое взвешенный граф ?
Взвешенный граф — граф, каждому ребру или

вершине которого поставлено в соответствие некое значение (вес).

Слайд 5

Тема урока: Пути в графах

Слайд 6

В таблице представлено расстояние между населенными пунктами. Определить кратчайшее расстояние между

пунктами A и E.

Слайд 7

Цели…
Как преобразовать информацию, представленную в табличной форме в граф
Как определить все

пути в графе
Определить кратчайший путь

Слайд 8

Еще раз проанализируем таблицу. Такую таблицу называют весовой матрицей. Какие особенности

в таблице вы заметили?

Слайд 9

Части таблицы, разделённые диагональю – симметричны, т.е. содержат одни и те

же данные. Следовательно, можно рассматривать данные любой половины таблицы, разделенной диагональю.

Слайд 10

Теперь приступим к построению графа

Слайд 11

Проверим правильность построения
A
B
C
E
D
2
9
8
10
16
11
3
1
4

Слайд 12

Определим все пути в графе и расстояние, пройденное на этом пути

(вес-расстояние в км.)

Будем делать обход по графу в алфавитном порядке, т.е. сначала все пути через АВ, АС, AD и т.д.

1.ABCDE – 25 км

2.ABCE – 15 км

3.ABDCE – 10 км

4.ACBDE – 31 км

5.ACDE – 24 км

6.ACE – 14 км

7.ADCE – 15 км

8.ADE – 19 км

9.AE – 16 км

Слайд 13

Кратчайший путь в данном графе : ABDCE – 10 км
A
B
C
E
D
2
9
8
10
16
11
3
1
4

Слайд 14

Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк

и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними.
Укажите таблицу, для которой выполняется условие: “Минимальная стоимость проезда
из А в B не больше 6”.
Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.

AC C B - 7
AC CE EB - 7

AC C B - 7
AE EC CB - 7

AC C B - 7
AC CE EB - 6

AD DC CB - 9
AD DC CE EB - 8

Слайд 15

Поиск количества путей
На рисунке изображена схема местности. Передвигаться из пункта в

пункт можно только в направлении стрелок. В каждом пункте можно бывать не более одного раза. Сколькими способами можно попасть из пункта 1 в пункт 9? У какого из путей наименьшая длина? У какого наибольшая длина?

Слайд 16

Решение задачи
Кратчайший путь: 1 5 9. Его длинна 2.
Длина наиболее продолжительного

пути 7: 1 2 3 6 5 7 8 9.
Число путей 14

Слайд 17

Задача 1
На рисунке — схема дорог, связывающих города А, Б, В,

Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт К, не проходящих через пункт В?

Слайд 18

Решение: А
Ответ: 5 путей

Слайд 19

Задача 2
На рисунке – схема дорог, связывающих города А, Б, В,

Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Слайд 20

Решение задачи
Начнем с конца. В точку К можно попасть двумя способами:

из точки Д и из точки Е.
В точку Д можно попасть из точек Б и В. А в точку Е из точек В и Г и т.д. Ход рассуждения отображен на схематичном рисунке.
Из рисунка видно, что у нас получилось различных 8 путей от начального пункта А до конечного пункта К.
Ответ: 8

Слайд 21

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

Слайд 22

Вариант 1
Постройте граф и определите длину кратчайшего пути между пунктом A

и F. Передвигаться можно только по дороге, протяженность которых указана в таблицы

Вариант 2
Постройте граф и определите длину кратчайшего пути между пунктом A и E. Передвигаться можно только по дороге, протяженность которых указана в таблицы

Слайд 23

Вариант 1
На рисунке — схема дорог, связывающих города А, Б, В,

Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт Л, проходящих через пункт Е? Постройте дерево.

Вариант 2
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, не проходящих через пункт В? Постройте дерево.