Шаг 99.
Эйлеровы пути и циклы

    На этом шаге мы рассмотрим Эйлеровы пути и циклы.

   

Определение 1 [1, с.106].
Эйлеровым путем в графе называется путь, проходящий через каждое ребро графа только один раз, т.е. путь v1,v2..., vm+1, такой, что каждое ребро e, принадлежащее E, появляется в последовательности v1, v2..., vm+1 в точности один раз как e={vi,vi+1}. 0 Иногда граф, обладающий эйлеровым путем, называют полуэйлеровым [2, с.43].

    Если v1=vm+1, то такой путь называется эйлеровым циклом, а граф, обладающий эйлеровым циклом, называют эйлеровым графом [2, с.43].

    Задача существования эйлерова пути в заданном графе была решена Л.Эйлером в 1736 г., и представленное им необходимое и достаточное условие существования такого пути считается первой в истории теоремой теории графов.

Теорема [1, с.106].
Эйлеров путь в графе существует тогда и только тогда, когда:
  • граф связный и
  • содержит не более чем две вершины нечетной степени.
Приведем формулировку этой же теоремы в другой терминологии.
Теорема [2, с.43].
Связный граф является полуэйлеровым тогда и только тогда, когда в нем не более двух вершин имеют нечетные степени.

    Если в связном графе нет вершин нечетной степени, то каждый эйлеров путь является циклом, так как концы эйлерова пути, не являющегося циклом, всегда вершины нечетной степени.

    Это утверждение в монографии [2, с.4 24 0] оформлено в виде теоремы.

Теорема.
Связный граф G является эйлеровым (обладает эйлеровым циклом) тогда и только тогда, когда каждая вершина в G имеет четную степень.
Определение 2 [3, с.182].
Эйлеров контур 0 в ориентированном графе - это контур, содержащий все дуги и только по одному разу.

    Каковы же те графы, которые обладают эйлеровыми контурами?

    Граф называется псевдосимметрическим, если в каждой его вершине число исходящих дуг равно числу заходящих. Эта терминология оправдывается тем, что всякий симметрический граф является в то же время псевдосимметрическим.

Теорема [3, с.182].
Граф обладает эйлеровым контуром тогда и только тогда, когда он является связным и псевдосимметрическим.

    Реализуем приведенный в [1,с.107] алгоритм нахождения эйлерова цикла в связном графе без вершин нечетной степени, представленном структурой Вирта. 

void Spisok::Euler ()
//Построение эйлерова цикла в связном графе без вершин нечетной
//степени, заданном  структурой  Вирта. Начало цикла определено
//указателем Head.
{
  Lref v,u; //Рабочие переменные.
  svqz q;   //Рабочая переменная.

  svqz Stack =NULL, CE = NULL;
  W_S (&Stack,Head);
  while (Stack!=NULL)
  {
    //Взглянем на верхний элемент стека Stack...
    v = Stack->Element;
    if  (v->Trail!=NULL)
    {
      u = v->Trail->Id;
		W_S (&Stack,u);
      DeleteGraph (v->Key,u->Key);
      DeleteGraph (u->Key,v->Key);
    }
    else
    {
      YDALENIE (&Stack,&v);
      W_S (&CE,v);
    }
  }
  //В стеке CE хранится эйлеров цикл.
  q = CE;
  while  (q!=NULL)
  {  cout << q->Element->Key << ' '; q = q->Sled; }
}

    Оценим теперь вычислительную сложность алгоритма [1, с.108]. Для этого отметим, что каждая итерация главного цикла либо помещает вершину в стек Stack и удаляет ребро из графа, либо переносит вершину из стека Stack в стек CE. Таким образом, число итераций этого цикла - O(m), где m - количество ребер.

    Ухудшить алгоритм может лишь процедура удаления ребра из графа, которая у нас называется DeleteGraph (), и встречается почти в каждой итерации. Она это и делает, ибо уже на поиски удаляемого ребра затрачивается время 2*O(n), где n - количество вершин графа.

    Из приведенных рассуждений можно сделать вывод, что общая сложность алгоритма есть O(m*n).

    Пример. 
#include <iostream.h>
#define TRUE 1
#define FALSE 0
typedef int Boolean;
typedef struct L *Lref; // Тип: указатель на заголовочный узел.
typedef struct T *Tref; // Тип: указатель на дуговой узел.

//Описание типа заголовочного узла.
typedef struct L 
{ 
  int Key; //Имя заголовочного узла.
  int Count; //Количество предшественников.
  Boolean Flag; //Флаг посещения узла при обходе.
  Tref Trail; //Указатель на список смежности.
  Lref Next; //Указатель на следующий узел в списке заголовочных узлов.
} Leader;

//Описание типа дугового узла.
typedef struct T 
{ 
  Lref Id; 
  Tref Next; 
} Trailer;

//Описание типа узла стека.
typedef Lref TipElement;
typedef struct Zveno *svqz;
typedef struct Zveno 
{ 
  TipElement Element; //Указатель на список смежности.
  svqz Sled; 
} St;

class Spisok
{
  private:
    Lref Head; //Указатель на голову списка заголовочных узлов.
    Lref Tail; //Указатель на фиктивный элемент 
               // в конце списка заголовочных узлов.
    void SearchGraph (int, Lref *);
    void W_S (svqz *, TipElement);
    void YDALENIE (svqz *, TipElement *);
    Lref Search (int);
    void DeleteGraph (int, int);
  public:
    Spisok() {//Инициализация списка заголовочных узлов.
              Head = Tail =  new (Leader); }
    void MakeGraph ();
    void PrintGraph ();
    void Euler ();
};

void main ()
{
  Spisok A;
  //Построение графа и вывод его структуры Вирта.
  A.MakeGraph ();
  A.PrintGraph (); cout<<endl;
  //Построение Эйлерова цикла.
  A.Euler(); 
  A.PrintGraph (); cout<<endl;
} 

void Spisok::SearchGraph (int w, Lref *h)
//Функция возвращает указатель на заголовочный узел 
//с ключом w в графе, заданном структурой Вирта с указателем Head. 
{
  *h = Head; (*Tail).Key = w;
  while ((**h).Key!=w) *h = (**h).Next;
  if (*h==Tail)
  //В списке заголовочных узлов нет узла с ключом w.
  //Поместим его в конец списка Head.
  { Tail = new (Leader); (**h).Count = 0; 
    (**h).Trail = NULL; (**h).Next = Tail; }
}

void Spisok::MakeGraph ()
//Функция возвращает указатель Head на структуру 
//Вирта, соответствующую ориентированному графу.
{
  int x,y;
  Lref p,q; //Рабочие указатели.
  Tref t,r; //Рабочие указатели.
  Boolean Res; //Флаг наличия дуги.
  cout<<"Вводите начальную вершину дуги: ";
  cin>>x;
  while (x!=0)
  {
     cout<<"Вводите конечную вершину дуги: "; cin>>y;
     //Определим, существует ли в графе дуга (x,y)?
     SearchGraph (x, &p); SearchGraph (y,&q);
     r = (*p).Trail; Res = FALSE; 
     while ((r!=NULL)&&(!Res)) 
       if ((*r).Id==q) Res = TRUE; 
       else r = (*r).Next; 
     if (!Res) //Если дуга отсутствует, то поместим её в граф.
      { t = new (Trailer); (*t).Id = q; 
        (*t).Next = (*p).Trail; (*p).Trail = t; (*q).Count++; } 
     cout<<"Вводите начальную вершину дуги: "; cin>>x;
  }
}

void Spisok::PrintGraph ()
//Вывод структуры Вирта, заданной указателем 
//Head и соответствующей ориентированному графу.
{
  Lref p; //Рабочий указатель.
  Tref q; //Рабочий указатель.

  p = Head;
  while (p!=Tail)
  {
     cout<<"("<<(*p).Key; q = (*p).Trail; 
     while (q!=NULL) 
      { cout<<(*(*q).Id).Key; q = (*q).Next; } 
     cout<<")"; p = (*p).Next; cout<<" ";
  }
}

void Spisok::W_S (svqz *stk, TipElement el)
//Помещение элемента el в стек stk.
{
  svqz q=new (St);
  (*q).Element = el; (*q).Sled = *stk; *stk = q;
}

void Spisok::YDALENIE (svqz *stk, TipElement *klad)
//Удаление звена из стека, заданного указателем *stk. 
//Значение информационного поля удаляемого звена сохраня- 
//ется в параметре klad.
{
  svqz q;

  if (*stk==NULL) cout<<"Попытка выбора из пустого стека!\n";
  else
   { *klad = (**stk).Element; q = *stk; *stk = (**stk).Sled; delete q; }
}

void Spisok::DeleteGraph (int x,int y)
//Функция возвращает указатель *Head на структуру 
//Вирта, соответствующую ориентированному графу и
//полученную удалением дуги (x,y).
{
  Lref p,q; //Рабочие указатели.
  Tref t,r; //Рабочие указатели.
  Boolean Res; //Флаг наличия дуги.

  // Определим, существует ли в графе дуга (x,y)? 
  p = Search (x);q = Search (y);
  if ((p!=NULL) && (q!=NULL))
  { // Вершины в графе есть. 
     r = (*p).Trail; Res = FALSE; 
     while ((r!=NULL) && (!Res)) 
     if ((*r).Id==q) Res = TRUE; 
     else r = (*r).Next; 
     if (Res) //Если дуга существует, то удалим её.
       if (r==(*p).Trail) 
        { (*p).Trail = (*(*p).Trail).Next; delete r; (*q).Count--; } 
       else { 
           t = (*p).Trail; 
          while ((*t).Next!=r) t = (*t).Next; 
          (*t).Next = (*(*t).Next).Next; delete r; (*q).Count--; }
  }
}

