разбор заданий первой части экзамена
Теория по заданию 9
ГРАФЫ
Задание включает в себя несколько видов:
Нужная теория по графам для задания 9 уже есть в разборе задания 4
- Поиск количества путей без усложнения
- Поиск количества путей с обязательной для прохождения точкой
- Поиск количество путей с обязательной для обхода точкой (ее нужно не пройти)
- Поиск количества путей с обязательной для прохождения точной и с обязательной для обхода одновременно (например: обязательно пройти через точку C и обойти точку E)
Алгоритм решения задания:
1. Начальную вершину ставим равной единице
2. Если в вершину входит одна стрелка, тогда переносим значение с этой стрелки с уже известной вершины.
3. Если в вершину входит несколько стрелок, тогда суммируем значения со всех этих стрелок
3. Если в вершину входит несколько стрелок, тогда суммируем значения со всех этих стрелок
4.При усложнении задания и появлении точек, которые нужно пройти или которые не надо проходить, лишние стрелки необходимо убрать из графа для корректного подсчета путей.ретья услуга
Теория ясна, приступим к практике.
Попробуйте решить 5 заданий, проверьте, на сколько хорошо вы разобрались в теме (после у вас будет возможность посмотреть правильные решения и ответы).
1.На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
Ответ:
Ответ:
2.На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город П, проходящих через город М?
Ответ:
Сколько существует различных путей из города А в город П, проходящих через город М?
Ответ:
3.На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К, не проходящих через пункт В?
Ответ:
Сколько существует различных путей из города А в город К, не проходящих через пункт В?
Ответ:
4.На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H?
Ответ:
Ответ:
5.На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
Ответ:
Ответ:
