Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.75/8: Рейтинг темы: голосов - 8, средняя оценка - 4.75
Massaraksh7
311 / 264 / 87
Регистрация: 27.05.2017
Сообщений: 1,350
1

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

23.06.2017, 02:57. Просмотров 1533. Ответов 26
Метки нет (Все метки)

Необходимо граф разбить на элементарные циклы, то есть такие циклы, которые не имею внутри подциклов. Пример - на рисунке. Как найти все циклы в графе, я знаю. Но мне нужны не все.
0
Миниатюры
Алгоритм поиска элементарных циклов в неориентированном графе  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.06.2017, 02:57
Ответы с готовыми решениями:

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

Алгоритм поиска всех деревьев в графе
Имеется граф. Необходимо найти множество всех деревьев. Где дерево это минимальная неизбыточная...

Алгоритм поиска циклов неориентированного графа
Помогите пожалуйста. Нужен алгоритм, который считал бы циклы неориентированного графа.

Количество мостов в неориентированном графе
Здравствуйте, я хотел бы посчитать количество мостов,с помощью нахождения компонент реберной...

Максимальный поток в неориентированном графе
Какой алгоритм следует использовать для нахождения максимального потока в неориентированном...

26
krapotkin
3941 / 3301 / 1128
Регистрация: 14.04.2014
Сообщений: 15,828
Записей в блоге: 17
23.06.2017, 07:08 2
вы слишком полагаетесь на глаза
если у нас действительно граф, то его можно нарисовать и вот так
и тогда все будет выглядеть по-другому
0
Миниатюры
Алгоритм поиска элементарных циклов в неориентированном графе  
Shamil1
Модератор
2292 / 1589 / 354
Регистрация: 26.03.2015
Сообщений: 5,774
23.06.2017, 09:42 3
Цитата Сообщение от krapotkin Посмотреть сообщение
и тогда все будет выглядеть по-другому
Но элементарные циклы те же остались.
0
krapotkin
3941 / 3301 / 1128
Регистрация: 14.04.2014
Сообщений: 15,828
Записей в блоге: 17
23.06.2017, 09:49 4
является ли цикл 1-2-3-4-5-13-6-7-8-9-10-11 элементарным?
0
23.06.2017, 09:49
Massaraksh7
311 / 264 / 87
Регистрация: 27.05.2017
Сообщений: 1,350
23.06.2017, 13:07  [ТС] 5
Цитата Сообщение от krapotkin Посмотреть сообщение
является ли цикл 1-2-3-4-5-13-6-7-8-9-10-11 элементарным?
Да, если исходить из того, как я сформулировал, является. Но такого не будет, ибо "в реале" сам граф "формируют" геодезисты.
0
Shamil1
Модератор
2292 / 1589 / 354
Регистрация: 26.03.2015
Сообщений: 5,774
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
311 / 264 / 87
Регистрация: 27.05.2017
Сообщений: 1,350
23.06.2017, 13:38  [ТС] 7
Цитата Сообщение от Shamil1 Посмотреть сообщение
Липский. Комбинаторика для программистов.
2.5. Отыскание фундаментального множества циклов в графе. (стр.92)
Алгоритм 2.9. (стр.95)
Спасибо, посмотрю.

Добавлено через 2 минуты
Цитата Сообщение от Shamil1 Посмотреть сообщение
А то, что на картинке, называется "цикл без хорд".
Цикл без хорд состоит из треугольников.
0
Shamil1
Модератор
2292 / 1589 / 354
Регистрация: 26.03.2015
Сообщений: 5,774
23.06.2017, 13:40 8
Цитата Сообщение от Massaraksh7 Посмотреть сообщение
Цикл без хорд состоит из треугольников.
Из вики:
Цикл без хорд в графе, также называемый дырой или порождённым циклом, — это цикл, в котором никакие две вершины цикла не соединены ребром, разве что это ребро само принадлежит циклу.
0
Massaraksh7
311 / 264 / 87
Регистрация: 27.05.2017
Сообщений: 1,350
23.06.2017, 14:23  [ТС] 9
Хорошо, пусть так. Тогда один из вариантов - найти все циклы, а потом из них исключить те, у которых есть подциклы. По какому принципу? Организовать обход цикла по часовой стрелке, и следить, чтобы справа не было вхождений? Ну или наоборот.
0
Massaraksh7
311 / 264 / 87
Регистрация: 27.05.2017
Сообщений: 1,350
25.06.2017, 16:26  [ТС] 10
Итак, продолжаем. Первым делом надо получить все существующие циклы графа, используя поиск в глубину. Для вот такого простого графа их число получается 416.
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
0
Изображения
 
