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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
#1

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

03.04.2013, 15:50. Просмотров 1010. Ответов 7

Народ, мне не нужен ваш код, мне нужна только идея решения.
Задача такая:
Количество вершин в графе < 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 минуты
тема актуальна)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.04.2013, 15:50
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Достроение до сильно связного орграфа (C++):

Я очень сильно запустил свой ПК,посоветуйте что нибудь т.к. очень сильно тормозит - C++
Сильно запустил свой ПК,при включении приходится ждать около часа чтобы не лагал так сильно,при переустановке Windows лагает также

Центр орграфа, классы - C++
помогите с конструктором и деструктором) Дан файл, первой строкой в файле является размерность матрицы, остальное является самой...

Компоненты сильной связности орграфа - C++
#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;string&gt; #include &lt;algorithm&gt; using namespace std; void search_depth(int v,...

Вычисление сильных компонент орграфа. Алгоритм Габова. - C++
Помогите, пожалуйста, найти инфу по этой теме. В интернете никак не могу отыскать, а если и нахожу, то очень мало :wall: Скинте ссылки...

Вывести на экран вершины орграфа, смежные с данной - C++
Уффф, к завтрашнему дню нужно сдать эти задачи, помогите пожалуйста кто чем сможет :sorry: (следующие задачи через обходы в глубину и...

Существует ли путь из a в b через одну вершину орграфа? - C++
я сделал класс графа. нужно теперь решить такое задание. написать булевскую функцию. помогите, кто знает class Graph{ ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 443
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
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
05.04.2013, 16:11  [ТС] #3
kamre, Я прочитал все сообщения на тех форумах, но не понял главного -- какие именно дуги ставить (как узнать какие дуги нужно доставить).
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 443
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
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
05.04.2013, 19:56  [ТС] #5
kamre, это для связанного графа, у нас не связанный изначально
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 443
05.04.2013, 20:27 #6
Цитата Сообщение от Ternsip Посмотреть сообщение
у нас не связанный изначально
А какие именно проблемы возникают для не связного DAG? Можно на конкретном примере?

Единственное, что приходит на ум - это изолированные вершины, т.к. они одновременно являются и стоками и истоками. Для таких вершин можно в двудольный граф добавлять две вершины в разные доли и ребро между ними, при этом ребро всегда будет входить в максимальное паросочетание.
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
А тот вариант вроде так не разбивает и остаются не связанные компоненты, вроде.
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 443
06.04.2013, 12:15 #8
Цитата Сообщение от Ternsip Посмотреть сообщение
тот вариант вроде так не разбивает и остаются не связанные компоненты
Как это не разбивает? Именно построение этих ребер и описано в алгоритме выше.

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

Вершину 10 можно разбить на две как я описывал выше и встроить в двудольный граф и его паросочетание, после этого и с ней будут добавлены ребра по алгоритму.
Миниатюры
Достроение до сильно связного орграфа  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.04.2013, 12:15
Привет! Вот еще темы с ответами:

Вывести на экран вершины орграфа, смежные с данной - C++
Вывести на экран те вершины орграфа, смежные с данной, т.е. вывести &quot;входящие&quot; и &quot;выходящие&quot; соседние вершины, но моя программа выводит...

сортировка связного списка - C++
Привет всем! пришлите пожалуйста код реализации сортировки односвязного списка (желательно с комментарием)! а то у меня совсем ничего...

Создание связного списка - C++
нужно создать связной список, что собственно уже сделал. что нужно: -функции: -root (выводит список) -push (+1 елемент в...

Сортировка связного списка - C++
Привет всем! как правильно написать сортировку для связного циклического списка ? помогите пожалуйста... #include &lt;iostream&gt; using...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
06.04.2013, 12:15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru