К началу учебного года! Готовые материалы для учителей на каждый урок со скидкой от 30%

СДЕЛАЙТЕ СВОИ УРОКИ ЕЩЁ ЭФФЕКТИВНЕЕ, А ЖИЗНЬ СВОБОДНЕЕ

Благодаря готовым учебным материалам для работы в классе и дистанционно

Выбрать материалы

Скидки до 50 % на комплекты
только до

Готовые ключевые этапы урока всегда будут у вас под рукой

Организационный момент

Проверка знаний

Объяснение материала

Закрепление изученного

Итоги урока

Была в сети 02.07.2025 11:58

Шнарева Галина Вячеславовна

преподаватель математических дисциплин

25 284

1 095

Подписчики

Подписки

Местоположение

Россия, Крым

Специализация

Математика

Обо мне Блог Файлы Тесты Галерея Активность Награды

Практическое занятие № 7 "Нахождение путей в графе"

Категория: Математика

21.11.2015 21:39

ИНСТРУКЦИОННАЯ КАРТА

на выполнение практического занятия № 7

по МДК.01.02 Математический аппарат для построения компьютерных сетей (тема 1. Теория графов)

Тема занятия: Нахождение путей в графе.

Цель проведения занятия: получение навыков при решении задач нахождения пути в графе.

Просмотр содержимого документа
«Практическое занятие № 7 "Нахождение путей в графе"»

ИНСТРУКЦИОННАЯ КАРТА

на выполнение практического занятия № 7

по МДК.01.02 Математический аппарат для построения компьютерных сетей (тема 1. Теория графов)

Тема занятия: Нахождение путей в графе.

Цель проведения занятия: получение навыков при решении задач нахождения пути в графе.

После выполнения работы студент должен

знать: типы задач на нахождение путей в графе;

уметь: находить пути в графе.

Материально-техническое оснащение рабочего места: инструкционные карты, конспект.

Инструктаж по технике безопасности

Рекомендованная литература:

Спирина М.С., Дискретная математика: Учебник для студ. Учреждений сред. проф. образования / М.С.Спирина, П.А.Спирин. –М.: Издательский центр «Академия», 2004. –368 с.
Александров А. В. и др. Прикладные алгоритмы на графах. Учебное пособие, ВлГУ, 2005
Харари Фрэнк. Теория графов / Харари Фрэнк ; Пер. с англ. В.П.Козырева; Под ред. Г.П.Гаврилова. - 4-е изд. - М. : URSS : Либроком, 2009. - 296 с
Битюцкий В. П. Электронный учебник: Дискретная математика / http://ait.ustu.ru/uploaded/materialy-po-disciplinam/discret-mathematics/el_ucheb/index.htm
Справочные данные по математике: Элементы теории графов. [Электронный ресурс]. – Режим доступа: http://book.itep.ru/10/grap1021.htm, свободный. – Загл. с экрана.

Содержание и порядок выполнения задания

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

Решение (1 вариант, подстановки):
1) начнем считать количество путей с конца маршрута – с города К
2) будем обозначать через N_X количество различных путей из города А в город X
3) общее число путей обозначим через N
4) по схеме видно, что N_Б = N_Г = 1
5) очевидно, что если в город X можно приехать только из Y, Z, то N_X = N_Y + N_Z, то есть нужно сложить число путей, ведущих из A во все города, откуда можно приехать в город X

6) поскольку в K можно приехать из Е, Д, Ж или И, поэтому N = N_К = N_Д + N_Е + N_Ж + N_И
7) в город И можно приехать только из Д, поэтому N_И = N_Д
8) в город Ж можно приехать только из Е и В, поэтому N_Ж = N_Е + N_В
9) подставляем результаты пп. 7 и 8 в формулу п. 6: N = N_В + 2N_Е + 2N_Д
10) в город Д можно приехать только из Б и В, поэтому N_Д = N_Б + N_Втак что N = 2N_Б + 3N_В + 2N_Е
11) в город Е можно приехать только из Г, поэтому N_Е = N_Г так что N = 2N_Б + 3N_В + 2N_Г
12) по схеме видно, что N_Б = N_Г = 1, кроме того, N_В = 1 + N_Б + N_Г = 3
13) окончательно N = 2N_Б + 3N_В + 2N_Г = 2·1 + 3·3 + 2·1 = 13 14) Ответ: 13.

