Алгоритм поиска элементарных циклов в неориентированном графе

@Massaraksh7 · Регистрация: 27.05.2017

Необходимо граф разбить на элементарные циклы, то есть такие циклы, которые не имею внутри подциклов. Пример - на рисунке. Как найти все циклы в графе, я знаю. Но мне нужны не все.

@krapotkin · 23.06.2017, 07:08

вы слишком полагаетесь на глаза
если у нас действительно граф, то его можно нарисовать и вот так
и тогда все будет выглядеть по-другому

@Shamil1 · 23.06.2017, 09:42

Сообщение от krapotkin

и тогда все будет выглядеть по-другому

Но элементарные циклы те же остались.

@krapotkin · 23.06.2017, 09:49

является ли цикл 1-2-3-4-5-13-6-7-8-9-10-11 элементарным?

@Massaraksh7 · 23.06.2017, 13:07 **[ТС]**

Сообщение от krapotkin

является ли цикл 1-2-3-4-5-13-6-7-8-9-10-11 элементарным?

Да, если исходить из того, как я сформулировал, является. Но такого не будет, ибо "в реале" сам граф "формируют" геодезисты.

@Shamil1 · 23.06.2017, 13:34

Сообщение от krapotkin

является ли цикл 1-2-3-4-5-13-6-7-8-9-10-11 элементарным?

Не является, так как существует ребро (5,11), которое не в ходит в цикл и связывает две вершины из этого цикла.

Добавлено через 7 минут
Massaraksh7,
Липский. Комбинаторика для программистов.
2.5. Отыскание фундаментального множества циклов в графе. (стр.92)
Алгоритм 2.9. (стр.95)

Добавлено через 8 минут

Сообщение от Massaraksh7

Необходимо граф разбить на элементарные циклы, то есть такие циклы, которые не имею внутри подциклов.

Элементраный цикл - это цикл, который не имеет самопересечений. А то, что на картинке, называется "цикл без хорд".

@Massaraksh7 · 23.06.2017, 13:38 **[ТС]**

Сообщение от Shamil1

Липский. Комбинаторика для программистов.
2.5. Отыскание фундаментального множества циклов в графе. (стр.92)
Алгоритм 2.9. (стр.95)

Спасибо, посмотрю.

Добавлено через 2 минуты

Сообщение от Shamil1

А то, что на картинке, называется "цикл без хорд".

Цикл без хорд состоит из треугольников.

@Shamil1 · 23.06.2017, 13:40

Сообщение от Massaraksh7

Цикл без хорд состоит из треугольников.

Из вики:
Цикл без хорд в графе, также называемый дырой или порождённым циклом, — это цикл, в котором никакие две вершины цикла не соединены ребром, разве что это ребро само принадлежит циклу.

@Massaraksh7 · 23.06.2017, 14:23 **[ТС]**

Хорошо, пусть так. Тогда один из вариантов - найти все циклы, а потом из них исключить те, у которых есть подциклы. По какому принципу? Организовать обход цикла по часовой стрелке, и следить, чтобы справа не было вхождений? Ну или наоборот.

@Massaraksh7 · 25.06.2017, 16:26 **[ТС]**

Итак, продолжаем. Первым делом надо получить все существующие циклы графа, используя поиск в глубину. Для вот такого простого графа их число получается 416.

Delphi

procedure DFS(k,v:integer);
var i,j,m,i1,j1:integer;
begin
push(k);
visited[k]:=1;
for i:=0 to np-1 do
    begin
    if i=k then continue;
    if i=v then continue;
    if (visited[i]=1) and (adj[i,k]<>0) then //--если не сама с себя
       begin
       for j:=0 to t-1 do
          begin
          circles[ncl].els[j]:=stack[j];
          end;
       for j:=0 to t-1 do if stack[j]=i then break;
       for m:=j to t-1 do circles[ncl].els[m-j]:=stack[m]; //---переносим цикл из стека
       circles[ncl].els[t-j]:=i;
       circles[ncl].nel:=t-j+1;
       continue;
       end;
    if adj[i,k]<>0 then DFS(i,k);
    end;
visited[k]:=0;
pop(k);
end;

@Massaraksh7 · 25.06.2017, 16:30 **[ТС]**

Это нас не устраивает, среди циклов много повторяющихся. Поэтому при записи нового цикла мы устроим проверку: а не было ли такого цикла раньше?
Получается уже лучше, всего 13 циклов осталось.

Delphi

function CompareCircles(i1,i2:integer):Boolean;
var i,j,k:integer;
begin
Result:=False;
if circles[i1].nel<>circles[i2].nel then exit;
k:=0;
for i:=0 to circles[i1].nel-2 do
   begin
   for j:=0 to circles[i2].nel-2 do
      begin
      if circles[i1].els[i]=circles[i2].els[j] then k:=k+1;
      end;
   end;
if k=(circles[i1].nel-1) then Result:=True;
end;
 
procedure push(k:integer);
begin
stack[t]:=k;t:=t+1;
end;
 
procedure pop(k:integer);
begin
t:=t-1;
end;
 
procedure DFS(k,v:integer);
var i,j,m,i1,j1:integer;
begin
push(k);
visited[k]:=1;
for i:=0 to np-1 do
    begin
    if i=k then continue;
    if i=v then continue;
    if (visited[i]=1) and (adj[i,k]<>0) then //--если не сама с себя
       begin
       for j:=0 to t-1 do
          begin
          circles[ncl].els[j]:=stack[j];
          end;
       for j:=0 to t-1 do if stack[j]=i then break;
       for m:=j to t-1 do circles[ncl].els[m-j]:=stack[m]; //---переносим цикл из стека
       circles[ncl].els[t-j]:=i;
       circles[ncl].nel:=t-j+1;
//-------------проверка, а может такой цикл уже есть?
       j1:=0;
       for i1:=0 to ncl-1 do
          begin
          if CompareCircles(i1,ncl)=True then begin j1:=1;break;end;
          end;
       continue;
       end;
    if adj[i,k]<>0 then DFS(i,k);
    end;
visited[k]:=0;
pop(k);
end;

@Massaraksh7 · 25.06.2017, 16:38 **[ТС]**

Но ещё остались циклы внутренними хордами, которые нам не нужны. Поэтому мы устраиваем проверку на них. Делаем это так: определяем направление цикла - по часовой, или против? Для этого находим сумму произведений x[i]*y[i+1]-x[i+1]*y[i] для каждого узла, и, в зависимости от знака, оставляем цикл как есть, или меняем его порядок. После этого проходимся по циклу, и для каждого узла определяем, а нет ответвляется ли вправо ребро, не являющееся частью его оболочки? После этого получаем то, что нам было нужно.
Полный алгоритм на Delphi:

Delphi

var np:integer;  // число узлов графа
var xa,ya:array [0..100] of integer;  // координаты узлов
adj:array [0..100,0..100] of integer; // матрица сопряжений
stack,visited:array [0..100] of integer; // стек для поиска в глубину
seg:array [0..1,0..100] of integer;nseg:integer; // массив ребер графа
 
type TCircle=record
             els:array [0..100] of integer;
             nel:integer;
             end;
var circles:array [0..100] of TCircle; // массив найденных циклов графа
ncl:integer; // число найденных циклов графа
t:integer; // переменная стека
 
function CompareCircles(i1,i2:integer):Boolean;
var i,j,k:integer;
begin
Result:=False;
if circles[i1].nel<>circles[i2].nel then exit;
k:=0;
for i:=0 to circles[i1].nel-2 do
   begin
   for j:=0 to circles[i2].nel-2 do
      begin
      if circles[i1].els[i]=circles[i2].els[j] then k:=k+1;
      end;
   end;
if k=(circles[i1].nel-1) then Result:=True;
end;
 
function ILeftOrRight(x0,y0,x1,y1,x2,y2:integer):integer;
begin
Result:=(x1-x0)*(y2-y1)-(y1-y0)*(x2-x1);
end;
 
function IsHorderCircle(n:integer):Boolean;
var i,j,d,k,i1,i2:integer;
begin
d:=0;
for i:=0 to circles[n].nel-2 do
   begin
   d:=d+xa[circles[n].els[i]]*ya[circles[n].els[i+1]]-xa[circles[n].els[i+1]]*ya[circles[n].els[i]];
   end;
d:=sign(d); // -1 - против, =1 - по  (или наоборот)
//---------Если против часовой стрелки, поменять направление
if d<0 then
   begin
   for i:=0 to circles[n].nel div 2 - 1 do
      begin
      k:=circles[n].els[i];
      circles[n].els[i]:=circles[n].els[circles[n].nel-1-i];
      circles[n].els[circles[n].nel-1-i]:=k;
      end;
   end;
//---------Обход по часовой, проверка ответвлений вправо
circles[n].els[circles[n].nel]:=circles[n].els[1];  //--Добавляем ещё один элемент в цикл
for i:=0 to circles[n].nel-2 do
   begin
   for j:=0 to np-1 do  //---поиск сопряжённых точек
      begin
      if (adj[circles[n].els[i+1],j]=1) and (j<>circles[n].els[i]) and (j<>circles[n].els[i+1]) and (j<>circles[n].els[i+2]) then
         begin
         i1:=ILeftOrRight(xa[circles[n].els[i]],ya[circles[n].els[i]],xa[circles[n].els[i+1]],ya[circles[n].els[i+1]],xa[j],ya[j]);
         i2:=ILeftOrRight(xa[circles[n].els[i+1]],ya[circles[n].els[i+1]],xa[circles[n].els[i+2]],ya[circles[n].els[i+2]],xa[j],ya[j]);
         if (i1>0) and (i2>0) then begin Result:=true;exit;end;
         end;
      end;
   end;
IntToStr(n);
Result:=False;
end;
 
procedure push(k:integer);
begin
stack[t]:=k;t:=t+1;
end;
 
procedure pop(k:integer);
begin
t:=t-1;
end;
 
procedure DFS(k,v:integer);
var i,j,m,i1,j1:integer;
begin
push(k);
visited[k]:=1;
for i:=0 to np-1 do
    begin
    if i=k then continue;
    if i=v then continue;
    if (visited[i]=1) and (adj[i,k]<>0) then //--если не сама с себя
       begin
       for j:=0 to t-1 do
          begin
          circles[ncl].els[j]:=stack[j];
          end;
       for j:=0 to t-1 do if stack[j]=i then break;
       for m:=j to t-1 do circles[ncl].els[m-j]:=stack[m]; //---переносим цикл из стека
       circles[ncl].els[t-j]:=i;
       circles[ncl].nel:=t-j+1;
//-------------проверка, а может такой цикл уже есть?
       j1:=0;
       for i1:=0 to ncl-1 do
          begin
          if CompareCircles(i1,ncl)=True then begin j1:=1;break;end;
          end;
//-------------проверка, цикл с внутренними хордами?
       if IsHorderCircle(ncl)=True then j1:=1;
       if j1=0 then ncl:=ncl+1; //--Если такого цикла не было, то добавляем, иначе - нет
       continue;
       end;
    if adj[i,k]<>0 then DFS(i,k);
    end;
visited[k]:=0;
pop(k);
end;
 
procedure TForm13.Button2Click(Sender: TObject);
var i,j,k:integer;
begin
//----------Сформировать adj
for i:=0 to 100 do for j:=0 to 100 do adj[i,j]:=0;
for i:=0 to nseg-1 do
   begin
   adj[seg[0,i],seg[1,i]]:=1;
   adj[seg[1,i],seg[0,i]]:=1;
   end;
//----------Запустить DFS
t:=0;ncl:=0;
for i:=0 to np-1 do visited[i]:=0;
for i:=0 to np-1 do
   begin
   if visited[i]=0 then DFS(i,-1);
   end;
for i:=0 to ncl-1 do begin Draw(i*100,300);DrawCircles(i,i*100,300);end;
end;

Просьба к модераторам, в названии темы заменить слово "элементарных циклов" на "циклов без хорд".

@Massaraksh7 · 25.06.2017, 17:19 **[ТС]**

---

@Massaraksh7 · 25.06.2017, 19:03 **[ТС]**

Поправка: более надёжное определение внутренних хорд через дирекционные углы.

Delphi

var np:integer;  // число узлов графа
var xa,ya:array [0..100] of integer;  // координаты узлов
adj:array [0..100,0..100] of integer; // матрица сопряжений
stack,visited:array [0..100] of integer; // стек для поиска в глубину
seg:array [0..1,0..100] of integer;nseg:integer; // массив ребер графа
 
type TCircle=record
             els:array [0..100] of integer;
             nel:integer;
             end;
var circles:array [0..100] of TCircle; // массив найденных циклов графа
ncl:integer; // число найденных циклов графа
t:integer; // переменная стека
 
function CompareCircles(i1,i2:integer):Boolean;
var i,j,k:integer;
begin
Result:=False;
if circles[i1].nel<>circles[i2].nel then exit;
k:=0;
for i:=0 to circles[i1].nel-2 do
   begin
   for j:=0 to circles[i2].nel-2 do
      begin
      if circles[i1].els[i]=circles[i2].els[j] then k:=k+1;
      end;
   end;
if k=(circles[i1].nel-1) then Result:=True;
end;
 