Massaraksh7
311 / 264 / 87
Регистрация: 27.05.2017
Сообщений: 1,350
25.06.2017, 16:30  [ТС] 11
Это нас не устраивает, среди циклов много повторяющихся. Поэтому при записи нового цикла мы устроим проверку: а не было ли такого цикла раньше?
Получается уже лучше, всего 13 циклов осталось.
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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;
0
Миниатюры
Алгоритм поиска элементарных циклов в неориентированном графе  
Massaraksh7
311 / 264 / 87
Регистрация: 27.05.2017
Сообщений: 1,350
25.06.2017, 16:38  [ТС] 12
Но ещё остались циклы внутренними хордами, которые нам не нужны. Поэтому мы устраиваем проверку на них. Делаем это так: определяем направление цикла - по часовой, или против? Для этого находим сумму произведений x[i]*y[i+1]-x[i+1]*y[i] для каждого узла, и, в зависимости от знака, оставляем цикл как есть, или меняем его порядок. После этого проходимся по циклу, и для каждого узла определяем, а нет ответвляется ли вправо ребро, не являющееся частью его оболочки? После этого получаем то, что нам было нужно.
Полный алгоритм на Delphi:
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
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;
Просьба к модераторам, в названии темы заменить слово "элементарных циклов" на "циклов без хорд".
0
Миниатюры
Алгоритм поиска элементарных циклов в неориентированном графе  
Massaraksh7
311 / 264 / 87
Регистрация: 27.05.2017
Сообщений: 1,350
25.06.2017, 17:19  [ТС] 13
---
0
Миниатюры
Алгоритм поиска элементарных циклов в неориентированном графе  
Massaraksh7
311 / 264 / 87
Регистрация: 27.05.2017
Сообщений: 1,350
25.06.2017, 19:03  [ТС] 14
Поправка: более надёжное определение внутренних хорд через дирекционные углы.
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
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
;
0
Massaraksh7
311 / 264 / 87
Регистрация: 27.05.2017
Сообщений: 1,350
25.06.2017, 19:06  [ТС] 15
---
0
Миниатюры
Алгоритм поиска элементарных циклов в неориентированном графе  
Massaraksh7
311 / 264 / 87
Регистрация: 27.05.2017
Сообщений: 1,350
26.06.2017, 16:10  [ТС] 16
И ещё. Это для координат экрана. Для математических координат 58 строка заменяется на if d>0 then, а 81 на if a3<a1 then begin Result:=true;exit;end;
0
Massaraksh7
311 / 264 / 87
Регистрация: 27.05.2017
Сообщений: 1,350
29.06.2017, 02:08  [ТС] 17
Обход в глубину из всех точек является лишним. Достаточно из одной (любой).
0
sabrus
0 / 0 / 2
Регистрация: 12.07.2013
Сообщений: 124
05.02.2019, 22:34 18
а теперь бинго. Отделить элементарный от неэлементарных можно ээээ элементарно.

Фильтрация на базе вот такого признака:
В элементарном цикле каждая вершина инцидентна только с двумя другими вершинами входящими в цикл, тогда как в НЕэлементарном обязательно есть как минимум две(но ищем ессно сам факт - т.е. что есть такая вершина) вершины инцидентных с не менее чем тремя другими вершинами.
0
Shamil1
Модератор
2292 / 1589 / 354
Регистрация: 26.03.2015
Сообщений: 5,774
06.02.2019, 09:35 19
Цитата Сообщение от sabrus Посмотреть сообщение
Отделить элементарный от неэлементарных можно ээээ элементарно.
ТСа интересует цикл без хорд.

Цитата Сообщение от Shamil1 Посмотреть сообщение
Элементраный цикл - это цикл, который не имеет самопересечений. А то, что на картинке, называется "цикл без хорд".
0
sabrus
0 / 0 / 2
Регистрация: 12.07.2013
Сообщений: 124
06.02.2019, 15:02 20
Цитата Сообщение от Shamil1 Посмотреть сообщение
ТСа интересует цикл без хорд.
Да, и я предложил способ определения таких циклов. Более простой чем:
Цитата Сообщение от Massaraksh7 Посмотреть сообщение
Поправка: более надёжное определение внутренних хорд через дирекционные углы.
0
06.02.2019, 15:02
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.02.2019, 15:02

Поиск цикла заданной длины в неориентированном графе
Всем привет! Есть такая задача: дана система двусторонних дорог. Найти замкнутый путь длиной не...

Реализовать алгоритм А* для поиска оптимального пути из начальной вершины в конечную на графе
Привет Нужно реализовать этот алгоритм для поиска оптимального пути из начальной вершины в...

Найти все циклы в неориентированном графе по матрице смежности
Здравствуйте. Задача в заголовке. С построением матрицы смежности проблем нет, вопрос в алгоритме...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru