Жизнь на Марсе. При высадке на Марс было основано N поселений. Их координаты заданы. Каждое поселение равномерно расширялось во все стороны на L марсианских миль в месяц. Постепенно поселения начали сливаться друг с другом, получая общее название. Какое минимальное время с момента высадки потребуется для того, чтобы на Марсе осталось не более K поселений?

Будем рассматривать граф, соответствующий марсианским поселениям. Если нет совпадающих по координатам поселений, то сначала он состоит только из N вершин. Два поселения соприкоснутся в середине соединяющего их отрезка через время T=D/2L, где D – расстояние между поселениями. Назовем это событие встречей. Будем встречу поселений отмечать ребром графа.

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

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

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

Рекурсия. Имеется программа, состоящая из n процедур P₁, P₂ ,…, P_n. Пусть для каждой процедуры известны процедуры, которые она может вызывать. Процедура P называется потенциально рекурсивной, если существует такая последовательность процедур Q₀, Q₁, …, Q_k, что Q₀ = Q_k = P, k ≥ 2 и для i = 1,…, k–1 процедура Q_i-1 может вызвать процедуру Q_i. Требуется определить для каждой из заданных процедур, является ли она потенциально рекурсивной.

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

Часто по смыслу задачи граф не должен иметь циклов. Рассмотрим, например, следующую задачу [3, 11].

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

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

Эта модель появилась в конце 50-х годов прошлого столетия и легла в основу направления "Сетевое планирование”. Таким образом, например, планировался американский проект пилотируемого полета на Луну. Иногда работам ставят в соответствие не вершины, а дуги графа. Каждый способ имеет свои достоинства и недостатки.

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

Если в графе есть цикл, содержащий некоторую вершину A, то при поиске в глубину с начальной вершиной V обязательно встретится дуга цикла, ведущая в A. С другой стороны, в графе может быть цикл, не содержащий вершины A и такой, что при поиске с начальной вершиной A он не найдется. Значит, для полного исследования графа можно запустить поиск в глубину с каждой вершиной в качестве начальной.

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

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

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

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

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

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

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

Вал с номером M вращается по часовой стрелке со скоростью 1000 оборотов в минуту. Требуется для каждого вала найти его угловую скорость. Необходимо отметить случай, когда заданная система противоречива, то есть на один вал передается вращение от разных источников с разными угловыми скоростями.

Для перехода к графу сопоставим вершинам валы, а ребрам - ременные передачи или жесткое сцепление. Тогда проводя поиск в ширину от начального вала можно рассчитать движение каждого вала.

В следующей задаче также можно использовать графы [11].

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

Вершинам ориентированного графа поставим в соответствие владельцев квартир. Если владельца A устраивает для обмена квартира (квартиры) владельца B, то в графе окажется дуга AB.

Учтем в описанном графе условия и пожелания нового клиента X. Простой обмен сводится к нахождению всех вершин, которые связаны с вершиной X взаимными дугами. Более сложные обмены обеспечивает поиск циклов X - C₁ - C₂ -…- C_K – X. Предполагается, что клиент переедет в квартиру владельца C₁, тот в свою очередь переедет в квартиру владельца C₂ и, в конце концов, владелец C_K займет квартиру владельца X. Задача может быть существенно усложнена, если допустить, что возможны обмены квартиры на две других, которые могут принадлежать разным владельцам.

Рассмотрим еще одну задачу с применением графов.

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

В качестве вершин графа возьмем имена заданных документов, а также имена файлов, на которые есть ссылки. В качестве дуг примем ссылку на файл. Тогда общее количество ссылок на несуществующие документы – это сумма всех ссылок на вершины, соответствующие таким файлам, имена которых не фигурируют как имена документов.

Количество документов, на которые нельзя попасть по ссылкам, начиная с первого документа, можно определить с помощью матрицы достижимости. Эта матрица, называемая также транзитивным замыканием, легко получается с помощью алгоритма Уоршела [1, 11]. По матрице достижимости находится количество вершин, не достижимых из первой вершины.

Иногда в дополнение к графу, который следует из условий задачи, необходимо строить некий модифицированный граф. Рассмотрим подобную задачу.

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

Определенный агент добыл ценные сведения. Резидент решил получить информацию по двум независимым каналам. Требуется найти минимальный размер затрат резидента для оплаты передачи информации по двум цепочкам агентов, которые начинаются с удачливого агента и заканчиваются резидентом, не пересекаясь друг с другом.

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

Во-первых, убедимся, что нельзя использовать "жадный” алгоритм, то есть найти кратчайший путь, затем удалить из графа вершины этого пути вместе с входными и выходными дугами и снова найти кратчайший путь. Рассмотрим следующий граф:

10 9

2 9

2 6 2 1

2 4

Пусть требуется найти два пути минимальной суммарной стоимости из вершины 1 в вершину 3.

Кратчайший путь 1-4-5-3 имеет стоимость 6. Следующим минимальным путем, не пересекающимся с первым, является путь 1-2-3 стоимости 19. Суммарная стоимость двух путей 25. Однако путь 1-5-6-3 стоимости 11 и 1-4-2-3 стоимости 13 имеют суммарную стоимость 24. Более того, путь 1-4-2-3 стоимости 13 и 1-5-3 стоимости 8 имеют суммарную стоимость 21.

Перебор всех путей и выбор лучшей пары из них бесперспективен. Для графа из 30 вершин, в котором все вершины связаны дугами, только количество путей с включением всех вершин равно 28!, что составляет более 10²⁹. А если рассматривать все пути и перебирать пары путей?!

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

Дуга из некоторой первой пары вершин в какую-либо вторую пару при поиске двух путей из A в B описывается следующими правилами:

• в исходном графе есть дуга L, соединяющая одну из вершин первой пары с одной из вершин второй пары;

• две другие вершины из этих пар совпадают;

• два пути, восстановленные в исходном графе из второй пары в обратном направлении к паре вершин (A, A), где A - начальная вершина, не пересекаются;

• стоимостью дуги между парами вершин является стоимость дуги L.

В приведенном примере дуга (1, 1) - (1, 4) имеет стоимость 2, а дуга (2, 5) - (5, 6) – стоимость 9.

Задача сводится к нахождению кратчайшего пути в новом графе из вершины (A, A) в вершину (B, B), где A и B - начальная и конечная вершины исходного графа соответственно. Поскольку стоимости дуг положительны, то удобно применить алгоритм Дейкстры (поиск в ширину кратчайшего пути). В новом графе не более N² вершин, поэтому общая трудоемкость алгоритма O(N⁴), что вполне допустимо для заданной в условии размерности графа.

В нашем примере кратчайшим путем будет (1, 1) - (1, 4) - (1, 2) - (2, 5) - (2, 3) - (3, 3) стоимости 21. По этому пути восстанавливаются два пути в исходном графе 1-4-2-3 – стоимости 13 и 1-5-3 – стоимости 8. Суммарная стоимость этих двух путей составляет указанную выше величину 21.

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

Задачи для самостоятельного решения

13.1. Центр дерева (6)

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

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

Ввод из файла INPUT.TXT. В первой строке вводится значение N (1 ≤ N ≤ 1000). В каждой из следующих N-1 строк вводится через пробел пара номеров компьютеров, обозначающая соединение.

Вывод в файл OUTPUT.TXT. В первой строке выводится значение M – количество искомых компьютеров. Во второй строке выдаются через пробел в порядке возрастания номера искомых компьютеров.

Пример

Ввод

4

1 2

4 3

2 3

Вывод

2

2 3

Указание. Предложить структуру данных, обеспечивающую быстрое нахождение листьев бескорневого дерева из условия задачи.

13.2. Радистка Кэт (6)

Разведывательная сеть состоит из N агентов, которые пронумерованы от 1 до N. Радистке Кэт присвоен номер 1. Имеется ровно N -1 каналов связи между агентами. Радистка Кэт может получить сообщение по сети от любого агента напрямую или через промежуточных агентов. Каждый канал может быть защищенным либо почти защищенным. Известно, что сообщение от агента не может быть перехвачено, если хотя бы половина каналов на пути от агента к Кэт окажется защищенными. Какое минимальное число каналов нужно преобразовать из почти защищенных в защищенные, чтобы сообщения агентов не перехватывались?

Ввод из файла INPUT.TXT. В первой строке вводится значение N. (1 ≤ N ≤ 100000). В каждой из следующих N -1 строк вводится через пробел три целых числа. Первые два из них задают номера агентов, связанных соединением, а третье число равно 1 в случае защищенного канала и 0 в случае почти защищенного.

Вывод в файл OUTPUT.TXT. В первой строке выводится значение M – количество каналов, которые нужно преобразовать. В следующих M строках парами номеров агентов выдаются каналы, подлежащие преобразованию.

Пример

Ввод

5

5 1 0

3 1 0

2 3 1

4 3 0

Вывод

2

1 2

13.3. Максимальный груз (5)

Имеются города с номерами от 1 до N и дороги между некоторыми из них. Из любого города можно попасть в любой другой, проехав, возможно, через некоторые другие города. Известно, какой максимальный груз можно провезти по каждой из дорог. Нужно узнать, какие максимальные грузы можно доставить из города 1 в остальные города.

Ввод из файла INPUT.TXT. Первая строка содержит количество городов N и дорог M через пробел. В каждой из следующих M строк находится по 3 числа. Первые два из них - i и j- задают дорогу, а третье C_ij – ее грузоподъемность.

Ограничения: 2 ≤ N ≤ 50; 0 ≤ C_ij ≤ 1000; время работы программы до 2 с.

Вывод в файл OUTPUT.TXT. В i-й строке выводится значение максимального груза, который может быть доставлен их города 1 до i+1-го города. Таким образом, файл OUTPUT.TXT состоит из M-1 строки.

Пример

Ввод

5 6

1 2 6

1 5 7

2 4 3

5 4 1

2 3 6

4 3 1

Вывод

6

6

3

7

Подсказка. Модифицировать алгоритм Дейкстры.

13.4. Эх, дороги (7)

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

Ввод из файла INPUT.TXT. Первая строка содержит целое положительное число N, задающее количество городов. Далее следуют N строк, описывающих длины участков дорог в виде матрицы С={C_{i j} }. В i-ой строке задаются через пробел длины дорог от города с номером i до городов с номерами 1, 2, …, N соответственно в виде целых положительных чисел, то есть значения C_i1, C_i2,…, C_iN. Если из i-го города нет прямого проезда в j-й, то в соответствующем месте ставится 0. Расстояния от города до самого себя также считается равным нулю, то есть главная диагональ матрицы C_ij состоит из нулей. Значения C_ij и C_ji могут отличаться. По некоторым дорогам разрешено движение только в одном направлении. Столица имеет номер 1.

Ограничения: 2 ≤ N ≤ 50; 0 ≤ C_ij ≤ 1000; время работы программы до 2 с.

Вывод в файл OUTPUT.TXT. В i-й строке выводится длина второго по минимальности пути из столицы до i+1-го города. Если кратчайших путей несколько, то эта длина совпадает с длиной кратчайшего пути. Повторение городов в пути допускается. Если другого пути не существует, выводится строка со словом No. Таким образом, файл OUTPUT.TXT состоит из N-1 строки.

Примеры

Ввод 1 Ввод 2

4 4

0 3 2 0 0 3 2 0

0 0 3 3 0 0 3 3

0 0 0 5 0 0 0 5

0 0 4 0 6 0 4 0

Вывод 1 Вывод 2

No 15

6 6

7 7

Подсказка. Модифицировать алгоритм Дейкстры.