function rDirAngle(x1,y1,x2,y2:Extended):Extended;
var x:Extended;
begin
if Abs(y2-y1)<0.000001 then
   begin
   if x2>x1 then begin Result:=PI/2;exit;end;
   if x2<x1 then begin Result:=3*PI/2;exit;end
   end;
x:=Arctan(Abs(x2-x1)/Abs(y2-y1))*180/PI;
if (x2>=x1) and (y2>y1) then Result:=x;
if (x2>=x1) and (y2<y1) then Result:=180-x;
if (x2<=x1) and (y2<y1) then Result:=180+x;
if (x2<=x1) and (y2>y1) then Result:=360-x;
Result:=Result*PI/180;
end;
 
function IsHorderCircle(n:integer):Boolean;
var i,j,d,k,i1,i2:integer;
a1,a2,a3:double;
begin
d:=0;
for i:=0 to circles[n].nel-2 do
   begin
   d:=d+xa[circles[n].els[i]]*ya[circles[n].els[i+1]]-xa[circles[n].els[i+1]]*ya[circles[n].els[i]];
   end;
d:=sign(d); // -1 - против, =1 - по  (или наоборот)
//---------Если против часовой стрелки, поменять направление
if d<0 then
   begin
   for i:=0 to circles[n].nel div 2 - 1 do
      begin
      k:=circles[n].els[i];
      circles[n].els[i]:=circles[n].els[circles[n].nel-1-i];
      circles[n].els[circles[n].nel-1-i]:=k;
      end;
   end;
//---------Обход по часовой, проверка ответвлений вправо
circles[n].els[circles[n].nel]:=circles[n].els[1];  //--Добавляем ещё один элемент в цикл
for i:=0 to circles[n].nel-2 do
   begin
   for j:=0 to np-1 do  //---поиск сопряжённых точек
      begin
      if (adj[circles[n].els[i+1],j]=1) and (j<>circles[n].els[i]) and (j<>circles[n].els[i+1]) and (j<>circles[n].els[i+2]) then
         begin
         a1:=rDirAngle(xa[circles[n].els[i+1]],ya[circles[n].els[i+1]],xa[circles[n].els[i]],ya[circles[n].els[i]]);
         a2:=rDirAngle(xa[circles[n].els[i+1]],ya[circles[n].els[i+1]],xa[circles[n].els[i+2]],ya[circles[n].els[i+2]]);
         a3:=rDirAngle(xa[circles[n].els[i+1]],ya[circles[n].els[i+1]],xa[j],ya[j]);
         a1:=a1*180/PI;a2:=a2*180/PI;a3:=a3*180/PI;
         a1:=a1-a2; while (a1<360) do a1:=a1+360;while (a1>360) do a1:=a1-360;
         a3:=a3-a2; while (a3<360) do a3:=a3+360;while (a3>360) do a3:=a3-360;
         if a3>a1 then begin Result:=true;exit;end;
         end;
      end;
   end;
IntToStr(n);
Result:=False;
end;
 
procedure push(k:integer);
begin
stack[t]:=k;t:=t+1;
end;
 
procedure pop(k:integer);
begin
t:=t-1;
end;
 
procedure DFS(k,v:integer);
var i,j,m,i1,j1:integer;
begin
push(k);
visited[k]:=1;
for i:=0 to np-1 do
    begin
    if i=k then continue;
    if i=v then continue;
    if (visited[i]=1) and (adj[i,k]<>0) then //--если не сама с себя
       begin
       for j:=0 to t-1 do
          begin
          circles[ncl].els[j]:=stack[j];
          end;
       for j:=0 to t-1 do if stack[j]=i then break;
       for m:=j to t-1 do circles[ncl].els[m-j]:=stack[m]; //---переносим цикл из стека
       circles[ncl].els[t-j]:=i;
       circles[ncl].nel:=t-j+1;
//-------------проверка, а может такой цикл уже есть?
       j1:=0;
       for i1:=0 to ncl-1 do
          begin
          if CompareCircles(i1,ncl)=True then begin j1:=1;break;end;
          end;
//-------------проверка, цикл с внутренними хордами?
       if IsHorderCircle(ncl)=True then j1:=1;
       if j1=0 then ncl:=ncl+1; //--Если такого цикла не было, то добавляем, иначе - нет
       continue;
       end;
    if adj[i,k]<>0 then DFS(i,k);
    end;
visited[k]:=0;
pop(k);
end;
 
procedure TForm13.Button2Click(Sender: TObject);
var i,j,k,minx,maxx:integer;
begin
//----------Сформировать adj
for i:=0 to 100 do for j:=0 to 100 do adj[i,j]:=0;
for i:=0 to nseg-1 do
   begin
   adj[seg[0,i],seg[1,i]]:=1;
   adj[seg[1,i],seg[0,i]]:=1;
   end;
//----------Запустить DFS
t:=0;ncl:=0;
for i:=0 to np-1 do visited[i]:=0;
for i:=0 to np-1 do
   begin
   if visited[i]=0 then DFS(i,-1);
   end;
minx:=100000;maxx:=-100000;for i:=0 to np-1 do begin if xa[i]<minx then minx:=xa[i];if xa[i]>maxx then maxx:=xa[i];end;
for i:=0 to ncl-1 do begin Draw(i*(maxx-minx+30),300);DrawCircles(i,i*(maxx-minx+30),300);end;
end

;

@Massaraksh7 · 25.06.2017, 19:06 **[ТС]**

---

@Massaraksh7 · 26.06.2017, 16:10 **[ТС]**

И ещё. Это для координат экрана. Для математических координат 58 строка заменяется на if d>0 then, а 81 на if a3<a1 then begin Result:=true;exit;end;

@Massaraksh7 · 29.06.2017, 02:08 **[ТС]**

Обход в глубину из всех точек является лишним. Достаточно из одной (любой).

@sabrus · 05.02.2019, 22:34

а теперь бинго. Отделить элементарный от неэлементарных можно ээээ элементарно.

Фильтрация на базе вот такого признака:
В элементарном цикле каждая вершина инцидентна только с двумя другими вершинами входящими в цикл, тогда как в НЕэлементарном обязательно есть как минимум две(но ищем ессно сам факт - т.е. что есть такая вершина) вершины инцидентных с не менее чем тремя другими вершинами.

@Shamil1 · 06.02.2019, 09:35

Сообщение от sabrus

Отделить элементарный от неэлементарных можно ээээ элементарно.

ТСа интересует цикл без хорд.

Сообщение от Shamil1

Элементраный цикл - это цикл, который не имеет самопересечений. А то, что на картинке, называется "цикл без хорд".

@sabrus · 06.02.2019, 15:02

Сообщение от Shamil1

ТСа интересует цикл без хорд.

Да, и я предложил способ определения таких циклов. Более простой чем:

Сообщение от Massaraksh7

Поправка: более надёжное определение внутренних хорд через дирекционные углы.

@Massaraksh7 338 / 283 / 95 Регистрация: 27.05.2017 Сообщений: 1,486
		1
	Алгоритм поиска элементарных циклов в неориентированном графе 23.06.2017, 02:57. Показов 5552. Ответов 28 Метки нет (Все метки) Необходимо граф разбить на элементарные циклы, то есть такие циклы, которые не имею внутри подциклов. Пример - на рисунке. Как найти все циклы в графе, я знаю. Но мне нужны не все. Миниатюры 0

@krapotkin 5429 / 4256 / 1372 Регистрация: 14.04.2014 Сообщений: 19,168 Записей в блоге: 19
	23.06.2017, 07:08	2
	вы слишком полагаетесь на глаза если у нас действительно граф, то его можно нарисовать и вот так и тогда все будет выглядеть по-другому Миниатюры 0

@Shamil1 Модератор 2968 / 2107 / 450 Регистрация: 26.03.2015 Сообщений: 8,229
	23.06.2017, 09:42	3
	Сообщение от krapotkin и тогда все будет выглядеть по-другому Но элементарные циклы те же остались. 0

@krapotkin 5429 / 4256 / 1372 Регистрация: 14.04.2014 Сообщений: 19,168 Записей в блоге: 19
	23.06.2017, 09:49	4
	является ли цикл 1-2-3-4-5-13-6-7-8-9-10-11 элементарным? 0

@Massaraksh7 338 / 283 / 95 Регистрация: 27.05.2017 Сообщений: 1,486
	23.06.2017, 13:07 [ТС]	5
	Сообщение от krapotkin является ли цикл 1-2-3-4-5-13-6-7-8-9-10-11 элементарным? Да, если исходить из того, как я сформулировал, является. Но такого не будет, ибо "в реале" сам граф "формируют" геодезисты. 0

