|
Название задачи: Ориентация графа . |
 |
Условие
Задан неориентированный граф с 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
(покажите это).
Таким образом, всегда можно добавить ребро, уменьшающее число висячих
вершин на две. Это завершает доказательство сформулированного утверждения.
Случай, когда исходный граф несвязен, разбирается аналогично.
