Тема- Графы Поиск путей Что нужно знать- если в город R можно приехать только из городов X Y и Z то чис

Работа добавлена на сайт samzan.net:

 К. Поляков, 2009-2012

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

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

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

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

,

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

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

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

На карту нанесены 4 города (A, B, C и D). Известно, что

между городами A и С – три дороги

между городами C и B – две дороги

между городами A и B – две дороги

между городами C и D – две  дороги

между городами B и D – четыре дороги

По каждой из этих дорог можно ехать в обе стороны. Сколькими различными способами можно проехать из города А в город D, посещая каждый город не более одного раза?

Решение:

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

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

2   4	3   2	2   2   2	3   2   4
A  B  D	A  С  D	A  B  С  D	A  C  B  D

1.  теперь рассмотрим маршрут  A  B  D; сначала можно двумя путями приехать из A в B, а затем – 4-мя путями из B в D; поэтому общее количество различных маршрутов равно произведению этих чисел: 2*4 = 8
2.  аналогично находит количество различных путей по другим маршрутам

A  С  D:   3*2 = 6

A  B  С  D: 2*2*2 = 8

A  C  B  D: 3*2*4 = 24

1.  всего получается 8 + 6 + 8 + 24 = 46.
2.  Ответ: 46.

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

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

Решение (1 вариант, подстановки):

1.  начнем считать количество путей с конца маршрута – с города К
2.  будем обозначать через NX количество различных путей из города А в город X
3.  общее число путей обозначим через N
4.  по схеме видно, что NБ = NГ = 1
5.  очевидно, что если в город X можно приехать только из Y, Z, то NX = NY + NZ, то есть нужно сложить число путей, ведущих из A во все города, откуда можно приехать в город X
6.  поскольку в K можно приехать из Е, Д, Ж или И, поэтому

N = NК = NД + NЕ + NЖ + NИ

1.  в город И можно приехать только из Д, поэтому NИ = NД
2.  в город Ж можно приехать только из Е и В, поэтому

NЖ = NЕ + NВ

1.  подставляем результаты пп. 6 и 7 в формулу п. 5:

N = NВ + 2NЕ + 2NД

1.  в город Д можно приехать только из Б и В, поэтому

NД = NБ + NВ

так что

N = 2NБ + 3NВ + 2NЕ

1.  в город Е можно приехать только из Г, поэтому NЕ = NГ так что

N = 2NБ + 3NВ + 2NГ

1.  по схеме видно, что NБ = NГ = 1, кроме того, NВ = 1 + NБ + NГ = 3
2.  окончательно N = 2NБ + 3NВ + 2NГ = 2·1 + 3·3 + 2·1 = 13
3.  Ответ: 13.

Решение (2 вариант, удобная форма записи):

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

К  ИДЖЕ

И  Д

Ж  ВЕ

Е  Г

Д  БВ

Г  А

В  АБГ

Б  А

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

Б  А

Г  А

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

В  АБГ

Е  Г

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

Д  БВ

Ж  ВЕ

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

И  Д

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

К  ИДЖЕ

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

1.  теперь идем по полученному списку вершин, полагая, что количество вариантов попасть в вершину равно суммарному количеству вариантов попасть в ее непосредственных предшественников.

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

1.  заметим, что вершины можно и не сортировать специально, а просто выбирать возможный порядок вычисления: проверять, какие значения известны и какие можно рассчитать с их помощью на следующем шаге
2.  Ответ: 13.

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

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

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

Б  А

В  АБГ

Г  А

Д  БВ

Е  Г

Ж  ВЕ

И  Д

К  ИДЖЕ

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

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

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

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

1.  следующий шаг

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

1.  и последние 2 шага

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

1.  Ответ: 13.

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

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

АБ, АВ, АГ

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

АБВ, АБД

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

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

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

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

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

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

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

АВД, АВЖ

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

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

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

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

АГВ, АГЕ

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

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

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

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

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

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

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

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

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

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

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

