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

Это сообщение отредактировал(а) Kud - 30.4.2005, 16:24

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

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

Цитата

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

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

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

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

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

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

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

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

by HeaDacHe

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

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