|
Название задачи: Ориентация графа . |
 |
Условие
Задан неориентированный граф с N вершинами, пронумерованными целыми
числами от 1 до N. Напишите программу, которая последовательно решает
следующие задачи:
а) выясняет количество компонент связности
графа;
б) находит и выдает все такие ребра, что удаление любого из них ведет к
увеличению числа компонент связности;
в) определяет, можно ли ориентировать все ребра графа таким образом, чтобы
получившийся граф оказался сильно связным (ориентированный граф называется сильно связным, если из любой его
вершины можно пройти в любую другую, двигаясь по ребрам вдоль стрелок);
г) ориентирует максимальное количество ребер, чтобы получившийся граф
оказался сильно связным;
д) определяет минимальное количество ребер, которые следует добавить в
граф, чтобы ответ на пункт в) был утвердительным.
Входные данные
Во входном файле записано целое число N (1 ≤ N ≤ 100) и список ребер графа,
заданных номерами концевых вершин.
Выходные данные
Ваша программа должна вывести в выходной файл последовательно ответы на
пункты a)-д) в следующем формате:
в первой строке запишите ответ на пункт
а);
во второй строке запишите количество ребер из ответа на пункт
б), а в
последующих строках выдайте сами эти ребра;
в следующую строку выведите сообщение «NOT
POSSIBLE», если
требуемым в пункте в) способом ориентировать граф невозможно, иначе
выведите сообщение «POSSIBLE»;
далее выведите максимальное количество ребер графа, которые можно
ориентировать (пункт г); в последующие строки выведите список этих
ребер;
в качестве ответа на пункт д) выведите количество ребер, которые следует
добавить в исходный граф, а далее выведите сами эти ребра.
Ребра задаются указанием номеров своих концевых вершин, а при выводе
ответа на пункт г) должна быть указана их ориентация (вначале выводится
номер начальной вершины, затем – номер конечной). Если ответ на пункт
а) отличен от единицы, то пункты в) и г) решать не следует и ответы на них не
выводятся. Баллы за пункт в) в случае утвердительного ответа на него
начисляются лишь в том случае, если программа правильным образом
ориентировала ребра графа (пункт г).
Пример входного файла
4
1 2
2 4
3 4
4 1
Пример выходного файла
1
1
3 4
NOT POSSIBLE
3
1 2
2 4
4 1
1
1 3
Решение
Скачать архив тестов и решений
Ребро, удаление которого увеличивает число компонент связности графа,
называется мостом. Если граф не содержит мостов, то он называется реберно-двусвязным. Ясно, что произвольный связный граф разбивается на компоненты
реберной двусвязности (т.е. максимальные реберно-двусвязные подграфы),
соединенные мостами [Емеличев 90, п. 34]. При этом каждая вершина
принадлежит в точности одной компоненте и каждое ребро, не являющееся
мостом, входит только в одну компоненту. Описанное разбиение графа может
быть осуществлено с помощью обхода в глубину, аналогично поиску обычных
компонент двусвязности графа [Липский 88, п. 2.6].
Понятно и то, что граф, содержащий мост, нельзя ориентировать требуемым в пункте в) способом. С другой стороны, любой реберно-двусвязный граф ориентировать таким образом можно. Для этого нужно выполнить обход в глубину из произвольной вершины r, ориентируя все ребра графа, принадлежащие глубинному остовному дереву, по направлению от r, а все ребра, ему не принадлежащие, – по направлению к r. (Докажите, что полученный граф будет сильно связным.) Таким образом, ответ на пункт в) положителен в том и только том случае, когда граф не содержит мостов.
Теперь ясно, что в пункте г) нужно ориентировать все реберно-двусвязные компоненты, а все мосты оставить неориентированными. Следовательно, пункты а)-г) могут быть решены все вместе сравнительно простой модификацией обхода в глубину.
Перейдем теперь к менее очевидному пункту д). Пусть заданный граф связен. Будем рассматривать его структуру «с точностью до реберно-двусвязных компонент», стянув каждую такую компоненту в одну новую «супервершину». При этом мы получим связный ациклический граф, т.е., попросту говоря, дерево (эта процедура стягивания компонент очень похожа на построение конденсации графа [Кристофидес 78, п. 2.3]). Обозначим через k количество висячих (т.е. степени 1) вершин этого дерева. Процесс добавления к исходному графу ребер требуемым в пункте д) способом можно мыслить как добавление ребер к рассматриваемому дереву. Поскольку в итоге не должно остаться ни одной висячей вершины, то к графу необходимо добавить не менее [k/2] ребер.
С другой стороны, такого количества ребер достаточно. Докажем это.
Утверждение очевидно для деревьев с k = 2 и k = 3. Рассмотрим теперь
добавление к дереву с k > 3 ребра, соединяющего две его висячие вершины u и
v. После добавления образуется граф с одним циклом (т.е. реберно-двусвязной
компонентой), который мы также стянем, получив новое дерево. Если вершина,
полученная в результате этого стягивания, в новом дереве не является висячей,
значит добавленное ребро уменьшило количество висячих вершин на две. В
противном случае назовем висячую вершину v плохой для u (а вершину u –
плохой для v), и для сокращения числа висячих вершин на две нам следует
искать другую пару (u, v). Однако оказывается, что для каждой висячей
вершины u может существовать не более одной плохой висячей вершины v
(покажите это).
Таким образом, всегда можно добавить ребро, уменьшающее число висячих
вершин на две. Это завершает доказательство сформулированного утверждения.
Случай, когда исходный граф несвязен, разбирается аналогично.
