Главная | Обратная связь | Поможем написать вашу работу!

повышенный уровень, время – 3 мин)

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

Что нужно знать:

· если в город R можно приехать только из городов X, Y, и Z, то число различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть

где обозначает число путей из вершины A в некоторую вершину Q

· число путей конечно, если в графе нет циклов – замкнутых путей

Пример задания:

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

Решение:

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

2) проведём сечение графа через вершину В:

3) обратим внимание на такой факт: если мы перешли через линию сечения из левой части в правую по ребру ГЕ или через вершину Ж, мы уже никак не попадём в вершину В (нет рёбер с «обратным направлением», поэтому эти маршруты запрещены; для более сложных случаев, когда такие рёбра с «обратным направлением» есть, нужно перерисовать граф (или провести сечение иначе) так, чтобы все вершины, ИЗ которых можно попасть в В, оказались слева от линии сечения

4) в данном случае выбрасывается вершина Ж, все связанные с ней рёбра, и ребро ГЕ:

5) дальше используем стандартный метод (см. разбор следующей задачи)

6) покажем только окончательный результат:

7) Ответ: 16.

Ещё пример задания:

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

Решение:

1) будем обозначать через N_X количество различных путей из города А в город X

2) для города А есть только один маршрут – никуда не двигаться, поэтому N_A = 1

3) для любого города X количество маршрутов N_X можно вычислить как

N_x = N_y + … + N_z

где сумма взята по всем вершинам, из которых есть прямой путь в вершину X; например,

N_Л = N_И + N_Ж + N_К

4) около каждого города будем записывать количество маршрутов из А в этот город

5) начнем считать количество путей с начала маршрута – с города А:

6) теперь находим те вершины, в которые можно попасть напрямую из уже рассмотренных вершин (пока – только из А), это Б и Г, для них тоже количество путей равно 1:

7) теперь можно определить количество путей для В и Е; в В можно приехать только из А, Б и Г, а в Е – только из Г:

N_В = N_А + N_Б + N_Г = 1 + 1 + 1 = 3

N_Е = N_Г = 1

8) теперь можно определить количество путей для Д, Ж и К; в Д можно приехать только из Б и В, в Ж – из В и Е, а в Е – только из Г:

N_Д = N_Б + N_В = 1 + 3 = 4

N_Ж = N_В + N_Е = 3 + 1 = 4

N_К = N_Е= 1

9) теперь можно определить количество путей для И, куда можно приехать только из Д (N_И = N_Д) и, наконец, для Л:

N_Л = N_Д + N_И + N_Ж + N_К = 13

10) Ответ: 13.

Ещё пример задания:

Р-01. Города A, B, C и D связаны дорогами. Известно, что существуют дороги между городами

A и С, C и B (две дороги), A и B, C и D (две дороги), B и D. Сколькими различными способами можно проехать из города А в город D, не заезжая дважды в один город?

Решение:

1) нарисуем граф, в котором множественные дороги из одного города в другой будем обозначать одной дугой и подписывать около неё количество дорог:

2) выпишем все маршруты, по которым можно ехать из A в D так, чтобы дважды не проезжать один и тот же город:

1 1	1 2	1 2 2	1 2 1
A ® B ® D	A ® С ® D	A ® B ® С ® D	A ® C ® B ® D

3) теперь рассмотрим маршрут A ® B ® D; на всех участках только одна дорога, поэтому есть только один такой маршрут

4) для маршрута A ® С ® D: на первом участке только одна дорога, на втором – две, общее число маршрутов равно произведению этих чисел: 1*2 = 2

5) аналогично находит количество различных путей по другим маршрутам

A ® B ® С ® D: 1*2*2 = 4

A ® C ® B ® D: 1*2*1 = 2

6) всего получается 1 + 2 + 4 + 2 = 9.

7) Ответ: 9.

Еще пример задания:

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

Решение (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) подставляем результаты пп. 6 и 7 в формулу п. 5:

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) теперь для удобства «обратного хода» вершины можно отсортировать так[1], чтобы сначала шли все вершины, в которые можно доехать только из начальной точки А:

Б А

Г А

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

В АБГ

Е Г

далее добавляем все вершины, куда можно доехать из А, Б, Г, В и Е:

Д БВ

Ж ВЕ

на следующем шаге добавляем вершину И

И Д

и, наконец, конечную. вершину

К ИДЖЕ

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

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.

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

