Организаторы конкурса благодарят Ассоциацию выпускников Уральского Университета, выступившую генеральным спонсором соревнования, и компанию "Урал-Релком", предоставившую средства связи и оказавшую информационную поддержку.

Трамвай - одноколейка.

Долгое время в городе Карпинске действовала необычная система трамвайных путей. Необычным было то, что по одной и той же паре рельсов поезда ходили в обе стороны, так что вторая пара рельсов становилась ненужной. Да ее и не было. Чтобы избежать столкновений, в нескольких точках пути использовались так называемые "разъезды". На разъезде два рельса разветвлялись в четыре, а через несколько метров сходились обратно. Таким образом, два трамвая, следующие навстречу друг другу, могли разъехаться. Если один из трамваев приезжал на разъезд раньше, то ему приходилось ждать, пока встречный поезд не подойдет.

Авторов заинтересовала проблема составления расписаний для подобных транспортных схем. Сформулированная в общем виде на языке графов, она и предлагается вниманию читателя.

Постановка задачи.

Пусть задан обыкновенный (без петель и кратных ребер) неориентированный связный граф. Для удобства дальнейшего изложения введем некоторые термины. Вершину степени один будем называть кольцом. Вершины степени два будут либо остановками, либо разъездами. Разница здесь в том, что на разъездах идущие навстречу трамваи могут разъехаться, а на остановках - не могут. Вершины степени три и более - стрелки. Вершина, являющаяся кольцом, остановкой или разъездом, называется станцией.

Далее везде предполагается, что исходный граф содержит не менее двух колец.

Маршрутом называется последовательность вершин, удовлетворяющая условиям проезда:

• любые две соседние вершины маршрута соединены ребром;
• начальная вершина маршрута совпадает с конечной и является кольцом; в точности одна из остальных вершин маршрута тоже является кольцом, при этом два этих кольца различны.¹

• если V₁ ... V_n - маршрут, то для всех i из{2,...,n-1} ( deg V_i <> 1 =>   V_i-1 <> V_i+1 ) ; Смысл этого ограничения в том, что трамваи могут разворачиваться только в кольцах. ( Здесь deg V обозначает степень вершины V).

Расписанием маршрута называется функция S(V) , ставящая в соответствие каждой стрелке и разъезду маршрута неотрицательное целое число. При этом если вершина встречается в маршруте несколько раз, ей могут соответствовать разные числа. Значение функции равно количеству встречных поездов, которое трамвай, следующий данным маршрутом, должен пропустить перед тем, как продолжить движение. Встречными считаются поезда, прибывающие по ребру, необходимому пропускающему трамваю для продолжения движения. Для удобства функцию полагаем равной нулю на остановках и кольцах.

Для каждого трамвая определяется свой маршрут. В начальный момент времени каждый трамвай находится в первой вершине этого маршрута. Если на некотором шаге трамвай находится в вершине V , то ребро, по которому он прибыл в нее, (а если V - остановка, то и второе инцидентное ей ребро) блокировано для других трамваев на этом шаге.

Зафиксируем трамвай Т и опишем его движение. Пусть трамвай прибыл в вершину V , и U - следующая по маршруту вершина . Тогда

1. Трамвай находится в состоянии ожидания, пока по ребру UV не пройдет S(V) поездов. При этом учитывается поезд ( если таковой был), прошедший по ребру UV и находящийся в вершине V в момент прибытия туда трамвая Т .
2. Пусть S(V) встречных проездов пропущено (или если S(V)=0) . Если ребро VU блокировано, то трамвай находится в состоянии ожидания до его освобождения.
3. Если трамвай не находится в состоянии ожидания, то он перемещается в вершину U .

Время измеряется в шагах. На каждом шаге происходит одновременное перемещение всех трамваев, не находящихся в состоянии ожидания.

Расписанием движения называется совокупность расписаний маршрутов, позволяющая проехать с любой станции на любую (возможно, с пересадками на промежуточных станциях ) ; при этом начальные вершины всех входящих в расписание маршрутов должны быть различны. В нулевой момент времени, с которого начинается отсчет, каждый трамвай находится в начальной вершине своего маршрута.

Рабочим временем для расписания движения называется минимальное число шагов, за которое каждый трамвай совершит не менее трех полных рейсов по своему маршруту². Если расписание движения не обеспечивает каждому трамваю трех полных рейсов, то его рабочее время полагается равным бесконечности.

Все вершины степени два исходного графа являются остановками. Добавлением разъезда назовем операцию, при которой к графу присоединяется новая вершина W , и некоторое ребро графа UV заменяется на пару ребер UW и WV . При этом W считается разъездом. Назовем граф допустимым, если он совпадает с исходным или получается из него добавлением конечного числа разъездов.

Задача состоит в построении расписания движения, обладающего минимальным рабочим временем на множестве всех допустимых графов.

Доказано (см. приложение), что для любого исходного графа с M кольцами можно построить допустимый граф, обладающий расписанием движения с конечным рабочим временем и полученный из исходного добавлением не более чем M-1 разъезда.

Условия конкурса.

В конкурсе могут принимать участие все желающие. Для этого следует написать программу, строящую по заданному графу некоторый допустимый граф и расписание движения для него. Программу необходимо доставить в организационный комитет конкурса в указанные ниже сроки. Каждый участник вправе представить не более двух программ.

Программам-участницам будет предложено несколько тестовых графов. На каждом из них будет измерено рабочее время построенного расписания движения. Если программа не справляется с построением на некотором графе, то за соответствующее рабочее время принимается удвоенное максимальное рабочее время среди всех, построенных для этого графа. Если для графа ни одна из программ не построила расписания, то для всех программ рабочее время по этому графу считается равным нулю. Число вершин тестового графа не может превосходить двадцати.

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

Для желающих посостязаться с машиной проводится дополнительный конкурс. На нем будут предложены те же тестовые графы, что и на конкурсе программ. Участники должны будут представить оргкомитету готовые расписания движения, по одному для каждого графа. Оценка работ и выявление победителей будут производиться тем же способом, что и в конкурсе программ. Победители конкурса будут награждены дипломами.

Для участия в дополнительном конкурсе необходимо прислать в оргкомитет заявку, заполненную по следующей форме:

фамилия, имя, отчество
город, страна
предприятие или учебное заведение
электронный адрес
почтовый адрес (для диплома)

Кроме перечисленного, в заявке можно указать дополнительную информацию о себе в свободной форме. Тестовые графы высылаются участникам ТОЛЬКО по электронной почте. Дополнительно эти данные будут опубликованы на WWW "http://www.mplik.rutramk" и на стенде деканата математико-механического факультета Уральского университета.

Требования к программе

1. Программа должна быть представлена в виде исходных текстов на языке С или С++, сосредоточенных в одном файле.
2. Программа должна быть переносимой, т.е. не зависеть от таких параметров, как длина битового представления int или char , набор команд процессора, и им подобных.
3. Текст программы должен начинаться с комментария, содержащего заявку той же формы, что указано выше.
4. Для компиляции программы будет использован gnu g++ в среде UNIX . Программа, не прошедшая компиляцию или сборку, к участию в конкурсе не допускается.
5. Программа должна осуществлять ввод данных со стандартного входного потока, а вывод результатов на стандартный выходной поток. Использование любых других, в том числе временных, файлов запрещено.
6. Время работы программы ограничено. Максимальное допустимое время работы содержится во входных данных (см. ниже). Программа может выяснять затраченное время с помощью стандартных библиотечных функций (см. например gmtime() ) . По истечении контрольного времени, программа будет принудительно завершена. В этом случае дальнейшие запуски программы не производятся.
7. Программа, не выдавшая по завершении работы расписания движения в формате, указанном ниже, или завершившаяся аварийно, считается не справившейся с данным тестовым графом.
8. Число добавленных разъездов не должно превышать удвоенного числа вершин исходного графа.
9. Если рабочее время построенного программой расписания превышает 10* N² , где N - число вершин исходного графа, то программа считается не справившейся с данным тестовым графом.

Формат входных данных

Для каждой вершины графа в списке смежности присутствует строка:

 
имя_вершины: имя_вершины имя_вершины ... имя_вершины 

Имя вершины не содержит пробелов, знаков препинания и табуляции и начинается с буквы.

Пример. Для графа из двух колец, соединенных ребром, входной файл может иметь вид:

15
2
V1: V2
V2: V1

Формат выходных данных

Список добавленных разъездов состоит из пар:

имя_вершины имя_вершины 

имя_вершины имя_вершины 
имя_вершины имя_разъезда 

Список маршрутов имеет вид:

<пустая строка>
имя_кольца: 0 
имя_вершины:  число
...
имя_вершины: число
имя_кольца: 0
<пустая строка>
имя_кольца: 0 
... и т.д.
 

Пример. Для входного файла, указанного выше, выходной файл может иметь вид:

2
V1 V2
V2 R1

V1: 0
R1: 0
R2: 0
V2: 0
R2: 0
R1: 0
V1: 0


 

Сроки и координаты

Программы должны быть получены оргкомитетом не позднее 19 мая 1996 года по екатеринбургскому времени. До этого же времени принимаются заявки на участие в дополнительном конкурсе. Тестовые графы будут опубликованы 20 мая. Прием работ дополнительного конкурса будет производиться до 26 мая. Результаты конкурса будут опубликованы по окончании проверки.

Допустимы следующие способы доставки работ и заявок в оргкомитет:

• высылать по электронной почте на адрес games@www.mplik.ru с темой сообщения "Karpinsk Tram-96"
• выслать по обычной почте на дискете 3.5 " 1.44M в формате IBM PC на адрес: 620083, Россия, Екатеринбург, Ленина 51, УрГУ, мат-мех, деканат . На конверте сделайте пометку "Карпинский трамвай - 96 ". Конверт можно не посылать по почте, а занести в деканат лично. При доставке в деканат дискеты не возвращаются.
• лично передать оргкомитету (мат-мех УрГУ, группа МГМТ-5). В этом случае можно получить дискеты обратно, лично обратившись в оргкомитет в течение недели после окончания конкурса.

Возможные вопросы и комментарии следует направлять по тем же адресам. Ответы на часто задаваемые вопросы и другая оперативная информация будет доступна по WWW "http://www.mplik.rutramk".

Организационный комитет конкурса

• Герштейн Сергей Яковлевич, sg@mplik.ru . Студент магистратуры Уральского университета .
• Штыков Евгений Александрович, eug@kontur.e-burg.su . Студент магистратуры Уральского университета .

Приложение

Теорема. Для любого исходного графа с M>1 кольцами можно построить допустимый граф, обладающий расписанием движения с конечным рабочим временем и полученный из исходного добавлением не более чем M-1 разъезда.

Предпошлем доказательству теоремы вспомогательное определение и лемму.

Определение. Маршрут, начинающийся с кольца V и проходящий через кольцо U , будем обозначать M(U,V). Циклическим покрытием станций исходного графа G со множеством колец К = {V₁, ...,V_n} называется совокупность маршрутов M(V₁,V₂), M(V₂,V₃), ... , M(V_n,V₁), покрывающая все станции.

Лемма. Для любого исходного графа существует циклическое покрытие станций.

Доказательство леммы. Проведем доказательство индукцией по числу остановок. База индукции очевидна: для нуля остановок любая совокупность маршрутов вида M(V₁,V₂), M(V₂,V₃), ... , M(V_n,V₁) является циклическим покрытием станций. Ее существование следует из связности исходного графа.

Рассмотрим исходный граф с P остановками. Построим по предположению индукции циклическое покрытие станций для произвольно выбранной P-1 остановки. Обозначим оставшуюся остановку через W , а инцидентные ей ребра через UW и VW. Если W принадлежит некоторому маршруту, то построенное покрытие является искомым. Предположим противное.

Пусть существует цикл W₀=W , W₁, ... , W_t=W. Найдем путь U₁, ... ,U_n, соединяющий некоторую вершину этого цикла со стрелкой одного из маршрутов. Пусть k - наибольший номер, такой что вершина U_k=W_s принадлежит нашему циклу, а m - наименьший номер, такой что m k , и вершина U_m принадлежит маршруту. Пусть этот маршрут имеет вид V_i, ... , U_m, ... , V_i. Заменим его на следующий маршрут: V_i, ... , U_m, U_m-1, ... , U_k=W_s, W_s+1, ... , W_t-1, W, W₁, ... , W_s=U_k, U_k+1, ... , U_m-1, U_m, ... , V_i. Полученная совокупность маршрутов является искомым покрытием.

Пусть W - точка сочленения. Покажем, что в этом случае одна из двух компонент связности, образующихся при удалении W содержит все кольца исходного графа. Действительно, если это не так, то из одной компоненты в другую проезд невозможен. Степень каждой вершины компоненты, не содержащей колец, не меньше двух, и следовательно, эта компонента содержит цикл. Используя цикл, любой маршрут можно модифицировать аналогичным описанному выше способом, причем измененный маршрут с необходимостью пройдет через вершину W. Лемма доказана.

Доказательство теоремы . Пусть V₁, ... , V_n - все кольца исходного графа. В силу леммы существует циклическое покрытие станций M(V₁,V₂), M(V₂,V₃), ... , M(V_n,V₁) . Добавим по одному разъезду на ребра, инцидентные вершинам V₂, ... , V_n, включив эти разъезды в соответствующие места маршрутов покрытия. Положим функцию расписания маршрута равной нулю всюду, за исключением добавленных разъездов, где она будет равна единице.

Полученное расписание движения решает поставленную задачу, т.к. трамваи объезжают свои маршруты поочередно и не мешают друг другу. Теорема доказана.

¹Смысл требования в том, что маршрут представляет из себя путь от первого кольца до второго и обратно, причем пути туда и обратно могут не совпадать.

²Первый рейс трамвая может отличаться от последующих из-за различного расположения других трамваев в момент старта. Поэтому в последующих рейсах могут возникать задержки, отсутствовавшие в первом.