Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Достроение до связного полностью графа

Автор: Kud 30.4.2005, 16:09

Есть граф. ориентированный. Необходимо добавить минимальное количество ребер что бы из каждой вершины был доступ к каждой. Ну т.е. что бы матрица смежности была вся в единичках =) кроме главной диагонали.

Автор: maxim1000 30.4.2005, 17:45

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

Автор: Kud 30.4.2005, 21:54

Этот алгоритм не пройдет т.к. граф ориентированный. просто соеденить с любой это не правильно.

Автор: maxim1000 30.4.2005, 23:00

Цитата

граф ориентированный

упс... не заметил...

Автор: maxim1000 30.4.2005, 23:18

ну один вариант есть:
просто выписываем все несоединенные пары вершин - кандидаты на добавление в список ребер
пусть их M (в общем случае можно считать, что оно пропорционально n^2, где n - количество всех вершин)
из них нужно выбрать минимальное подмножество, которое решает задачу
перебор получается немаленький
можно воспользоваться динамическим программированием, тогда сложность будет порядка M^2 (n^4)
но что-то мне это не нравится... n^4 - как-то слишком...

Автор: Kud 1.5.2005, 00:05

Цитата(maxim1000 @ 30.4.2005, 23:18)

можно воспользоваться динамическим программированием, тогда сложность будет порядка M^2 (n^4)
но что-то мне это не нравится... n^4 - как-то слишком...

а можно поподробней с этого места? А то что-то посидел ... ничего в голову не пришло =(

Автор: Kud 1.5.2005, 01:24

У нас (на локальномфоруме) предложили такое решение: по мойму оно правильное. =)

Стягиваем ССК в вершины.
Теперь нужно сделать граф такой, чтобы из каждой вершины выходила и входила хотя бы одна дуга и при этом он был одной компонентой связности. Поэтому вначале проводим дуги от вершин, из которых ничего не выходит к вершинам, в которые ничего не входит из разных компонент связности. Если после этого у нас осталось K компонет связности, то добавляем K дуг, причем по возможности для каждой компоненты связности вводим дугу в вершину, в которую не входит ни одна дуга и выводим из вершин, из которых не выходит. Пусть теперь мы объединили все компоненты связности и у нас осталось a вершин, из которых не выходит дуг и b вершин, в которые не входят дуги. Тогда соединяем их попарно min{a, b} дугами, оставшиеся a + b - 2*min{a, b} вершин присоединяем к любым вершинам, т.е. в этом случае всего добавляем max{a ,b} дуг.

by HeaDacHe

Автор: poor_yorik 8.5.2005, 14:47

Kud ты понимаешь, граф может и не иметь вершин, из которых только выходят или только входят дуги. Хотя он и не будет сильно связным. Идея у тебя хорошая, но я предлягаю ее чуть-чуть улучшить.
Вначале найди все компоненты сильной связности по такому типу. Формируешь для каждой вершины А поиском в глубину вершины два множества S и Q. Множество S будет содержать все вершины в которые можно попасть из А, а множество Q будет содержать все вершины, из которых можно будет попасть в А. Пересечением множеств S и Q и будет комонента сильной связности, которая содержит вершину А. Так находишь все компоненты связности.
Далее строишь граф G таким образом. Вершины в нем обозначают компоненты связности графа, и если из одной компоненты связности можно попасть в другую, то значит в графе G будет дуга между вершинами, соответствующими данным компонентам связности. smile

А уже в полученном графе G испробуй свой алгоритм. Скорее всего заработает. smile

Автор: Прохожая 23.5.2005, 12:47

Ребята, есть такой замечательный сайт - http://www.belsky.narod.ru/
там выложен курс лекций и по графам тоже, и алгоритмы есть. поищите, вдруг поможет smile

!
искать в разделе МАТЕМАТИКА