VPF::Нахождение ВСЕХ эйлеровых циклов в графе (pascal)

Panourgue

Дата 27.12.2006, 10:33 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 9.6.2006

Репутация: нет
Всего: нет

Здраствуйте!
Алгоритм для нахождения ВСЕХ эйлеровых циклов и цепей (т.е. незамкнутых; это если есть нечетные вершины) в ор- и неорграфах (Delphi / Pascal)
Умоляю, помогите!

SoWa

Дата 27.12.2006, 15:43 (ссылка)

(нет голосов)

Загрузка ...

Харекришна

Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74

Во первых поиск, во вторых перебор.

--------------------

Всем добра smile

Panourgue

Дата 27.12.2006, 16:28 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 9.6.2006

Репутация: нет
Всего: нет

2SoWa:, А нельзя ли поподробнее? smile

Что значит перебор?

----------------
Просто я к программированию и алгоритмам имею не совсем непосредственное отношение...

SoWa

Дата 27.12.2006, 17:14 (ссылка)

(нет голосов)

Загрузка ...

Харекришна

Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74

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

--------------------

Всем добра smile

IvanoffAndrey

Дата 31.12.2006, 13:21 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 157
Регистрация: 8.7.2006
Где: СГАУ

Репутация: нет
Всего: 2

Я бы искал эйлеровы циклы согласно теореме:
Граф содержит Эйлеров цикл тогда и тоглько тогда когда все его вершины имеют четную степень. Это значит,
1. что нужно удостовериться в четности всех степеней вершин.
2. Найти один цикл согласно алгоритма Флери
3. сгенерировать всевозможные переставки данного цикла.
Вроде так.
Если тебя все еще интерисует этот вопрос отвечу подробнее.

Цитата

во вторых перебор.

Не стоит делать перебор, существуют абсолютно полные алгоритмы например алгоритм Флери, если надо опишу его.

--------------------

Размерность пространства есть число Pi и в каждой точке вселенной оно стремиться к этому числу.

VaiMR

Дата 16.1.2007, 01:39 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 67
Регистрация: 25.11.2006

Репутация: нет
Всего: 2

Вот например так (правда си++):

Код


//================ проверка связности =====================

//-----Проверка наличия вершин помеченных 2 маркером-------
char kolv2(int kolv,int mbuf[])
 {
  for (int i=0;i<kolv;i++)
   if (mbuf[i]==2)
    return 't';
  return 'f';
 }
//---------------------------------------------------------

char svaz(int kolv,int *gr[])
{
 int mbuf[maxkolv];

 for (int i=0;i<kolv;i++)
  mbuf[i]=1;

 mbuf[1]=2;
 while (kolv2(kolv,mbuf)=='t')
  for (i=0;i<kolv;i++)
   if (mbuf[i]==2)
    {
     mbuf[i]=3;
      for (int j=0;j<kolv;j++)
       if ((gr[i][j]==1)&&(mbuf[j]==1))
    mbuf[j]=2;
    };
 for (i=0;i<kolv;i++)
  if (mbuf[i]==1)
   return 'f';
 return 't';
}
//=========================================================

//================ поиск эйлерова пути ====================

//-----Проверка наличия ненулевых вершин ------------------
char kolvn0(int kolv,int mbuf[])
 {
  for (int i=0;i<kolv;i++)
   if (mbuf[i]>0)
    return 't';
  return 'f';
 }
//---------------------------------------------------------

void euler(int kolv,int *gr[])
{
 int v,u,i,x,i1=0,i2=0;
 int st1[maxkolv];
 int st2[maxkolv];

 for(i=0;i<kolv;i++) st1[i]=0, st2[i]=0;
 do
  cout<<"введите номер стартовой вершины: ",cin>>v; // ЗДЕСЬ В ЦИКЛЕ ПЕРЕБИРАЕМ ВСЕ ВЕРШИНЫ!!!
 while (v>kolv);

 st1[i1]=v;
 while (kolvn0(kolv,st1)=='t')
  {
   v=st1[i1];
   i=0;
   while ((i<kolv)&&(gr[v-1][i]==0))
    i++;
   if (i<kolv)
    {
     u=i;
     i1++;
     st1[i1]=u+1;
     gr[v-1][u  ]=0;
     gr[u  ][v-1]=0;
    }
   else
    {
     st2[i2]=st1[i1];
     st1[i1]=0      ;
     i1--;
     i2++;
    }
  };
 cout<<"эйлеров цикл: ";
 for(i=0;i<kolv-1;i++) cout<<st2[i]<<" -> ";
 cout<<st2[kolv-1];
 cout<<" -> "<<v;
}

А вот проверка связности на Паскале:

Код



const kolvmax=10;

type mass=array[1..kolvmax,1..kolvmax] of byte;
     mversh=array[1..kolvmax] of byte;

{Проверка графа на связность}

function svaz(var mbuf:mversh;const m:mass;kolv,n:byte):boolean;
var i,j:byte;

{Проверка наличия вершин помеченных 2 маркером}

 function kolv2(const mbuf:mversh;kolv:byte):boolean;
  var i:byte;
  begin
   for i:=1 to kolv do
    if mbuf[i]=2
     then
      begin
       kolv2:=true;
       exit;
      end;
  kolv2:=false;
  end;

{////////////////////////////////////////////////}

begin
 for i:=1 to kolv do
  mbuf[i]:=1;
 mbuf[n]:=2;
 while kolv2(mbuf,kolv) do
  begin
   for i:=1 to kolv do
    if mbuf[i]=2
     then
      begin
       mbuf[i]:=3;
        for j:=1 to kolv do
          if (m[i,j]=1)and(mbuf[j]=1)
           then
            mbuf[j]:=2;
      end;
   end;
 for i:=1 to kolv do
  if mbuf[i]=1
   then
    begin
     svaz:=false;
     exit;
    end;
 svaz:=true;
end;

{////////////////////////////////////////////////////}

На Паскале нет Эйлеровых циклов, так как когда писал не нужно было.

Это сообщение отредактировал(а) VaiMR - 16.1.2007, 08:42

VaiMR

Дата 16.1.2007, 08:40 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 67
Регистрация: 25.11.2006

Репутация: нет
Всего: 2

Оказывается есть реализация на Паскале в моей копилке:

Код


Program Euler;
const n=9;
      m: array[1..n, 1..n] of boolean=
      (
      (False, True,  True,  False, False, False, False, False, False),
      (True,  False, True,  False, False, False, True,  True,  False),
      (True,  True,  False, True,  True,  False, False, False, False),
      (False, False, True,  False, True,  False, False, False, False),
      (False, False, True,  True,  False, True,  False, True,  False),
      (False, False, False, False, True,  False, True,  True,  True ),
      (False, True,  False, False, False, True,  False, True,  True ),
      (False, True,  False, False, True,  True,  True,  False, False),
      (False, False, False, False, False, True,  True,  False, False)
      );
Type
    list=^node;
    node=record
             i: integer;
          next: list
         end;
Var stack1, stack2: list;
        v, u, x, i: integer;

 Procedure Push(x: integer; var stack: list);
 Var temp: list;
 Begin
   New(temp);
   temp^.i:=x;
   temp^.next:=stack;
   stack:=temp
 End;

 Procedure Pop(var x: integer; var stack: list);
 Begin
   x:=stack^.i;
   stack:=stack^.next
 End;

 Function Peek(stack: list): integer;
 Begin
   Peek:=stack^.i
 End;

 Procedure PrintList(l: list);
 Begin
   Writeln;
   If l=nil then writeln('NIL');
   While l<>nil do
   Begin
     Write(l^.i:3);
     l:=l^.next
   End
 End;

Begin
  stack1:=nil;
  stack2:=nil;
  Write('Начальная вершина: ');readln(v);
  Push(v, stack1);
  While stack1<>NIL do
  Begin
    v:=peek(stack1);
    i:=1;
    While (i<=n) and not m[v, i] do inc(i);
    If i<=n then
            Begin
              u:=i;
              Push(u, stack1);
              m[v, u]:=False;
              m[u, v]:=False;
            End
            else
            Begin
              pop(x, stack1);
              push(x, stack2)
            End
  End;
  PrintList(stack2)
End.

Этот код писал не сам (взял из учебника) smile

esperant0

Дата 16.1.2007, 09:37 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 714
Регистрация: 20.5.2005

Репутация: 4
Всего: 14

Цитата(IvanoffAndrey @ 31.12.2006, 13:21)

Не стоит делать перебор, существуют абсолютно полные алгоритмы например алгоритм Флери, если надо опишу его.

Почему не стоит, задача класса PSPACE разве нет:?

--------------------

Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer

Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором а затем стерто и которое он - пользователь не мог видеть.

xZero

Дата 27.11.2008, 22:55 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 2.10.2006

Репутация: нет
Всего: нет

Код


private void FindCircle(Int32 v) {
            for (Int32 i = 0; i < n; i++) {
                     if (newg[v, i] > 0) {
                        newg[v, i]--;
                        newg[i, v]--;
                        FindCircle(i);               
                    } 
            }
            result.Add(v);
       
 } 
// newg - матрица смежности
// n - число вершин

таким рекурсивным алгоритмом можно найти один эйлеров цикл.
А как найти все эйлеровы циклы в графе?

например если v = 1;
находим вершины, смежные v. Пусть это вершины 3,5,6. Если в FindCircle(i) ставить вершины в
той последовательности, то получим один цикл, если в последовательности, например 5,3,6, то получим уже другой цикл.
Таким образом нужно модифицировать как-то этот рекурсивный алгоритм для нахождения всех циклов. Кто-нибудь может подсказать как это реализовать, потому что я пока что не смог придумать...

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »