Циклы в графах
© Захаров С.В., 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;