Автор: Ola 4.10.2003 12:12
Среди всех остовов заданного графа найти остов с минимальным количеством листьев. Помогите, пожалуйста. Срочно.
Автор: trminator 5.10.2003 22:12
Можно уточнить? Остов = остовное дерево? (скорее всегго, да, но мало ли...)
Автор: Ola 11.10.2003 11:03
Цитата
Можно уточнить? Остов = остовное дерево? (скорее всегго, да, но мало ли...)
Да, действительно, остов=остовное дерево. Здесь надо использовать рекурсивный алгоритм обхода графа (DFS-алгоритм).
Автор: Ola 25.10.2003 12:51
Может у кого-нибудь есть этот 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 - счетчик.
Объясните, пожалуйста.