Ещё пример задания:
Р-05. Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Например, из A в B есть дорога длиной 4 км, а из B в A дороги нет.
|
A |
B |
C |
D |
E |
F |
Z |
A |
|
4 |
6 |
|
|
|
30 |
B |
|
|
3 |
|
|
|
|
C |
|
|
|
11 |
|
|
27 |
D |
|
|
|
|
4 |
7 |
10 |
E |
|
|
|
|
|
4 |
8 |
F |
|
|
|
|
5 |
|
2 |
Z |
29 |
|
|
|
|
|
|
Сколько существует таких маршрутов из A в Z, которые проходят через 6 и более населенных пунктов? Пункты A и Z при подсчете учитывать. Два раза проходить через один пункт нельзя.
Решение (1 способ, перебор вариантов):
обратим внимание, что числа в таблице нас совсем не интересуют – достаточно знать, что между данными пунктами есть дорога
нам нужно найти все пути, которые проходят через 6 и более пунктов, считая начальный и конечный; то есть между A и Z должно быть не менее 4 промежуточных пункта
начнем с перечисления всех маршрутов из А, которые проходят через 2 пункта; по таблице видим, что из A можно ехать в B, C и Z; количество пунктов на маршруте будем записывать сверху:
2
3
4
5
6
7
AB
AC
AZ
маршрут AZ нас не интересует, хотя он и пришел в конечный пункт, он проходит меньше, чем через 6 пунктов (только через 2!); здесь и далее такие «неинтересные» маршруты из A в Z будем выделять серым фоном
теперь ищем все маршруты, проходящие через 3 пункта; из B можно ехать только в C, а из С – в D и Z:
2
3
4
5
6
7
AB
ABC
AC
ACD
ACZ
AZ
далее из C едем в D и Z, а из D – в E, F и Z:
2
3
4
5
6
7
AB
ABC
ABCD
ABCZ
AC
ACD
ACDE
ACDF
ACDZ
ACZ
AZ
строим следующий уровень только для тех маршрутов, которые ещё не пришли в Z:
2
3
4
5
6
7
AB
ABC
ABCD
ABCDE
ABCDF
ABCDZ
ABCZ
AC
ACD
ACDE
ACDEF
ACDEZ
ACDF
ACDFE
ACDFZ
ACDZ
ACZ
AZ
следущие два уровня дают «интересные» маршруты, проходящие через 6 или 7 пунктов:
2 |
3 |
4 |
5 |
6 |
7 |
AB |
ABC |
ABCD |
ABCDE |
ABCDEF |
ABCDEFZ |
ABCDEZ |
|
||||
ABCDF |
ABCDFE |
ABCDFEZ |
|||
ABCDFZ |
|
||||
ABCDZ |
|
|
|||
ABCZ |
|
|
|
||
AC |
ACD |
ACDE |
ACDEF |
ACDEFE |
|
ACDEFZ |
|
||||
ACDEZ |
|
|
|||
ACDF |
ACDFE |
ACDFEF |
|
||
ACDFEZ |
|
||||
ACDFZ |
|
|
|||
ACDZ |
|
|
|
||
ACZ |
|
|
|
|
|
AZ |
|
|
|
|
|
на последней схеме зелёным фоном выделены «интересные» маршруты, их всего 6; красным фоном отмечены маршруты, в которых получился цикл – они дважды проходят через один и тот же пункт; такие маршруты запрещены и мы далее их не рассматриваем
Ответ: 6.
можно было нарисовать схему возможных маршрутов в виде дерева:
Решение (2 способ, через построение графа, М.В. Кузнецова)
Построим граф, соответствующий таблице. Наличие значений преимущественно на диагонали таблицы говорит о наличии дорог, последовательно связывающих указанные населенные пункты (A-B, B-C, …). Построение графа начнем с размещения узлов (населенных пунктов), располагая их «по кругу», а затем последовательно изобразим все указанные в таблице дороги. Так как нас интересует только число дорог, проходящих через 6 и более пунктов, то длины дорог (веса ребер) указывать не будем.
Из А исходит три дороги, но ясно, что дорога A-Z нас не интересует.
Из B исходит одна дорога, из С - две…
Из D исходит три дороги, из Е – две.
Из F выходят две дороги, причём одна возвращает в Е (рисуем новую стрелку, FE и EF – разные дороги).
Анализ графа.
Общее число пунктов 7. Есть дороги, последовательно связывающие все 7 пунктов, значит 1-й путь: ABCDEFZ.
Есть 3 дороги, которые позволяют «проехать мимо» соседнего пункта (AC идёт «мимо» B, DF – мимо E,…), значит, есть 3 способа проехать через 6 пунктов (ACDEFZ, ABCDFZ, ABCDEZ).
…
Есть одна «обратная дорога», позволяющая изменить порядок прохождения пунктов – FE. Эта дорога при наличии дороги DF, идущей «мимо» Е, создает дополнительные маршруты: один через 7 пунктов ABCDFEZ и один через 6 пунктов ACDFEZ.
Вывод: общее число дорог, соответствующих условию: 1+3+2=6
Ответ: 6