Задача про графы и остовы. Опции

[Ola]

Среди всех остовов заданного графа найти остов с минимальным количеством листьев. Помогите, пожалуйста. Срочно.

[trminator]

Можно уточнить? Остов = остовное дерево? (скорее всегго, да, но мало ли...)

[Ola]

Можно уточнить? Остов = остовное дерево? (скорее всегго, да, но мало ли...)

Да, действительно, остов=остовное дерево. Здесь надо использовать рекурсивный алгоритм обхода графа (DFS-алгоритм).

[Ola]

Может у кого-нибудь есть этот DFS-алгоритм, написанный на Паскале? Потому что у меня только в схематичном виде, если можно так выразиться. И кое-что там не понятно. Привожу его:

procedure DFS(u,v);
begin
inc(k); num[u]:=k;
for  ??? w принадлежит Adj(u) (цикл по всем вершинам w, смежным с вершиной u) do
if num[w]=0 then
begin
??? T:=T U (u,w);
  DFS(w,u);
end
else if (w<>v) and num[w]<num[u] then
  ??? B:=B U (u,w);
num:=0;k:=0;
for  ??? v принадлежит V (цикл по всем элементам множества) do
if num[v]=0 then DFS(v,0);
end;

где num[v]={0, если в вершине еще не были;
u>0 - номер по порядку в процессе обхода вершин графа.}
T - ребра, образующие остов.
В - ребра, не входящие в остов графа - хорды.
k - счетчик.
Объясните, пожалуйста.

Сообщение отредактировано: volvo - 17.12.2004 14:41