Lref Spisok::Search (int w)
//Функция возвращает указатель на заголовочный узел с 
//ключом w. Если узел отсутствует, то функция возвращает 
//NULL.
{
  Lref h;

  h = Head;
  (*Tail).Key = w; //Поиск "с барьером".
  while ((*h).Key!=w) h = (*h).Next;
    if (h==Tail) //В списке заголовочных узлов нет узла с ключом w.
      h = NULL;
  return h;
}

void Spisok::Euler ()
//Построение эйлерова цикла в связном графе без вершин нечетной
//степени, заданном  структурой  Вирта. Начало цикла определено
//указателем Head.
{
  Lref v,u; //Рабочие переменные.
  svqz q;   //Рабочая переменная.

  svqz Stack =NULL, CE = NULL;
  W_S (&Stack,Head);
  while (Stack!=NULL)
  {
    //Взглянем на верхний элемент стека Stack...
    v = Stack->Element;
	 if  (v->Trail!=NULL)
    {
      u = v->Trail->Id;
		W_S (&Stack,u);
      DeleteGraph (v->Key,u->Key);
      DeleteGraph (u->Key,v->Key);
    }
    else
    {
      YDALENIE (&Stack,&v);
      W_S (&CE,v);
    }
  }
  //В стеке CE хранится эйлеров цикл.
  q = CE;
  while  (q!=NULL)
  {  cout << q->Element->Key << ' '; q = q->Sled; }
}
Текст этой программы можно взять здесь.

    Замечания.
  1. Приведем алгоритм построения эйлеровой цепи в данном эйлеровом графе. Этот метод известен под названием алгоритма Флёри.

        Теорема [2, с.45-46].

        Пусть G - эйлеров граф; тогда следующая процедура всегда возможна и приводит к построению эйлеровой цепи графа G. Выходя из произвольной вершины u, идем по ребрам графа произвольным образом, соблюдая лишь следующие правила:

    • стираем ребра по мере их прохождения и стираем также изолированные вершины, которые при этом образуются;
    • на каждом этапе идем по мосту только тогда, когда нет других возможностей (или другими словами, не проходить по ребру, если удаление этого ребра приводит к разбиению графа на две связные компоненты).

  2. В монографии [4, с.173-175] изложен "изящный и практически эффективный алгоритм Хоанг Туя (1964 г.). При этом, правда, предполагается, что для нахождения какой-нибудь цепи между двумя заданными вершинами, а значит, и цикла, содержащего заданное цикловое ребро, достаточно хорошие алгоритмы известны.

  3. Ребрам графа G приписаны положительные веса. Требуется найти цикл, проходящий через каждое ребро графа G по крайней мере один раз и такой, что для него общий вес (а именно сумма величин nj*c(aj), где числа nj показывают, сколько раз проходилось ребро aj, а c(aj) - вес ребра) минимален.

        Очевидно, что если G содержит эйлеров цикл, то любой такой цикл будет оптимальным, так как каждое ребро проходится только один раз и вес этого цикла равен тогда сумме c(aj), где j изменяется от 1 до m.

        Сформулированная задача называется задачей китайского почтальона [5, с.230-231].

  4. Кёнигсберг (теперь Калининград) расположен на обоих берегах реки Преголя и на двух островах этой реки. Берега реки и два острова соединены семью мостами. Вопрос - поставленный в 1736 г. - состоит в том, можно ли, начав с некоторой точки, совершить прогулку и вернуться в исходную точку, пройдя по каждому мосту ровно один раз. Если каждый берег реки и острова считать вершиной графа, а каждый мост - ребром, то карту можно представить в виде графа, а ответ на поставленный вопрос зависит теперь от существования эйлерова цикла в этом графе.

        Отрицательное решение Л.Эйлером (Commentarii Acad.Petropoletanae 8(1736),128-140) этой задачи, по-видимому, можно считать первой печатной научной работой по несуществовавшей тогда теории графов.

        Типичной задачей по эйлеровым графам является задача с такой постановкой: можно ли нарисовать какую-нибудь диаграмму (соединив данные точки линией), не отрывая карандаша от бумаги и не проходя никакую линию дважды.

  5. [6, с.39]. Эйлеровым графом может быть представлен, например, план выставки; это позволяет так расставить указатели маршрута, чтобы посетитель смог пройти по каждому залу в точности по одному разу.

   

(1) Липский В. Комбинаторика для программистов. - М.: Мир, 1988. - 213 с.
(2) Уилсон Р. Введение в теорию графов. - М.: Мир, 1977. - 207 с.
(3) Берж К. Теория графов и ее применения. - М.: ИЛ,1962. - 320 с.
(4) Зыков А.А. Основы теории графов. М.: Наука, 1987. - 384 с.
(5) Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978. - 432 с.
(6) Березина Л.Ю. Графы и их применение. - М.: Просвещение, 1979. - 143 с.

    Со следующего шага мы начнем рассматривать алгоритмы на графах.




Предыдущий шаг Содержание Следующий шаг