1.  Ответ: 13.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тренировочные работы МИОО 2011-2012.

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

 11 http://kpolyakov.spb.ru

И

Ж

Д

Б

Е

Е

К

А

В

Г

К

А

В

Г

И

Ж

Д

Б

Е

К

А

В

Г

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

И

Д

Ж

З

К

Е

Г

В

Б

А

Б

И

Д

Ж

З

К

Е

Г

А

Д

Ж

З

К

Е

Г

В

В

З

Б

А

И

Д

Ж

З

Б

К

Е

Г

И

Ж

Д

Б

Е

К

А

В

Г

З

И

Ж

Д

Б

Е

К

А

В

Г

В

Б

А

И

Д

Ж

З

К

Е

Г

В

А

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

И

Д

Ж

З

К

Е

Г

В

Б

А

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

И

Д

Ж

З

К

Е

Г

В

Б

А

З

Ж

Б

Е

Д

Г

В

Б

Б

А

З

Ж

Е

Д

В

А

Г

К

И

Ж

Е

Б

З

Д

А

В

Г

И

Ж

Д

Б

Е

К

А

В

Г

Д

Ж

И

З

Г

В

А

К

Е

Б

Д

Ж

И

З

Б (1)

Г(1)

В

А

К

Е

Д

Ж

И

Б (1)

Г(1)

В (3)

А

К

Е

Д

Ж

И

Ж(3+1=4)

Б (1)

Г(1)

В (3)

А

К

Е(1)

Д (1+3=4)

И (4)

Ж(4)

Б (1)

Г(1)

В (3)

А

К(4+4+4+1=13)

Е(1)

Д (4)

И (4)

Г

В

А

И

Е

Б

Д

Ж

Г

З

В

А

И

Е

Б

Д

Ж

З

Г

В

А

И

Е

Б

Д

Ж

З

Б

Г

З

Ж

Е

Д

Г

В

А

В

А

К

Е

Б

Д

Ж

И

Г

В

А

К

Е

Б

Д

Ж

И

З

Г

В

А

К

Е

Б

Д

Ж

Г

З

В

А

К

Е

Б

Д

Ж

З

Г

В

А

К

Е

Б

Д

Ж

И

З

Г

В

А

К

Е

Б

Д

Ж

И

З

J

I

А

B

H

G

C

F

E

D

K

E

А

B

C

D

F

G

H

I

J

K

E

K

J

I

H

G

F

D

C

B

А

Д

В

А

Л

З

Б

Е

Ж

И

К

Г

А

B

D

С

3

2

4

2

2

1. Расчет процентов по кредитам и вкладам
2. Учет и анализ OСновных средств торгового предприятия на примере ООО
3. Трансгенерационный подход в семейной психотерапии
4. . Нормальная продолжительность рабочего времени относительно законодательства не может превышать 8 час
5. Понятие факторов экономического роста
6. Варіант 1 Порівняти склад та функціонування фінансової системи України та розвинутих країн- США Великобр
7. Отчет по лабораторной работе 6 Исследование микроклимата производственных помещений В
8. Лабораторная работа 3 Тема- Использование операций реляционной алгебры для формирования запросов на вы
9. Тема- Методика расследования дорожнотранспортных происшествий.
10. тематической статистики1
11. Социология молодёжи как наука 7 1
12. тематический курс лекций по патофизиологии системы Кровь и основанные на нем ситуационные задачи тестовы
13. Статья- Тихвинская икона Божией Мате
14. ПРОСПЕКТ 1997 544 с
15. практикум По дисциплине ТЕПЛОСНАБЖЕНИЕ И ВЕНТИЛЯЦИЯ N
16. тематическое изучение курса истории происходит в средней школе
17. Теория игр и статических решений
18. Реферат- Церковная музыка (XIX век)
19. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА К КУРСОВОЙ РАБОТЕ по дисциплине Валютное регулирование и валютный контроль ЮУр
20. Международные финансово-кредитные организации

Материалы собраны группой SamZan и находятся в свободном доступе