Решение задач по теме "Графы. Поиск количества путей"

Умение представлять и считывать данные в разных типах информационных моделей (схемы, карты, таблицы, графики и формулы)

Содержимое разработки

Информационные модели   Графы. Поиск количества путей  Учитель информатики МОБУ «Сенькинская средняя общеобразовательная школа» Скворцова Ольга Валерьевна

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

Графы. Поиск количества путей

Учитель информатики

МОБУ «Сенькинская средняя общеобразовательная школа»

Скворцова Ольга Валерьевна

13-е задание: «Информационные модели»  Уровень сложности — повышенный,  Требуется использование специализированного программного обеспечения — нет,  Максимальный балл — 1,  Примерное время выполнения
  • 13-е задание: «Информационные модели» Уровень сложности — повышенный, Требуется использование специализированного программного обеспечения — нет, Максимальный балл — 1, Примерное время выполнения — 3 минуты.    Проверяемые элементы содержания: Умение представлять и считывать данные в разных типах информационных моделей (схемы, карты, таблицы, графики и формулы)
Если в город R из города A можно добраться только из городов X, Y и Z, то количество различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть: N R = N X + N Y + N Z  где N R — это количество путей из вершины A в вершину R Число путей не бесконечно, исключением является только граф, в котором есть циклы – замкнутые пути. Часто задачи с графами целесообразней решать с конца.
  • Если в город R из города A можно добраться только из городов X, Y и Z, то количество различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть:

N R = N X + N Y + N Z

где N R — это количество путей из вершины A в вершину R

  • Число путей не бесконечно, исключением является только граф, в котором есть циклы – замкнутые пути.
  • Часто задачи с графами целесообразней решать с конца.
Типичные ошибки

Типичные ошибки

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

Подсчёт путей с избегаемой вершиной

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

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

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

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

Подсчёт путей с обязательной и избегаемой вершинами

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

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

Подсчет путей

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

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

Подсчёт путей с обязательной вершиной

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

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

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

Демо 2021

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

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

Пробный 2021

Наибольшая длинна 8. На рисунке - схема дорог, связывающих города А, Б, В, Г, Е, Ж, К, Л, М. По каждой дороге можно двигаться в одном направлении, указанном стрелкой. Какая наибольшая длина пути из А в М ? 2020

Наибольшая длинна

  • 8. На рисунке - схема дорог, связывающих города А, Б, В, Г, Е, Ж, К, Л, М. По каждой дороге можно двигаться в одном направлении, указанном стрелкой. Какая наибольшая длина пути из А в М ?

2020

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

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

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

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

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

Сохранить у себя:
Решение задач по теме "Графы. Поиск количества путей"

Получите свидетельство о публикации сразу после загрузки работы



Получите бесплатно свидетельство о публикации сразу после добавления разработки