Подразделы

Другие разделы

Дата и время

19/12/2024 23:44:40

Авторизация

Зарегистрироваться
Восстановить пароль

Занятие 18

Эйлеров путь Задача: Уроборос Разбор задачи Топологическая сортировка Максимальное паросочетание Задача о назначениях

Эйлеров путь

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

Эйлеров путь в графе существует тогда и только тогда, когда:

граф связный и
содержит не более чем две вершины нечетной степени.

Для нахождения Эйлерова цикла можно использовать алгоритм "змеи" из книги Шеня.

Змея – это ненулевая последовательность из вершин графа, в которой две соседние вершины соединены ребром графа. Первая вершина последовательности – хвост змеи, а последняя – голова. При добавлении вершины в последовательность змея растет с головы, также возможно отрезать кончик хвоста, удалив первую вершину. Вначале змея состоит из единственной вершины. Далее действуем по следующему алгоритму:

while(змея включает не все ребра) {
  if(из головы выходит неиспользованное в змее ребро)
    удлинить змею этим ребром
  else {
    // хвост змеи находится в той же вершине, что и голова
    отрезать конец хвоста и добавить его к голове
    т.е. змея откусывает свой хвост
  }
}

Докажем, что мы достигнем цели.

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

2) Змея не укорачивается, поэтому либо она охватывает все ребра, либо, начиная с некоторого момента, будет иметь постоянную длину. Во втором случае змея будет бесконечно "скользить по себе". Это возможно, только если из всех вершин змеи не выходит неиспользованных ребер. Из связности следует, что использованы все ребра.

Модифицированный алгоритм, в котором для хранения тела змеи используется стек, а при невозможности удлинить змею голова отрезается и добавляется к стеку-результату, можно применить и для поиска Эйлерова пути. В качестве стартовой нужно взять вершину нечетной степени, а если таких нет, то любую вершину ненулевой степени.

int m[N][N]; // информация о ребрах графа
int p[K+1]; // для экономии памяти этот массив используем для 
            // хранения стека с телом змеи и стека-результата
            // стеки растут навстречу друг другу
int p1; // голова змеи
int p2; // вершина стека-результата
int s; // стартовая вершина
int n,k; // количество вершин и ребер
...
p1=0;
p2=k+1; 
p[p1]=s;
while(p1>=0)
{ 
  int i, v=p[p1];
  for(i=0; i<n; ++i)
    if(m[v][i]>0) // есть путь из вершины v
    { --m[v][i]; // вычеркиваем ребро, в прямом
      --m[i][v]; // и обратном направлении
      p[++p1]=i; // увеличиваем змею
      break;
    }
  if(i>=n) // зашли в тупик
    p[--p2]=p[p1--]; // возвращаемся к предыдущей вершине
                     // голову змеи помещаем в результат
}
if(p2>0)
{ // обошли не все ребра => граф не Эйлеров
  printf("IMPOSSIBLE\n");
}
else
{ for(int i=0; i<=k; ++i)
    printf("%d%c",p[i],i<k?' ':'\n');
}