Тема- Графы Поиск путей Что нужно знать- если в город R можно приехать только из городов X Y и Z то чис
Работа добавлена на сайт samzan.net: 2015-07-10
Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
К. Поляков, 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, посещая каждый город не более одного раза?
Решение:
- нарисуем граф, в котором множественные дороги из одного города в другой будем обозначать одной дугой и подписывать около неё количество дорог:
- выпишем все маршруты, по которым можно ехать из A в D так, чтобы дважды не проезжать один и тот же город:
2 4
|
3 2
|
2 2 2
|
3 2 4
|
A B D
|
A С D
|
A B С D
|
A C B D
|
- теперь рассмотрим маршрут A B D; сначала можно двумя путями приехать из A в B, а затем – 4-мя путями из B в D; поэтому общее количество различных маршрутов равно произведению этих чисел: 2*4 = 8
- аналогично находит количество различных путей по другим маршрутам
A С D: 3*2 = 6
A B С D: 2*2*2 = 8
A C B D: 3*2*4 = 24
- всего получается 8 + 6 + 8 + 24 = 46.
- Ответ: 46.
Пример задания:
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Решение (1 вариант, подстановки):
- начнем считать количество путей с конца маршрута – с города К
- будем обозначать через NX количество различных путей из города А в город X
- общее число путей обозначим через N
- по схеме видно, что NБ = NГ = 1
- очевидно, что если в город X можно приехать только из Y, Z, то NX = NY + NZ, то есть нужно сложить число путей, ведущих из A во все города, откуда можно приехать в город X
- поскольку в K можно приехать из Е, Д, Ж или И, поэтому
N = NК = NД + NЕ + NЖ + NИ
- в город И можно приехать только из Д, поэтому NИ = NД
- в город Ж можно приехать только из Е и В, поэтому
NЖ = NЕ + NВ
- подставляем результаты пп. 6 и 7 в формулу п. 5:
N = NВ + 2NЕ + 2NД
- в город Д можно приехать только из Б и В, поэтому
NД = NБ + NВ
так что
N = 2NБ + 3NВ + 2NЕ
- в город Е можно приехать только из Г, поэтому NЕ = NГ так что
N = 2NБ + 3NВ + 2NГ
- по схеме видно, что NБ = NГ = 1, кроме того, NВ = 1 + NБ + NГ = 3
- окончательно N = 2NБ + 3NВ + 2NГ = 2·1 + 3·3 + 2·1 = 13
- Ответ: 13.
Решение (2 вариант, удобная форма записи):
- начнем считать количество путей с конца маршрута – с города К
- записываем для каждой вершины, из каких вершин можно в нее попасть
К ИДЖЕ
И Д
Ж ВЕ
Е Г
Д БВ
Г А
В АБГ
Б А
- теперь для удобства «обратного хода» вершины можно отсортировать так, чтобы сначала шли все вершины, в которые можно доехать только из начальной точки А:
Б А
Г А
затем на каждом шаге добавляем те вершины, в которые можно доехать из уже добавленных в список (и из исходной точки):
В АБГ
Е Г
далее добавляем все вершины, куда можно доехать из А, Б, Г, В и Е:
Д БВ
Ж ВЕ
на следующем шаге добавляем вершину И
И Д
и, наконец, конечную. вершину
К ИДЖЕ
именно в таком порядке мы и будем вычислять количество путей для каждой вершины
- теперь идем по полученному списку вершин, полагая, что количество вариантов попасть в вершину равно суммарному количеству вариантов попасть в ее непосредственных предшественников.
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
- заметим, что вершины можно и не сортировать специально, а просто выбирать возможный порядок вычисления: проверять, какие значения известны и какие можно рассчитать с их помощью на следующем шаге
- Ответ: 13.
Возможные ловушки и проблемы:
- очень важна аккуратность и последовательность; сначала идем от конечной точки к начальной, выписывая все вершины, из которых можно приехать в данную; затем идем обратно, определяя числовые значения
- построение полного дерева маршрутов – занятие трудоемкое и достаточно бесперспективное, даже грамотные учителя информатики здесь в большинстве случаев что-то забывают и ошибаются
|
Решение (3 вариант, перебор вершин по алфавиту):
- Запишем вершины в алфавитном порядке и для каждой из них определим, из каких вершин можно в нее попасть
Б А
В АБГ
Г А
Д БВ
Е Г
Ж ВЕ
И Д
К ИДЖЕ
- теперь определяем количество путей; сначала ставим 1 для тех вершин, в которые можно проехать только из начальной (А):
вершина
|
откуда?
|
N
|
Б
|
А
|
1
|
В
|
АБГ
|
|
Г
|
А
|
1
|
Д
|
БВ
|
|
Е
|
Г
|
|
Ж
|
ВЕ
|
|
И
|
Д
|
|
К
|
ИДЖЕ
|
|
- затем на каждом шаге добавляем те вершины, в которые можно доехать из уже добавленных в список (и из исходной точки):
вершина
|
откуда?
|
N
|
Б
|
А
|
1
|
В
|
АБГ
|
3
|
Г
|
А
|
1
|
Д
|
БВ
|
|
Е
|
Г
|
1
|
Ж
|
ВЕ
|
|
И
|
Д
|
|
К
|
ИДЖЕ
|
|
- следующий шаг
вершина
|
откуда?
|
N
|
Б
|
А
|
1
|
В
|
АБГ
|
3
|
Г
|
А
|
1
|
Д
|
БВ
|
4
|
Е
|
Г
|
1
|
Ж
|
ВЕ
|
4
|
И
|
Д
|
|
К
|
ИДЖЕ
|
|
- и последние 2 шага
вершина
|
откуда?
|
N
|
Б
|
А
|
1
|
В
|
АБГ
|
3
|
Г
|
А
|
1
|
Д
|
БВ
|
4
|
Е
|
Г
|
1
|
Ж
|
ВЕ
|
4
|
И
|
Д
|
4
|
К
|
ИДЖЕ
|
13
|
- Ответ: 13.
Решение (4 вариант, перебор всех путей с начала, А. Яфарова):
- запишем все вершины, в которые есть прямой путь из вершины A: Б, В и Г; получается три начальных отрезка:
АБ, АВ, АГ
- рассмотрим маршрут АБ: из Б можно ехать в В и Д, поэтому получаем два маршрута:
АБВ, АБД
- рассматриваем конечные точки этих маршрутов: из В можно ехать в Д и Ж, а из Д – в И и К:
АБВД, АБВЖ, АБДИ, АБДК
- снова смотрим на конечные точки: из Д едем в И и К, из Ж и И – только в К:
АБВДИ, АБВДК, АБВЖК, АБДИК, АБДК
- из И едем только в К, таким образом, все возможные маршруты, содержащие участок АБ, доведены до конечной точки К, всего 5 таких маршрутов:
АБВДИК, АБВДК, АБВЖК, АБДИК, АБДК
- затем аналогично рассматриваем маршруты, которые начинаются с АВ:
АВД, АВЖ
АВДИ, АВДК, АВЖК
АВДИК, АВДК, АВЖК
всего 3 маршрута
- наконец, остается рассмотреть маршруты, которые начинаются с АГ:
АГВ, АГЕ
АГВД, АГВЖ, АГЕЖ, АГЕК
АГВДИ, АГВДК, АГВЖК, АГЕЖК, АГЕК
АГВДИК, АГВДК, АГВЖК, АГЕЖК, АГЕК
всего 5 маршрутов
- складываем количество маршрутов для всех начальных участков: 5 + 3 + 5 = 13
- Ответ: 13.
Возможные проблемы:
- при большом количестве маршрутов легко запутаться и что-то пропустить
|
Решение (5 вариант, графический, О.О. Грущак, КузГПА):
- Главную идею решения: (число дорог в город N есть сумма дорог, приводящих в города, из которых есть прямой проезд в город N), отразим на самой схеме, показывая на ней ЧИСЛО ДОРОГ, приводящих в каждый город.
- Последовательность очевидна: начинаем с Б и Г (городов, куда есть по 1-й дороге из А)
- Посчитаем дороги в В: 1 (из A)+ 1(дороги города Б)+ 1(дороги города В)= 3
- Аналогично посчитаем дороги в Д, И, Е, Ж:
- Определяем число дорог в город К, как сумму дорог в города, с которыми он связан: Д, И, Ж, Е.
- Ответ: 13.
Задачи для тренировки:
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
- На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G, H, I, J, K. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город K?
- На рисунке – схема дорог, связывающих города 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?
- На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
Тренировочные работы МИОО 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