Форум программистов, компьютерный форум CyberForum.ru

Достроение до сильно связного орграфа - C++

Восстановить пароль Регистрация
 
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
03.04.2013, 15:50     Достроение до сильно связного орграфа #1
Народ, мне не нужен ваш код, мне нужна только идея решения.
Задача такая:
Количество вершин в графе < 200
Задан ориентированный граф G. Требуется добавить в него наименьшее количество дуг так, чтобы он стал сильно связным (то есть чтобы из любой вершины существовал путь в любую другую).
Возможно, что связанно с конденсацией графа и обходом в глубину)
Я сначала думал, что если сконденсировать граф, потом, просто, глубиной узнать, в какие вершины нужно запихать дугу и из каких нужно выпускать, но дальше нет идеи как соединять их так, чтобы их кол-во было min
Пример:
Ввод
4 4 //n = 4 m = 4
// m строк с описанием дуг
1 2
2 3
3 4
2 3
Выход
1 //(1 дуга)
4 1 //(из 4 в 1)

Добавлено через 54 минуты
тема актуальна)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 438
04.04.2013, 05:03     Достроение до сильно связного орграфа #2
Цитата Сообщение от Ternsip Посмотреть сообщение
Задан ориентированный граф G. Требуется добавить в него наименьшее количество дуг так, чтобы он стал сильно связным (то есть чтобы из любой вершины существовал путь в любую другую).
http://stackoverflow.com/questions/1...onnected-graph

Добавлено через 8 часов 1 минуту
Вот еще ссылка: http://stackoverflow.com/questions/1...nts-from-a-dag
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
05.04.2013, 16:11  [ТС]     Достроение до сильно связного орграфа #3
kamre, Я прочитал все сообщения на тех форумах, но не понял главного -- какие именно дуги ставить (как узнать какие дуги нужно доставить).
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 438
05.04.2013, 18:49     Достроение до сильно связного орграфа #4
Цитата Сообщение от Ternsip Посмотреть сообщение
не понял главного -- какие именно дуги ставить
По второй ссылке написано какие именно дуги нужно добавлять в DAG, чтобы получить из него сильно связную компоненту:
Assuming there are no isolated vertices in the graph you only need to add max(|sources|,|sinks|) edges to make it strongly connected.

Let T={t1,…,tn} be the sinks and {s1,…,sm} be the sources of the DAG. Assume that n <= m. (The other case is very similar). Consider a bipartite graph G(T,S) between the two sets defined as follows. G(T,S) has an edge (ti,sj) if and only if ti can be reached from sj.

Let M be a maximal matching in G(T,S). Without loss of generality assume that M consists of k edges: {(t1,s1),(t2,s2),…,(tk,sk)}. In the original graph DAG G, add directed-edges {(t1->s2),(t2->s3),…,(tk−1->sk),(tk->s1)}. It's easy to see that by adding these edges, the vertices induced by M are strongly connected in G.

Now consider the remaining vertices in G(T,S). Because M maximal, each vertex in S−M (resp. T−M)should be connected to a vertex in T (resp. S−M). So we pair up the remaining vertices arbitrarily, say {(tk+1,sk+1),…,(tn,sn)} and add the corresponding directed edges in G. For each remaining source vertex source si (i belongs to {n+1,…,m} we add the edge (t1->si) in G. Thus the total number of edges added is max(|sources|,|sinks|).
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
05.04.2013, 19:56  [ТС]     Достроение до сильно связного орграфа #5
kamre, это для связанного графа, у нас не связанный изначально
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 438
05.04.2013, 20:27     Достроение до сильно связного орграфа #6
Цитата Сообщение от Ternsip Посмотреть сообщение
у нас не связанный изначально
А какие именно проблемы возникают для не связного DAG? Можно на конкретном примере?

Единственное, что приходит на ум - это изолированные вершины, т.к. они одновременно являются и стоками и истоками. Для таких вершин можно в двудольный граф добавлять две вершины в разные доли и ребро между ними, при этом ребро всегда будет входить в максимальное паросочетание.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
06.04.2013, 10:54  [ТС]     Достроение до сильно связного орграфа #7
kamre, тест:
17 8
1 3
2 4
5 7
6 8
9 12
11 13
14 16
15 17
Лучший вариант так: 3-2 4-5 7-6 8-9 12-11 13-14 16-15 17-1
А тот вариант вроде так не разбивает и остаются не связанные компоненты, вроде.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.04.2013, 12:15     Достроение до сильно связного орграфа
Еще ссылки по теме:

C++ Вывести на экран вершины орграфа, смежные с данной
Вывести на экран вершины орграфа, смежные с данной C++
C++ Существует ли путь из a в b через одну вершину орграфа?

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 438
06.04.2013, 12:15     Достроение до сильно связного орграфа #8
Цитата Сообщение от Ternsip Посмотреть сообщение
тот вариант вроде так не разбивает и остаются не связанные компоненты
Как это не разбивает? Именно построение этих ребер и описано в алгоритме выше.

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

Вершину 10 можно разбить на две как я описывал выше и встроить в двудольный граф и его паросочетание, после этого и с ней будут добавлены ребра по алгоритму.
Миниатюры
Достроение до сильно связного орграфа  
Yandex
Объявления
06.04.2013, 12:15     Достроение до сильно связного орграфа
Ответ Создать тему

Метки
граф, компоненты сильной связанности
Опции темы

Текущее время: 13:17. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru