338 / 283 / 95
Регистрация: 27.05.2017
Сообщений: 1,486
1

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

23.06.2017, 02:57. Показов 5552. Ответов 28
Метки нет (Все метки)

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

Поиск всех циклов в неориентированном графе.
На входе программа принимает номера вершин и вес ребра между ними. Например: 2 3 1 - между...

Нахождение элементарных циклов в графе
Помогите пожалуйста с написание программы нахождение элементарный циклов в графе на Pascal

Метод поиска в глубину, в неориентированном графе
Добрый день! Помогите решить задание: Используя метод поиска в глубину, в неориентированном...

Исследовать алгоритм нахождения Эйлерова пути в неориентированном графе
Задание: Реализовать в виде программы и исследовать алгоритм нахождения эйлерова пути в...

28
5429 / 4256 / 1372
Регистрация: 14.04.2014
Сообщений: 19,168
Записей в блоге: 19
23.06.2017, 07:08 2
вы слишком полагаетесь на глаза
если у нас действительно граф, то его можно нарисовать и вот так
и тогда все будет выглядеть по-другому
Миниатюры
Алгоритм поиска элементарных циклов в неориентированном графе  
0
Модератор
2968 / 2107 / 450
Регистрация: 26.03.2015
Сообщений: 8,229
23.06.2017, 09:42 3
Цитата Сообщение от krapotkin Посмотреть сообщение
и тогда все будет выглядеть по-другому
Но элементарные циклы те же остались.
0
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
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
Модератор
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
338 / 283 / 95
Регистрация: 27.05.2017
Сообщений: 1,486
23.06.2017, 13:38  [ТС] 7
Цитата Сообщение от Shamil1 Посмотреть сообщение
Липский. Комбинаторика для программистов.
2.5. Отыскание фундаментального множества циклов в графе. (стр.92)
Алгоритм 2.9. (стр.95)
Спасибо, посмотрю.

Добавлено через 2 минуты
Цитата Сообщение от Shamil1 Посмотреть сообщение
А то, что на картинке, называется "цикл без хорд".
Цикл без хорд состоит из треугольников.
0
Модератор
2968 / 2107 / 450
Регистрация: 26.03.2015
Сообщений: 8,229
23.06.2017, 13:40 8
Цитата Сообщение от Massaraksh7 Посмотреть сообщение
Цикл без хорд состоит из треугольников.
Из вики:
Цикл без хорд в графе, также называемый дырой или порождённым циклом, — это цикл, в котором никакие две вершины цикла не соединены ребром, разве что это ребро само принадлежит циклу.
0
338 / 283 / 95
Регистрация: 27.05.2017
Сообщений: 1,486
23.06.2017, 14:23  [ТС] 9
Хорошо, пусть так. Тогда один из вариантов - найти все циклы, а потом из них исключить те, у которых есть подциклы. По какому принципу? Организовать обход цикла по часовой стрелке, и следить, чтобы справа не было вхождений? Ну или наоборот.
0
338 / 283 / 95
Регистрация: 27.05.2017
Сообщений: 1,486
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
338 / 283 / 95
Регистрация: 27.05.2017
Сообщений: 1,486
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
338 / 283 / 95
Регистрация: 27.05.2017
Сообщений: 1,486
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
338 / 283 / 95
Регистрация: 27.05.2017
Сообщений: 1,486
25.06.2017, 17:19  [ТС] 13
---
Миниатюры
Алгоритм поиска элементарных циклов в неориентированном графе  
0
338 / 283 / 95
Регистрация: 27.05.2017
Сообщений: 1,486
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
338 / 283 / 95
Регистрация: 27.05.2017
Сообщений: 1,486
25.06.2017, 19:06  [ТС] 15
---
Миниатюры
Алгоритм поиска элементарных циклов в неориентированном графе  
0
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
338 / 283 / 95
Регистрация: 27.05.2017
Сообщений: 1,486
29.06.2017, 02:08  [ТС] 17
Обход в глубину из всех точек является лишним. Достаточно из одной (любой).
0
1 / 1 / 2
Регистрация: 12.07.2013
Сообщений: 144
05.02.2019, 22:34 18
а теперь бинго. Отделить элементарный от неэлементарных можно ээээ элементарно.

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

Цитата Сообщение от Shamil1 Посмотреть сообщение
Элементраный цикл - это цикл, который не имеет самопересечений. А то, что на картинке, называется "цикл без хорд".
0
1 / 1 / 2
Регистрация: 12.07.2013
Сообщений: 144
06.02.2019, 15:02 20
Цитата Сообщение от Shamil1 Посмотреть сообщение
ТСа интересует цикл без хорд.
Да, и я предложил способ определения таких циклов. Более простой чем:
Цитата Сообщение от Massaraksh7 Посмотреть сообщение
Поправка: более надёжное определение внутренних хорд через дирекционные углы.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.02.2019, 15:02
Помогаю со студенческими работами здесь

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

Алгоритм поиска сечений в графе.
Привет всем кто на форуме. Может кто объяснить алгоритм поиска сечений в графе. имеются пути,...

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

Алгоритм поиска в глубину в ориентированном графе
Добрый вечер,форумчане:) Знаю, что подобная тема встречалась тут довольно часто, но у меня все-таки...

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru