Поиск путей в графе

Поиск путей в графе. Леднева М.Ю., Мочалина О.М., Муравкина Е.А.

Задание 1

Весёлая команда учителей информатики, проходя в декабре очередное повышение квалификации, решила создать несколько интересных задач, чтобы порадовать к Новому году своих коллег и учеников. Передвигаться по схеме можно только в направлении, указанном стрелками. На созданной схеме «Кленовый листок» определите количество путей от точки А до точки Ш.

Задание 2

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

Задание 3

На схеме представлены дороги, связывающие города. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города № 1 в город № 5, проходящих через город № 8 и не проходящих через город № 2?

Задание 4

На схеме представлены дороги, связывающие города. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города № 1 в город № 12, проходящих через город № 4 и не проходящих через город № 8?

Задание 5

Весёлая команда учителей информатики, проходя в декабре очередное повышение квалификации, решила создать несколько интересных задач, чтобы порадовать к Новому году своих коллег и учеников. Передвигаться по схеме можно только в направлении, указанном стрелками. На созданной схеме «Снежинка» определите количество путей от точки А до точки Ю.

Задание 6

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

Задание 7

На схеме представлены дороги, связывающие города. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города № 1 в город № 11, проходящих через город № 4 или через город № 8, но не через оба пункта?

Задание 8

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

Задание 9

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

Задание 10

На схеме представлены дороги, связывающие города. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе № 9, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.