Теория графов.Оргдеревья., Разбиение оргдеревьев. Опции

[Fanat]

Как разбить ориентированное дерево на все неизоморфные поддеревья?..Входные данные-например,FO представление.

[Michael_Rybak]

Идем от листов вверх к корню, и индексируем по ходу.

Лучше сразу на примере:



Берем листья: F, G, H, I, K, L, M, N. Присваиваем каждому из них индекс 0. Между собой соответствующие поддеревья изоморфны, и других таких нет.

Теперь рассматриваем узел, у которого все сыновья проиндексированы, а он - нет. Например E. Записываем индексы его сыновей: G(0), H(0); сортируем индексы: (0; 0). Смотрим, есть ли у нас такое поддерево среди рассмотренных? Нету. Значит, это - новое, даем ему индекс 1. Ведем такую табличку:

0: ()
1: (0; 0)

Берем следующий узел с проиндексированными сыновьями, например B. Записываем его детей: E(1), F(0); сортируем индексы: (0; 1). Такого еще не было, даем индекс 2:

0: ()
1: (0; 0)
2: (0; 1)

Дальше. Узел C. Дети: M(0), N(0). Сортируем индексы: (0; 0). Это у нас уже было. Это - индекс 1.

Узел J. Дети: K(0), L(0). Сортируем индексы: (0; 0). Это у нас уже было. Это - индекс 1.

Узел D. Дети: I(0), J(1). Сортируем индексы: (0; 1). Это у нас уже было. Это - индекс 2.

Узел А. Дети: B(2), C(1), D(2). Сортируем индексы: (1; 2; 2). Такого еще не было, это будет индекс 3:

0: ()
1: (0; 0)
2: (0; 1)
3: (1; 2; 2)

Таким образом, в дереве есть 4 вида неизоморфных поддеревьев, и корням изоморных поддеревьев поставлены в соответствие одинаковые индексы.

Чтобы делать это за n log n, можно строить префиксное дерево для списка полученных индексов (в котором, например, путь 1-2-2 оканчивается значением 3)

[Fanat]

Требуеться разбить на ВСЕ неизоморфные поддеревья.
Алгоритм:
Нахождение и удаление висячих вершин.
Проверка на изоморфность оргдеревьев.

Только вот с реализациеё чето у меня не особо. Даже списковое представление сделать не получаеться.

[Michael_Rybak]

Требуеться разбить на ВСЕ неизоморфные поддеревья.

А я и написал тебе, как разбить на ВСЕ неизоморфные поддеревья.

А если нет - тогда потрудись объяснить, что значит "разбить", и приведи пример входа и выхода для требуемого алгоритма. И лучше - несколько примеров.

[Fanat]

Например,рассмотрим такое огрдерево.


Дерево имеет 4 неизоморфных поддерева.
Приведено их FO представление.

Код

program 1;
uses crt;
type ptr=^elem;
     elem=record
     num:integer;
     next:ptr;
     end;
  vector=array[1..100] of ptr;
var an,k,ak:ptr;
      ch:integer;
      num,kol,nom:integer;
      f:text;
      s:char;
      i,n,j:integer;
      zap,zap1:vector;

  procedure del_list(var an:ptr);
      begin
     an:=nil;
      end;

  procedure add_begin(var an:ptr;num:integer);
      var k:ptr;
      begin
    new(k);
    k^.next:=an;
    k^.num:=num;
    an:=k;
      end;

     procedure add_end(var an:ptr;num:integer);
       var k:ptr;
    begin
    new(k);
    k^.next:=nil;
    k^.num:=num;
    an^.next:=k;
     end;

   procedure beg_list(var an:ptr;var k:ptr);
     begin
       k:=an;
     end;
   procedure end_list(var an:ptr;var k:ptr);
     begin
       k:=nil;
     end;


    procedure next(var k:ptr;var ch:integer);
       begin
     ch:=k^.next^.num;
       end;

   procedure take_beg(an:ptr;var ch:integer);
    begin
    ch:=an^.num;
       end;


begin
repeat
clrscr;
assign(f,'1.txt');
i:=1;

    reset(f);
    read(f,kol);
    for i:=1 to kol
    do
    begin
    del_list(zap[i]);
    add_begin(zap[i],i);
    beg_list(zap[i],an)
    end;
    i:=1;
    while not eof(f) do
          begin
         read(f,num);
         write(' ',num);
         if num=0 then i:=i+1
            else
         add_end(zap[i],num);
          end;
writeln;

write(zap[1]^.num,'  ');
write(zap[1]^.next^.num,'   ');
writeln(zap[1]^.next^.next^.num);
writeln;
  writeln('Xotite povtoprit? Y/N');
  until readkey='n';
end.

В этом коде создаем списковое представление дерева.Просьба подправить, так как оно создаётся неверно.
Что-то со ссылками.Напиример в рассмотреном нами дереве результат будет 1 4 268 вместо должного 1 2 4.

Сообщение отредактировано: Fanat - 6.11.2006 21:00

[Michael_Rybak]

Приведи, пожалуйста, определения "FO представление" и "ориентированное дерево"