 |
Решение (2 способ, через построение графа, М.В. Кузнецова)
|
|
|
|
1) Построим граф, соответствующий таблице. Наличие значений преимущественно на диагонали таблицы говорит о наличии дорог, последовательно связывающих указанные населенные пункты (A-B, B-C, …). Построение графа начнем с размещения узлов (населенных пунктов), располагая их «по кругу», а затем последовательно изобразим все указанные в таблице дороги. Так как нас интересует только число дорог, проходящих через 6 и более пунктов, то длины дорог (веса ребер) указывать не будем.
| 
|
| Из А исходит три дороги, но ясно, что дорога A-Z нас не интересует. | Из B исходит одна дорога, из С - две… |
| 
|
| Из D исходит три дороги, из Е – две. | Из F выходят две дороги, причём одна возвращает в Е (рисуем новую стрелку, FE и EF – разные дороги). |
2) Анализ графа.
Общее число пунктов 7. Есть дороги, последовательно связывающие все 7 пунктов, значит 1-й путь: ABCDEFZ.
Есть 3 дороги, которые позволяют «проехать мимо» соседнего пункта (AC идёт «мимо» B, DF – мимо E,…), значит, есть 3 способа проехать через 6 пунктов (AC DEFZ, ABC DF Z, ABCD EZ).
…
Есть одна «обратная дорога», позволяющая изменить порядок прохождения пунктов – FE. Эта дорога при наличии дороги DF, идущей «мимо» Е, создает дополнительные маршруты: один через 7 пунктов ABC DFE Z и один через 6 пунктов ACDFE Z.
3) Вывод: общее число дорог, соответствующих условию: 1+3+2=6
4) Ответ: 6
Ещё пример задания:
Р-04. Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
| A | B | C | D | E | F | G | |
| A | |||||||
| B | |||||||
| C | |||||||
| D | |||||||
| E | |||||||
| F | |||||||
| G |
Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).
|
|
|
Решение:
9) начнём строить возможные маршруты из пункта A; за 1 шаг можно приехать в B, D или сразу в G (в скобках показаны длины маршрутов):
AB(5), AD(12), AG(25)
заметим, что G – это целевая точка (конечный пункт), поэтому мы уже имеем один полный маршрут длиной 25
10) строим двух шаговые маршруты: из B дальше можно ехать в D (возврат в А неинтересен!)
ABD (5 + 8 = 13)
этот маршрут нет смысла продолжать, поскольку в D можно приехать быстрее: длина уже найденного маршрута AD равна 12
11) из D можно ехать в B и C:
ADB (12 + 8 = 20)
ADC (12 + 2 = 14)
12) третий шаг: маршрут ADB продолжать бессмысленно: из B можно вернуться только в A и D
13) продолжаем маршрут ADC (14):
ADCE (14 + 4 = 18)
ADCF (14 + 5 = 19)
ADCG (14 + 10 = 24)
в последнем варианте мы приехали в конечный пункт, причем новый маршрут имеет длину 24 < 25, то есть, он короче найденного ранее
14) четвёртый шаг: продолжаем маршрут ADCE:
ADCEG (18 + 5 = 23)
и маршрут ADCF:
ADCFG (19 + 5 = 24)
15) других продолжений (без возврата в уже посещённые пункты) нет, поэтому кратчайший маршрут – ADCEG, он имеет длину 23.
16) Ответ: 23.
17) Заметим, что эти рассуждения можно зарисовать в виде дерева возможных маршрутов. После первого шага:
После второго шага:
После третьего шага:
После четвёртого шага:
Ещё пример задания:
Р-03. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
| A | B | C | D | E | F | |
| A | ||||||
| B | ||||||
| C | ||||||
| D | ||||||
| E | ||||||
| F |
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
|
|
|
Решение (вариант 1, использование схемы):
1) построим граф – схему, соответствующую этой весовой матрице; из вершины А можно проехать в вершины B и C (длины путей соответственно 2 и 4):
2) для остальных вершин можно рассматривать только часть таблицы над главной диагональю, которая выделена серым цветом; все остальные рёбра уже были рассмотрены ранее
3) например, из вершины В можно проехать в вершины C и E (длины путей соответственно 1 и 7):
4) новые маршруты из С – в D и E (длины путей соответственно 3 и 4):
5) новый маршрут из D – в E (длина пути 3):
6) новый маршрут из E – в F (длина пути 2):
7) нужно проехать из А в F, по схеме видим, что в любой из таких маршрутов входит ребро EF длиной 2; таким образом, остается найти оптимальный маршрут из A в E
8) попробуем перечислить возможные маршруты из А в Е:
А – В – Е длина 9
А – В – С – Е длина 7
А – В – C – D – Е длина 9
А –C – Е длина 8
А –C – B – Е длина 12
А –C – D – Е длина 10
9) из перечисленных маршрутов кратчайший – A-B-C-E – имеет длину 7, таким образов общая длина кратчайшего маршрута A-B-C-E-F равна 7 + 2 = 9
10) таким образом, правильный ответ – 9.
Решение (вариант 2, с начала маршрута):
1) составим граф, который показывает, куда (и как) можно ехать из пункта А, рядом с дугами будем записывать увеличение пути, а рядом с названиями пунктов – общую длину пути от пункта A:
2) видно, что напрямую в пункт F из A не доехать
3) строим граф возможных путей дальше: определяем, куда можно ехать из B и C (конечно, не возвращаясь обратно); из B можно ехать только в A (обратно), в C и в E;
4) узел C уже есть на схеме, и оказывается, что короче ехать в него по маршруту A-B-C, чем напрямую A-C, длина «окольного» пути составляет 3 вместо 4 для «прямого»;
при движении по дороге B-E длина увеличивается на 7:
5) строим маршруты из пункта C; кроме A и B, из пункта C можно ехать в D (длина 3) и E (длина 4), причем кратчайший маршрут из A в E оказывается A-B-C-E (длина 7); «невыгодные» маршруты на схеме показывать не будем:
6) из пункта D, кроме как в С и E, ехать некуда; путь D-C – это возврат назад (нас не интересует), путь D-E тоже не интересует, поскольку он дает длину 6 + 3 = 9, а мы уже нашли, что в E из A можно доехать по маршруту длины 7
|
|
|
7) из пункта E можно ехать в F, длина полного маршрута 7 + 2 = 9
8) Ответ: 9
Решение (вариант 3, с конца маршрута):
1) можно точно так же начинать с пункта F и искать кратчайший маршрут до A; судя по таблице, из F можно ехать только в E:
2) из E ведут дороги в B, C и D
3) из B можно сразу попасть в A, длина пути будет равна 11:
4) из пункта C есть прямая дорога в A длиной 4, таким образом, существует маршрут длиной
6 + 4 = 10
5) кроме того, есть дорога C-B, которая дает маршрут F-E-C-B-A длиной 9
6) рассмотрение пути C-D не позволяет улучшить результат: оптимальный маршрут имеет длину 9
7) Ответ: 9
| Возможные ловушки и проблемы: · можно не заметить, что маршруты, проходящие через большее число пунктов, оказываются короче (A-B-C короче, чем A-C, A-B-C-E короче, чем A-B-E) |
Ещё пример задания:
Р-02. Между четырьмя местными аэропортами: ОКТЯБРЬ, БЕРЕГ, КРАСНЫЙ и СОСНОВО, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:
Аэропорт вылета Аэропорт прилета Время вылета Время прилета
СОСНОВО КРАСНЫЙ 06:20 08:35
КРАСНЫЙ ОКТЯБРЬ 10:25 12:35
ОКТЯБРЬ КРАСНЫЙ 11:45 13:30
БЕРЕГ СОСНОВО 12:15 14:25
СОСНОВО ОКТЯБРЬ 12:45 16:35
КРАСНЫЙ СОСНОВО 13:15 15:40
ОКТЯБРЬ СОСНОВО 13:40 17:25
ОКТЯБРЬ БЕРЕГ 15:30 17:15
СОСНОВО БЕРЕГ 17:35 19:30
БЕРЕГ ОКТЯБРЬ 19:40 21:55
Путешественник оказался в аэропорту ОКТЯБРЬ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт СОСНОВО.
1) 15:40 2) 16:35 3)17:15 4) 17:25
Решение:
1) сначала заметим, что есть прямой рейс из аэропорта ОКТЯБРЬ в СОСНОВО с прибытием в 17:25:
ОКТЯБРЬ СОСНОВО 13:40 17:25
2) посмотрим, сможет ли путешественник оказаться в СОСНОВО раньше этого времени, если полетит через другой аэропорт, с пересадкой
3) можно лететь, через КРАСНЫЙ, но, как следует из расписания,
ОКТЯБРЬ КРАСНЫЙ 11:45 13:30
…
КРАСНЫЙ СОСНОВО 13:15 15:40
путешественник не успеет на рейс КРАСНЫЙ – СОСНОВО, который улетает в 13:15, то есть на 15 минут раньше, чем в КРАСНЫЙ прилетает самолет ОКТЯБРЬ – КРАСНЫЙ
4) можно лететь через БЕРЕГ,
БЕРЕГ СОСНОВО 12:15 14:25
|
|
|
…
ОКТЯБРЬ БЕРЕГ 15:30 17:15
но рейс БЕРЕГ – СОСНОВО вылетает даже раньше, чем рейс ОКТЯБРЬ – БЕРЕГ, то есть, пересадка не получится
5) поскольку даже перелеты с одной пересадкой не стыкуются по времени, проверять варианты с двумя пересадками в данной задаче бессмысленно (хотя в других задачах они теоретически могут дать правильное решение)
6) таким образом, правильный ответ – 4 (прямой рейс).
| Возможные ловушки и проблемы: · можно не заметить, что путешественник не успеет на пересадку в КРАСНОМ (неверный ответ 15:40) · можно перепутать аэропорты вылета и прилета (неверный ответ 16:35) |
Решение (вариант 2, граф):
1) для решения можно построить граф, показывающий, куда может попасть путешественник из аэропорта ОКТЯБРЬ
2) из аэропорта ОКТЯБРЬ есть три рейса:
ОКТЯБРЬ СОСНОВО 13:40 17:25
ОКТЯБРЬ КРАСНЫЙ 11:45 13:30
ОКТЯБРЬ БЕРЕГ 15:30 17:15
3) построим граф, около каждого пункта запишем время прибытия
4) проверим, не будет ли быстрее лететь с пересадкой: рейс «КРАСНЫЙ-СОСНОВО» вылетает в 13:15, то есть, путешественник на него не успевает; он не успеет также и на рейс «БЕРЕГ-СОСНОВО», вылетающий в 12:15
5) таким образом, правильный ответ – 4 (прямой рейс).
Еще пример задания:
Грунтовая дорога проходит последовательно через населенные пункты А, B, С и D. При этом длина дороги между А и В равна 80 км, между В и С – 50 км, и между С и D – 10 км. Между А и С построили новое асфальтовое шоссе длиной 40 км. Оцените минимально возможное время движения велосипедиста из пункта А в пункт В, если его скорость по грунтовой дороге – 20 км/час, по шоссе – 40 км/час.
1) 1 час 2) 1,5 часа 3)3,5 часа 4) 4 часа
Решение:
1) нарисуем схему дорог, обозначив данные в виде дроби (расстояние в числителе, скорость движения по дороге – в знаменателе):
2) разделив числитель на знаменатель, получим время движения по каждой дороге
3) ехать из А в B можно
· напрямую, это займет 4 часа, или …
· через пункт C, это займет 1 час по шоссе (из А в С) и 2,5 часа по грунтовой дороге
(из В в С), всего 1 + 2,5 = 3,5 часа
4) таким образом, правильный ответ – 3.
| Возможные ловушки и проблемы: · можно не заметить, что требуется найти минимальное время поездки именно в В, а не в С (неверный ответ 1 час) · можно ограничиться рассмотрением только прямого пути из А в В и таким образом получить неверный ответ 4 часа · можно неправильно нарисовать схему |
Еще пример задания:
Р-01. Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.
|
|
|
| 1) | 2) | 3) | 4) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
Решение (вариант 1):
1) нужно рассматривать все маршруты из А в В, как напрямую, так и через другие станции
2) рассмотрим таблицу 1:
· из верхней строки таблицы следует, что из А в В напрямую везти нельзя, только через C (стоимость перевозки А-С равна 3) или через D (стоимость перевозки из А в D равна 1)
| A | B | C | D | Е | |
| A |
· предположим, что мы повезли через C; тогда из третьей строки видим, что из C можно ехать в В, и стоимость равна 4
| A | B | C | D | Е | |
| C |
· таким образом общая стоимость перевозки из А через С в В равна 3 + 4 = 7
· кроме того, из С можно ехать не сразу в В, а сначала в Е:
| A | B | C | D | Е | |
| C |
а затем из Е – в В (стоимость также 2),
| A | B | C | D | Е | |
| Е |
так что общая стоимость этого маршрута равна 3 + 2 + 2 = 7
· теперь предположим, что мы поехали из А в D (стоимость 1); из четвертой строки таблицы видим, что из D можно ехать только обратно в А, поэтому этим путем в В никак не попасть:
| A | B | C | D | Е | |
| D |
· таким образом, для первой таблицы минимальная стоимость перевозки между А и В равна 7; заданное условие «не больше 6» не выполняется
3) аналогично рассмотрим вторую схему; возможные маршруты из А в В:
· 
, стоимость 7
· 
, стоимость 7
· таким образом, минимальная стоимость 7, условие не выполняется
4) для третьей таблицы:
· , стоимость 7
· 
, стоимость 6
· 
, стоимость 7
· таким образом, минимальная стоимость 6, условие выполняется
5) для четвертой:
· 
, стоимость 9
· 
, стоимость 8
· минимальная стоимость 8, условие не выполняется
6) условие «не больше 6» выполняется только для таблицы 3
7) таким образом, правильный ответ – 3.
| Возможные ловушки и проблемы: · метод ненагляден, легко запутаться и пропустить решение с минимальной стоимостью |
Решение (вариант 2, с рисованием схемы):
1) для каждой таблицы нарисуем соответствующую ей схему дорог, обозначив стоимость перевозки рядом с линиями, соединяющими соседние станции:
| 1) | 2) | 3) | 4) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
2) теперь по схемам определяем кратчайшие маршруты для каждой таблицы:
1: или 
, стоимость 7
2: или , стоимость 7
3: , стоимость 6
4: , стоимость 8
8) условие «не больше 6» выполняется только для таблицы 3
9) таким образом, правильный ответ – 3.
| Возможные ловушки и проблемы: · нужно внимательно строить схемы по таблицам, этот дополнительный переход (от табличных моделей к графическим) повышает наглядность, но добавляет еще одну возможность для ошибки · наглядность схемы зависит от того, как удачно вы выберете расположение ее узлов; один из подходов – сначала расставить все узлы равномерно на окружности, нарисовать все связи и посмотреть, как можно расположить узлы более удобно · по невнимательности можно пропустить решение с минимальной стоимостью |
Еще пример задания [1]:
Р-00. Между четырьмя местными аэропортами: ВОСТОРГ, ЗАРЯ, ОЗЕРНЫЙ и ГОРКА, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:
Аэропорт вылета Аэропорт прилета Время вылета Время прилета
ВОСТОРГ ГОРКА 16:15 18:30
ОЗЕРНЫЙ ЗАРЯ 13:40 15:50
ОЗЕРНЫЙ ВОСТОРГ 14:10 16:20
ГОРКА ОЗЕРНЫЙ 17:05 19:20
ВОСТОРГ ОЗЕРНЫЙ 11:15 13:20
ЗАРЯ ОЗЕРНЫЙ 16:20 18:25
ВОСТОРГ ЗАРЯ 14:00 16:15
ЗАРЯ ГОРКА 16:05 18:15
ГОРКА ЗАРЯ 14:10 16:25
ОЗЕРНЫЙ ГОРКА 18:35 19:50
Путешественник оказался в аэропорту ВОСТОРГ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт ГОРКА.
1) 16:15 2) 18:15 3)18:30 4) 19:50
Решение («обратный ход»):
1) сначала заметим, что есть прямой рейс из аэропорта ВОСТОРГ в ГОРКУ с прибытием в 18:30:
ВОСТОРГ ГОРКА 16:15 18:30
2) посмотрим, сможет ли путешественник оказаться в ГОРКЕ раньше этого времени, если полетит через другой аэропорт, с пересадкой; рассмотрим все остальные рейсы, который прибывают в аэропорт ГОРКА:
ЗАРЯ ГОРКА 16:05 18:15
ОЗЕРНЫЙ ГОРКА 18:35 19:50
3) это значит, что имеет смысл проверить только возможность перелета через аэропорт ЗАРЯ (через ОЗЕРНЫЙ явно не получится раньше, чем прямым рейсом); для этого нужно быть в ЗАРЕ не позже, чем в 16:05
4) смотрим, какие рейсы прибывают в аэропорт ЗАРЯ раньше, чем в 16:05:
ОЗЕРНЫЙ ЗАРЯ 13:40 15:50
5) дальше проверяем рейсы, который приходят в ОЗЕРНЫЙ раньше, чем в 13:40
ВОСТОРГ ОЗЕРНЫЙ 11:15 13:20
6) таким образом, мы «пришли» от конечного пункта к начальному, в обратном направлении
7) поэтому оптимальный маршрут
8) и правильный ответ – 2.
| Возможные ловушки и проблемы: · «напрашивается» ошибочный ответ 18:30 (прямой рейс) · при решении задачи «прямым ходом», с начального пункта, легко пропустить вариант с двумя пересадками |
Задачи для тренировки [2]:
| A | B | C | D | |
| A | ||||
| B | ||||
| C | ||||
| D |
1) В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите схему, соответствующую таблице.
| 1) | 2) | 3) | 4) |
| 
| 
| 
|
2) В таблицах приведена протяженность автомагистралей между соседними населенными пунктами. Если пересечение строки и столбца пусто, то соответствующие населенные пункты не соединены автомагистралями. Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта А до пункта С не больше 5». Протяженность маршрута складывается из протяженности автомагистралей между соответствующими соседними населенными пунктами. При этом любой населенный пункт должен встречаться на маршруте не более одного раза.
| 1) | 2) | 3) | 4) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
3) В таблице приведена стоимость перевозки грузов между соседними станциями. Если пересечение строки и столбца пусто, то соответствующие станции не являются соседними. Укажите таблицу, для которой выполняется условие «Минимальная стоимость перевозки грузов от пункта А до пункта В не больше 3».
| 1) | 2) | 3) | 4) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
| A | B | C | D | |
| A | ||||
| B | ||||
| C | ||||
| D |
4) В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую таблице.
| 1) | 2) | 3) | 4) |
| 
| 
|  
|
5) В таблицах приведена стоимость перевозки грузов между соседними станциями. Если пересечение строки и столбца пусто, то соответствующие станции не являются соседними. Укажите номер таблицы, для которой выполняется условие «Максимальная стоимость перевозки грузов от пункта В до пункта D не больше 6».
| 1) | 2) | 3) | 4) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
| A | B | C | D | |
| A | ||||
| B | ||||
| C | ||||
| D |
6) В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую таблице.
| 1) | 2) | 3) | 4) |
| 
| 
| 
|
7) В таблицах приведена протяженность автомагистралей между соседними населенными пунктами. Если пересечение строки и столбца пусто, то соответствующие населенные пункты не являются соседними. Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта А до пункта С не больше 6». Протяженность маршрута складывается из протяженности автомагистралей между соответствующими соседними населенными пунктами. При этом через любой насеченный пункт маршрут должен проходить не более одного раза.
| 1) | 2) | 3) | 4) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
| A | B | C | D | E | |
| A | |||||
| B | |||||
| C | |||||
| D | |||||
| E |
8) В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую таблице.
| 1) | 2) | 3) | 4) |
| 
|  
| 
|
| A | B | C | D | E | |
| A | |||||
| B | |||||
| C | |||||
| D | |||||
| E |
9) В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую таблице.
| 1) | 2) | 3) | 4) |
 
| 
| ||
|
|
|
12 |