Решение (3 вариант, перебор вершин по алфавиту):

1) Запишем вершины в алфавитном порядке и для каждой из них определим, из каких вершин можно в нее попасть

Б А

В АБГ

Г А

Д БВ

Е Г

Ж ВЕ

И Д

К ИДЖЕ

2) теперь определяем количество путей; сначала ставим 1 для тех вершин, в которые можно проехать только из начальной (А):

вершина	откуда?	N
Б	А
В	АБГ
Г	А
Д	БВ
Е	Г
Ж	ВЕ
И	Д
К	ИДЖЕ

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

вершина	откуда?	N
Б	А
В	АБГ
Г	А
Д	БВ
Е	Г
Ж	ВЕ
И	Д
К	ИДЖЕ

4) следующий шаг

вершина	откуда?	N
Б	А
В	АБГ
Г	А
Д	БВ
Е	Г
Ж	ВЕ
И	Д
К	ИДЖЕ

5) и последние 2 шага

вершина	откуда?	N
Б	А
В	АБГ
Г	А
Д	БВ
Е	Г
Ж	ВЕ
И	Д
К	ИДЖЕ

6) Ответ: 13.

Решение (4 вариант, перебор всех путей с начала, А. Яфарова):

1) запишем все вершины, в которые есть прямой путь из вершины A: Б, В и Г; получается три начальных отрезка:

АБ, АВ, АГ

2) рассмотрим маршрут АБ: из Б можно ехать в В и Д, поэтому получаем два маршрута:

АБ В, АБ Д

3) рассматриваем конечные точки этих маршрутов: из В можно ехать в Д и Ж, а из Д – в И и К:

АБВ Д, АБВ Ж, АБД И, АБД К

4) снова смотрим на конечные точки: из Д едем в И и К, из Ж и И – только в К:

АБВД И, АБВД К, АБВЖ К, АБДИ К, АБДК

5) из И едем только в К, таким образом, все возможные маршруты, содержащие участок АБ, доведены до конечной точки К, всего 5 таких маршрутов:

АБВДИ К, АБВДК, АБВЖК, АБДИК, АБДК

6) затем аналогично рассматриваем маршруты, которые начинаются с АВ:

АВД, АВЖ

АВДИ, АВДК, АВЖК

АВДИК, АВДК, АВЖК

всего 3 маршрута

7) наконец, остается рассмотреть маршруты, которые начинаются с АГ:

АГВ, АГЕ

АГВД, АГВЖ, АГЕЖ, АГЕК

АГВДИ, АГВДК, АГВЖК, АГЕЖК, АГЕК

АГВДИК, АГВДК, АГВЖК, АГЕЖК, АГЕК

всего 5 маршрутов

8) складываем количество маршрутов для всех начальных участков: 5 + 3 + 5 = 13

9) Ответ: 13.

Возможные проблемы: · при большом количестве маршрутов легко запутаться и что-то пропустить

Решение (5 вариант, графический, О.О. Грущак, КузГПА):

1) Главную идею решения: (число дорог в город N есть сумма дорог, приводящих в города, из которых есть прямой проезд в город N), отразим на самой схеме, показывая на ней ЧИСЛО ДОРОГ, приводящих в каждый город.

2) Последовательность очевидна: начинаем с Б и Г (городов, куда есть по 1-й дороге из А)

3) Посчитаем дороги в В: 1 (из A)+ 1(дороги города Б)+ 1(дороги города В)= 3

4) Аналогично посчитаем дороги в Д, И, Е, Ж:

5) Определяем число дорог в город К, как сумму дорог в города, с которыми он связан: Д, И, Ж, Е.

6) Ответ: 13.

Задачи для тренировки [2]:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

E

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

(http://ege.yandex.ru) На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G, H, I, J, K. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город K?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ф

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[1] Такая процедура называется топологической сортировкой графа.

[2] Источники заданий:

1. Демонстрационные варианты ЕГЭ 2011-2016.

2. Тренировочные работы МИОО и СтатГрад 2011-2013.

3. Крылов С.С., Ушаков Д.М. ЕГЭ 2015. Информатика. Тематические тестовые задания. — М.: Экзамен, 2015.

4. Ушаков Д.М. ЕГЭ-2015. Информатика. 20 типовых вариантов экзаменационных работ для подготовки к ЕГЭ. — М.: Астрель, 2014.

5. Авторские разработки.

Воспользуйтесь поиском по сайту: