На главную страницу

В начало

Циклы в графах

© Захаров С.В., 2002 г.
Все приведённые в статье алгоритмы являются общеНАРОДным достоянием. Разрешается свободное их использование.

Вхождение атома в состав небольшого цикла (3-7 - членного) сильно влияет на его свойства (на прочность связей, частоты их колебаний, вклад в молекулярную рефракцию, и, конечно, на химическую активность). При этом чем более напряжён цикл (чем меньше атомов входит в его состав), тем больше изменяются свойства атомов, входящих в него, связей, образуемых ими, и соседних с ними атомов и химических групп.

Вхождение атома в трёхчленный цикл в наибольшей степени влияет на свойства молекулы. Ниже приводится функция (Delphi), проверяющая, входит ли вершина Top графа Graph в состав трёхчленного цикла:

// Определяет, входит ли вершина Top графа Graph в
// трёхчленный цикл.
function IsCycle3(Graph: TMathGraph; Top: Integer): Boolean;
var
 i,j,n: Integer;
begin
 Result:=False;
 n:=Graph.TopCount-1;
 if (Top<0) or (Top>n) then Exit;
 for i:=0 to n do
 begin
  if (i<>Top) and (Graph.Connected[i,Top]) then
  begin
   for j:=i+1 to n do
   begin
    if (j<>Top) and (Graph.Connected[i,j]) and (Graph.Connected[j,Top]) then
    begin
     Result:=True;
     Exit;
    end;
   end;
  end;
 end;
end;

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

// Определяет, входит ли вершина Top графа Graph в состав цикла.
function IsCycle(Graph: TMathGraph; Top: Integer): Boolean;
var
 i,j,n: Integer;
 strMark: string;
begin
 Result:=False;
 n:=Graph.TopCount-1;
 if (Top<0) or (Top>n) then Exit;
 for i:=0 to n do strMark:=strMark+'v';
 for i:=0 to n do
 begin
  if (i=Top) or (not Graph.Connected[i,Top]) then Continue;
  for j:=0 to n do strMark[j]:='v';
  strMark[Top]:='m';
  MarkSubgraphViaRecursion(Graph,i,n,strMark);
  for j:=0 to n do if (j<>Top) and (j<>i) and (strMark[j]='m')
   and (Graph.Connected[j,Top]) then begin Result:=True; Exit; end;
 end;
end;

Следующая функция определяет минимальный размер цикла, в который входит связь между вершинами Top1 и Top2. Если вершины не связаны или связь не входит в состав цикла, функция возвращает -1:

function GetCycleSizeWithBond(Graph: TMathGraph;
 Top1: Integer; Top2: Integer): Integer;
var
 i,j,k,n: Integer;
 p,p1: ^Integer;
 Lst: TList;
begin
 n:=Graph.TopCount-1;
 Result:=n+1;
 if not Graph.Connected[Top1,Top2] then begin Result:=-1; Exit; end;
 Lst:=TList.Create;
 AddIntegersToLst(Lst,n+1,n+1);
 p:=Lst[Top1];
 p^:=0;
 for k:=1 to n do
 begin
  for i:=0 to n do
  begin
   p:=Lst[i];
   if (p^<k) or (i=Top2) then Continue;
   for j:=0 to n do
   begin
    if (i=j) or (not Graph.Connected[i,j]) or (j=Top2) then Continue;
    p1:=Lst[j];
    if (p^>k) and (p1^+1=k) then
    begin
     p^:=k;
    end;
   end;
  end;
 end;
 for i:=0 to n do
 begin
  if (i<>Top1) and (i<>Top2) and (Graph.Connected[i,Top2]) then
  begin
   p:=Lst[i];
   if Result>p^ then Result:=p^;
  end;
 end;
 if Result=n+1 then Result:=-1 else Result:=Result+2;
 DisposeLst(Lst); Lst.Free;
end;

А следующая функция, использующая предыдущую, определяет минимальный размер цикла, в который входит вершина Top. Если указанная вершина не входит в цикл, функция возвращает -1:

function GetCycleSizeWithTop(Graph: TMathGraph; Top: Integer): Integer;
var
 i,k,n: Integer;
begin
 n:=Graph.TopCount-1;
 Result:=n+2;
 for i:=0 to n do
 begin
  if (i<>Top) and (Graph.Connected[i,Top]) then
  begin
   k:=GetCycleSizeWithBond(Graph,Top,i);
   if (k<>-1) and (k<Result) then Result:=k;
  end;
 end;
 if Result=n+2 then Result:=-1;
end;

В начало

На главную страницу