Алгоритм

← →
asdqwer (2003-12-28 19:40) [0]

Нигде не встретил алгоритм поиска наибольшего полного подграфа данного графа (полный граф - это тот, у которого соединены любые две вершины). Заранее спасибо.

← →
SergP (2003-12-28 23:27) [1]

Я прикинул. Получается нечто типа:

type subgraf:array[1..N] of integer;
...
var
n:integer;
s:array [1..N,1..N] of boolean;
k,m:subgraf;
// s[a,b]=true если вершины a и b соединены, иначе false
// n - кол. вершин графа
...
procedure SearchMaxSubgraph;
begin
k[0]:=1;
m[0]:=1;
fs(1);
// после выполнения процедуры в m[0] имеем размерность
// макссубграфа, а в m[1]...m[m[0]] номера вершин исходного
// графа, которые входят в субграф.
end;
...
procedure fs(r:integer);
var
u:integer;
x:boolean;
begin
if r<=n then
begin
for u:=r to n do // перебираем все оставшиеся вершины
begin
x:=true;
for i:=1 to k[0] do if not s[k[i],u] then x:=false;
// устанавливаем x в false если эту вершину нельзя добавить
// в уже найденый субграф
if x then
begin
inc(k[0]); // если вершина подходит, то добавляем ее.
k[k[0]]:=u;
if k[0]>m[0] then m:=k; // если найденый субграф больше
//предыдущего найденого то запоминаем его
fs(u+1);// рекурсивный вызов функции для дальнейшего поиска
dec(k[0]); // возвращаемся к предыдущему субграфу для
//проверки его со следующими вершинами
end;
end;
end;
end;

Только я не проверял, а писал прямо в форум. Так что кое-что придется подправить. Код может быть немного неправильным и неоптимальным, но здесь главное натолкнуть тебя на мысль.

← →
SergP (2003-12-28 23:37) [2]

Надеюсь что код сам подправишь...

Кстати даже если окажется что я где-то ошибся, то все равно хорошо что что-то написал. Так как щас кто-нить будет меня критиковать за то что неправильно написали и предлагать свой код, а иначе бы просто никто не ответил и ветка бы "ушла в никуда". :-)))

← →
asdqwer (2003-12-29 08:48) [3]

Большое спасибо, SergP, однако сложность данного алгоритма довольно велика: O(n^n). Хотелось бы порядка O(n^3).

← →
SergP (2003-12-29 09:32) [4]

> asdqwer (29.12.03 08:48) [3]
> Большое спасибо, SergP, однако сложность данного алгоритма
> довольно велика: O(n^n). Хотелось бы порядка O(n^3).

Мне просто не приходилось заниматься графами. Да и этот кусок проги я прикинул просто из-за интереса к всякого рода подобным задачкам...

И хотя я немогу оценить сложность моего алгоритма. Но мне кажется что она все-таки не O(n^n), а поменьше будет.

← →
SergP (2003-12-29 11:00) [5]

Тут я еще вот о чем подумал:

1.Допустим имеется массив описывающий граф:
...1.2.3.4.5.6.7.8
-|-----------------
1|
2|.T
3|.T.F
4|.T.T.F
5|.T.F.T.T
6|.T.T.T.T.F
7|.T.T.T.T.T.T
8|.F.T.T.T.T.T.T

2.Выбираем из указаной части масива элементы F (false):

Получаем:
(8 , 1)
(5 , 2)
(3 , 2)
(4 , 3)
(6 , 5)

3.Теперь из каждой пары чисел нам нужно выкинуть не менее одного, так чтобы при этом в общем выкинуть минимальное количество чисел.

В данном примере выкидываем 8 , 3 , 5. Значит подграф с оставшимися вершинами 1,2,4,6,7 является наибольшим полным подграфом нашего графа.

Вот только не знаю как реализовать сам алгоритм для этого, вернее для 3-го пункта.

← →
DAC (2003-12-29 11:54) [6]

Данная задача является классической задачей теории сложности. Носит название "Задача клика". Доказано, что она NPC-задача. На данный момент представляется маловероятным найти полиномиальный алгоритм её решения (врядли можно надеятся на оценку O(n^3)). Для получения более полной информации об этой задаче рекомендую обратиться к книжке М. Гэри, Д. Джонсон "Вычислительные машины и труднорешаемые задачи".

← →
SergP (2003-12-29 16:21) [7]

2 asdqwer:

Попробуй спросить об алгоритме здесь:
http://algolist.manual.ru/forum/
Может там тебе помогут. Как раз это форум с как бы это сказать - "математическим уклоном"..

Алгоритм Найти похожие ветки