Маршруты в сети кривых
Управление городских железных дорог намерено по-новому перегруппировать маршруты, которыми оно обслуживает свою трамвайную сеть. Оно предполагает распределить эти маршруты таким образом, чтобы каждая линия обслуживалась впредь лишь одним-единственным маршрутом; при этом пассажир получает право с одним и тем же билетом менять маршруты и делать столько пересадок, сколько ему нужно, чтобы достигнуть места своего назначения. Задача заключается в том, чтобы определить наименьшее число маршрутов, необходимое для полного проведения в жизнь этого принципа.
Рисунок 1
Для маленького города, где рельсовая сеть может быть схематически представлена рис. 1, вопрос решается крайне просто. Мы должны либо установить один маршрут по линии АВ и другой по линии CD, либо объединить в один маршрут АК и KD, а по линии ВКС назначить второй маршрут, либо, наконец, провести один маршрут из А через К в С, а другой – из В через К в D.
Очевидно, что этим исчерпываются все возможности и что при любой из этих комбинаций необходимы два маршрута. Одним-единственным маршрутом обойтись нельзя, как бы мы ни комбинировали наши четыре линии АК, ВК, СК и DK. При этом мы исключаем решения, которые явно не соответствуют условию задачи; так, например, нельзя маршрут, ведущий из К, закончить в какой-нибудь точке R, а от R до В назначить другой маршрут, т.е. устроить в R пересадочный пункт, как это иногда бывает необходимо делать в связи с ремонтными работами. При таких условиях нам потребовалось бы, конечно, больше двух маршрутов, и можно было бы даже сколько угодно увеличивать их число подобным образом. Однако задача, как уже было сказано, состоит в том, чтобы обойтись наименьшим числом маршрутов.
Рисунок 2
В несколько более трудных условиях находится управление, ведающее городской трамвайной сетью, схематически изображенной на рис. 2; впрочем, и эта схема все еще довольно проста. Управление может установить прежде всего окружной или кольцевой маршрут от А через В, С, D, Е опять к А, далее, второй – диаметральный маршрут от А через F, G, Н к D, и, наконец, к этим двум оно должно, очевидно, присоединить еще три маршрута: EG, BF, СН, и всего, таким образом, ввести пять маршрутов. Впрочем, один из них можно сэкономить: например, маршруты первый и второй можно объединить в один, заставив курсировать вагоны сначала от А через В, С, D, Е опять к А и затем далее, от А через F, G, Н к D. Но нельзя ли обойтись и тремя маршрутами?
Рисунок 3
Или рассмотрим еще один пример. По схеме рис. 3 мы можем назначить один маршрут от А через В, С, D, Е опять к А и оттуда через F к В. Тогда для обслуживания всей сети нам потребуются еще три маршрута: FC, FD и FE. Но и здесь это число можно сократить, назначив второй маршрут от С через F до D и введя «челнок» на участке EF. В результате мы обходимся здесь тремя маршрутами, причем для двух из них точка F является промежуточной станцией, а для третьего эта точка служит конечным пунктом. Но нельзя ли обойтись только двумя маршрутами?
В двух последних случаях (впрочем, все еще довольно простых) мы уже сталкиваемся со сравнительно большим числом возможностей, которые нам нужно разобрать, чтобы с такой же ясностью и полнотой, как для схемы рис. 1, ответить на вопрос, можно ли обойтись меньшим числом маршрутов или нет?
И вот уже сквозь внешнее оформление задачи, столь далекой от обычных условий и масштабов трамвайной сети больших городов, намечаются контуры математической проблемы, правда, очень несложной. В схеме рис. 1 мы просто испробовали все возможности и получили искомый ответ (именно два маршрута). Однако такой подход к задаче мы не можем назвать математическим. И если мы прилежно исчерпаем все возможности схемы рис. 2, пока не удостоверимся, что для нее нельзя обойтись меньше, чем четырьмя маршрутами, то и эта работа имеет столь же мало общего с математикой, как, например, терпеливое, пусть даже безошибочное, перемножение семизначных чисел. Математика, или, по крайней мере, легкое веяние математики, появляется только тогда, когда мы находим решение задачи не путем пересмотра всех случаев и не только для одной частной схемы рис. 2, а путем логических умозаключений сразу для произвольно сложных сетей и кривых.
Идея, к которой сводится решение нашей задачи, чрезвычайно проста. Обратим внимание на то, где должны быть расположены конечные пункты отдельных маршрутов. Прежде всего, совершенно ясно, что они должны быть там, где находится конец одного какого-нибудь отрезка нашей сети, например – для схемы рис. 1 – в точках А, В, С, D. Поскольку в этой схеме имеется всего четыре конечные точки и так как каждый маршрут имеет самое большее два конечных пункта (когда он не является кольцевым), то ясно, что между этими четырьмя конечными пунктами должно быть назначено, по меньшей мере, два маршрута. Таким образом, решение, полученное нами выше в результате проб, достигнуто теперь посредством общего рассуждения.
Но в схеме рис. 2 вовсе нет свободных концов. Зато здесь имеются такие точки, как, например, А, в которых сходятся три направления. Если каждый участок должен обслуживаться одним только маршрутом, то очевидно, что в такой точке должен быть, по крайней мере, один конечный пункт некоторого маршрута. Поскольку в схеме рис. 2 таких точек, как это легко сосчитать, имеется восемь, то здесь должно быть, по меньшей мере, восемь конечных пунктов маршрутов. Восемь – опять число четное – число концов четырех маршрутов. Таким образом, для схемы рис. 2 должно быть установлено, самое меньшее, четыре маршрута; трех маршрутов здесь будет недостаточно. В схеме рис. 3 мы встречаемся с подобным же положением: здесь имеется пять точек пересечения того же типа, что и выше рассмотренные, и, кроме того, шестая точка – F, в которой сходятся не три, а пять направлений и которую мы назовем «точкой пересечения 5-го порядка». Две пары из этих пяти направлений могут принадлежать, как это выяснено выше, каждая одному маршруту, и одно остается лишним, так что точка F обязательно должна быть конечным пунктом. Сказанное имеет силу для любой точки пересечения любого нечетного порядка. Полученное число конечных пунктов, 6, опять четное и требует, по меньшей мере, трех маршрутов, двух будет недостаточно. Теперь ясно, каким образом для любой, сколь угодно сложной сети кривых можно непосредственно вычислить наименьшее возможное число необходимых маршрутов: нужно перебрать все точки пересечения и сосчитать, сколько среди них имеется точек нечетного порядка; тогда наименьшее число необходимых маршрутов будет равно половине числа таких точек.
Продвинувшись так далеко по пути овладения нашей проблемой, мы намерены теперь довести ее решение до конца; мы покажем, что число точек пересечения нечетного порядка всегда четно и что всегда можно обойтись числом маршрутов, равным половине числа точек нечетного порядка.
Ясно, что вообще всякую, сколь угодно сложную систему кривых можно обслужить таким количеством маршрутов, что ни один отрезок не будет обслуживаться одновременно двумя маршрутами, – надо только на каждом отдельном участке между парой соседних точек пересечения ввести отдельный маршрут («челнок»), для чего потребуется столько же маршрутов, сколько имеется таких участков.
Но в то же время ясно, что, вообще говоря, мы вводим при этом много лишних маршрутов. Нас же интересует наименьшее возможное число маршрутов. Ясно также, что среди всех возможных систем маршрутов заведомо должны существовать так называемые «оптимальные системы», т.е. системы с наименьшим числом маршрутов, подобно тому, как среди учеников школы непременно должны быть самые младшие, хотя какие именно это ученики и нельзя в точности установить до проверки метрик.
Далее ясно, что система маршрутов ни в коем случае не может быть оптимальной, если в ней имеются излишние конечные пункты, подобные, например, пункту R в схеме рис. 1. Система не может быть оптимальной и тогда, когда в ней не произведены возможные соединения маршрутов и имеются такие точки, в которых смыкаются своими конечными пунктами два различных маршрута; в этом случае можно уменьшить число маршрутов путем попарного их соединения (как, например, в схеме рис. 3 объединялись маршруты CF и DF). Оптимальная система маршрутов не допускает подобных сокращений. Все такие пары маршрутов в ней уже соединены, и точка пересечения нечетного порядка может быть концом не более чем одного маршрута. Точка же пересечения четного порядка вообще не может быть конечным пунктом.
Остается еще выяснить, могут ли входить в состав оптимальных систем замкнутые кольцевые маршруты, вовсе не имеющие конечных пунктов. Подобный кольцевой маршрут нам встретился при рассмотрении схемы рис. 2. Мы сумели там устранить это кольцо, присоединив к нему в пункте А маршрут DHGFA и уменьшив тем самым общее число маршрутов с пяти до четырех. Этот прием можно применить во всех тех случаях, когда на кольцевом маршруте имеется точка пересечения нечетного порядка. Таким образом, в оптимальной системе (с точкой пересечения нечетного порядка) такого кольцевого маршрута быть не может, ибо при наличии его число маршрутов допускало бы сокращение.
Рисунок 4
Если точки пересечения, которые лежат на кольце – все четного порядка, то можно поступить подобным же образом. Пусть А будет такой точкой пересечения четного порядка (рис. 4) на кольцевом маршруте (имеющем форму восьмерки); дальнейшее направление исходящих из А (пунктирных) ветвей на рисунке не показано и может быть совершенно произвольным. Как уже было выяснено, точка А в оптимальной системе заведомо не является конечным пунктом для пунктирных ветвей, сходящихся в А. Маршрут, ведущий, например, из В в А, находит в этой точке свое продолжение, скажем, в ветви АЕ. При этих условиях мы можем остановить движение по этому маршруту ВАЕ в точке А, заставить вагон обойти кольцо и только уже после, этого позволить ему продолжать путь в направлении АЕ. Кольцо было бы таким образом включено в маршрут ВАЕ, а общее число маршрутов благодаря этому уменьшилось бы на один, что для оптимальной системы невозможно.
Итак, мы пришли к выводу, что в оптимальной системе конечные пункты маршрутов могут быть только в точках пересечения нечетного порядка, и именно по одному конечному пункту на каждую точку пересечения. Мы выяснили далее, что в оптимальной системе кольцевых маршрутов вообще не может быть, за исключением того случая, когда вся сеть и все имеющиеся в сети точки пересечения четного порядка охватываются одним-единственным кольцевым маршрутом. Таким образом, число точек пересечения нечетного порядка равно числу конечных пунктов маршрутов в оптимальной системе. Из этого следует, что число точек пересечения нечетного порядка всегда четно и что можно установить маршруты так, что их число будет равно половине числа точек пересечения нечетного порядка. Если же точки пересечения все четного порядка, то вопрос решается единственным, не имеющим концов, кольцевым маршрутом.
Источник: Ганс Радемахер, Отто Тепліц. Числа і фігури (Тернопіль, «Навчальна книга – Богдан», 2010).
Смотрите так же:
Создано на конструкторе сайтов Okis при поддержке Flexsmm - накрутить подписчиков в вк