Решение (2 вариант, удобная форма записи):
1) начнем считать количество путей с конца маршрута – с города К
2) записываем для каждой вершины из каких вершин можно в нее попасть

3) теперь для удобства «обратного хода» вершины можно отсортировать так, чтобы сначала шли все вершины, в которые можно доехать только из начальной точки А:

Б ← А Г ← А
затем на каждом шаге добавляем те вершины, в которые можно доехать из уже добавленных в список (и из исходной точки):
В ← АБГ Е ← Г
далее добавляем все вершины, куда можно доехать из А, Б, Г, В и Е:
Д ← БВ Ж ← ВЕ
на следующем шаге добавляем вершину И: И ←Д
и, наконец, конечную вершину К ←ИДЖЕ именно в таком порядке будем вычислять количество путей для каждой вершины. Такая процедура называется топологической сортировкой графа.
4) теперь идем по полученному списку вершин, полагая, что количество вариантов попасть в вершину равно суммарному количеству вариантов попасть в ее непосредственных предшественников.
N_Б = 1, N_Г = 1 N_В = 1+1+1 = 3, N_Е = 1 N_Д = 1+3 = 4, N_Ж = 3 + 1 = 4 N_И = 4, N = N_К = 4 + 4 + 4 + 1 = 13
5) заметим, что вершины можно и не сортировать специально, а просто выбирать возможный порядок вычисления: проверять, какие значения известны и какие можно рассчитать с их помощью на следующем шаге. 6) Ответ: 13.

Замечания: очень важна аккуратность и последовательность; сначала идем от конечной точки к начальной, выписывая все вершины, из которых можно приехать в данную; затем идем обратно, определяя числовые значения построение полного дерева маршрутов.

Задани2 ( по вариантам).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17. На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H?

18. На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город M?

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

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

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

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

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

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

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

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

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

28. На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город E?

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

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

Вопросы для самоконтроля:

Перечислите типы задач на поиск путей в графе.
Какие существуют два вида алгоритма поиска путей в графе?
В чем заключается идея алгоритма поиска пути «в глубину»?
В чем заключается идея алгоритма поиска пути «в ширину»?
В чем заключается идея алгоритма поиска пути в данной практической работе?

Краткие сведения по теоретической части работы

В основе построения большинства алгоритмов на графах лежит систематический перебор вершин графа, при котором каждая вершина просматривается в точности один раз, а количество просмотров ребер графа ограничено заданной константой (лучше – не более одного раза). Один из основных методов проектирования графовых алгоритмов – это поиск (или обход графа) в глубину (depth first search, DFS), при котором начиная с произвольной вершины v₀, ищется ближайшая смежная вершина v, для которой в свою очередь осуществляется поиск в глубину (т.е. снова ищется ближайшая, смежная с ней вершина) до тех пор, пока не встретится ранее просмотренная вершина, или не закончится список смежности вершины v (то есть вершина полностью обработана). Если нет новых вершин, смежных с v, то вершина v считается использованной, идет возврат в вершину, из которой попали в вершину v, и процесс продолжается до тех пор, пока не получим v = v₀. Иными словами, поиск в глубину из вершины v основан на поиске в глубину из всех новых вершин, смежных с вершиной v. В алгоритме поиска в ширину (breadth first search, BFS). Обработка вершины v осуществляется путем просмотра сразу всех новых соседей этой вершины. При этом полученный путь является кратчайшим путем из одной вершины в другую. Методические рекомендации по выполнению и оформлению

Порядок выполнения работы:

1. Изучить инструкцию к практической работе.

2. Выполнить задание.

3. Оформить отчет.

Содержание отчета о занятии:

1. Тема.

2. Цель.

4. Практическое задание.

5. Ответ на 1 контрольный вопрос (по указанию преподавателя).

Инструкционная карта составлена преподавателем: Шнарева Г.В.