@Shamil1 Модератор 2968 / 2107 / 450 Регистрация: 26.03.2015 Сообщений: 8,229
	23.06.2017, 13:34	6
	Сообщение от krapotkin является ли цикл 1-2-3-4-5-13-6-7-8-9-10-11 элементарным? Не является, так как существует ребро (5,11), которое не в ходит в цикл и связывает две вершины из этого цикла. Добавлено через 7 минут Massaraksh7, Липский. Комбинаторика для программистов. 2.5. Отыскание фундаментального множества циклов в графе. (стр.92) Алгоритм 2.9. (стр.95) Добавлено через 8 минут Сообщение от Massaraksh7 Необходимо граф разбить на элементарные циклы, то есть такие циклы, которые не имею внутри подциклов. Элементраный цикл - это цикл, который не имеет самопересечений. А то, что на картинке, называется "цикл без хорд". 1

@Massaraksh7 338 / 283 / 95 Регистрация: 27.05.2017 Сообщений: 1,486
	23.06.2017, 13:38 [ТС]	7
	Сообщение от Shamil1 Липский. Комбинаторика для программистов. 2.5. Отыскание фундаментального множества циклов в графе. (стр.92) Алгоритм 2.9. (стр.95) Спасибо, посмотрю. Добавлено через 2 минуты Сообщение от Shamil1 А то, что на картинке, называется "цикл без хорд". Цикл без хорд состоит из треугольников. 0

@Shamil1 Модератор 2968 / 2107 / 450 Регистрация: 26.03.2015 Сообщений: 8,229
	23.06.2017, 13:40	8
	Сообщение от Massaraksh7 Цикл без хорд состоит из треугольников. Из вики: Цикл без хорд в графе, также называемый дырой или порождённым циклом, — это цикл, в котором никакие две вершины цикла не соединены ребром, разве что это ребро само принадлежит циклу. 0

@Massaraksh7 338 / 283 / 95 Регистрация: 27.05.2017 Сообщений: 1,486
	23.06.2017, 14:23 [ТС]	9
	Хорошо, пусть так. Тогда один из вариантов - найти все циклы, а потом из них исключить те, у которых есть подциклы. По какому принципу? Организовать обход цикла по часовой стрелке, и следить, чтобы справа не было вхождений? Ну или наоборот. 0

@Massaraksh7 338 / 283 / 95 Регистрация: 27.05.2017 Сообщений: 1,486
	25.06.2017, 17:19 [ТС]	13
	--- Миниатюры 0

@Massaraksh7 338 / 283 / 95 Регистрация: 27.05.2017 Сообщений: 1,486
	25.06.2017, 19:06 [ТС]	15
	--- Миниатюры 0

@Massaraksh7 338 / 283 / 95 Регистрация: 27.05.2017 Сообщений: 1,486
	26.06.2017, 16:10 [ТС]	16
	И ещё. Это для координат экрана. Для математических координат 58 строка заменяется на `if d>0 then`, а 81 на `if a3<a1 then begin Result:=true;exit;end;` 0

@Massaraksh7 338 / 283 / 95 Регистрация: 27.05.2017 Сообщений: 1,486
	29.06.2017, 02:08 [ТС]	17
	Обход в глубину из всех точек является лишним. Достаточно из одной (любой). 0

@sabrus 1 / 1 / 2 Регистрация: 12.07.2013 Сообщений: 144
	05.02.2019, 22:34	18
	а теперь бинго. Отделить элементарный от неэлементарных можно ээээ элементарно. Фильтрация на базе вот такого признака: В элементарном цикле каждая вершина инцидентна только с двумя другими вершинами входящими в цикл, тогда как в НЕэлементарном обязательно есть как минимум две(но ищем ессно сам факт - т.е. что есть такая вершина) вершины инцидентных с не менее чем тремя другими вершинами. 0

@Shamil1 Модератор 2968 / 2107 / 450 Регистрация: 26.03.2015 Сообщений: 8,229
	06.02.2019, 09:35	19
	Сообщение от sabrus Отделить элементарный от неэлементарных можно ээээ элементарно. ТСа интересует цикл без хорд. Сообщение от Shamil1 Элементраный цикл - это цикл, который не имеет самопересечений. А то, что на картинке, называется "цикл без хорд". 0

@sabrus 1 / 1 / 2 Регистрация: 12.07.2013 Сообщений: 144
	06.02.2019, 15:02	20
	Сообщение от Shamil1 ТСа интересует цикл без хорд. Да, и я предложил способ определения таких циклов. Более простой чем: Сообщение от Massaraksh7 Поправка: более надёжное определение внутренних хорд через дирекционные углы. 0