Реверсивный поиск и перебор поддеревьев графа

Большинство комбинаторных и оптимизационных проблем содержат в себе задачу обхода вершин некоего связного графа. Граф, как правило, имеет большой размер и не задан явно, иначе перебор его вершин не составил бы труда. Известна лишь какая-то начальная вершина; также для каждой полученной в процессе перебора вершины можно узнать список смежных с ней вершин. Задача проста: посетить все вершины графа по одному разу.

Существуют два классических алгоритма для решения этой задачи: поиск в глубину (depth-first search) и поиск в ширину (breadth-first search). Оба алгоритма требуют, кроме памяти для хранения «фронта» (стека или очереди) вершин, которые будут посещены, дополнительной памяти для запоминания тех вершин, которые уже посещены.

При некотором условии можно написать рекурсивный алгоритм обхода, не требующий запоминания посещённых вершин. Алгоритм был предложен в 1996 году и называется «реверсивный поиск» (reverse search) [1]. Для его работы требуется, чтобы для каждой вершины v графа была определена соседняя вершина f(v), имеющая максимальный «приоритет». f должна быть задана так, чтобы любой путь вида v → f(v) → f(f(v)) → ... заканчивался, и обязательно в одной и той же вершине v^*. Для определённости положим f(v^*)=v^*.

Простейший пример: пронумеруем вершины графа натуральными числами (p(v)) и определим f(v) как вершину, имеющую максимальный номер среди множества nei(v) всех соседей v. Конечно, не любая нумерация будет соответствовать критерию. На множестве V вершин графа функция p должна иметь единственный локальный максимум, он же и глобальный.


Рассмотрим граф T, множество вершин которого совпадает с V, а ребро между u и w есть, когда u=f(w) или w=f(u). Несложно показать, что этот граф будет деревом. На рисунке рёбра дерева обозначены стрелками, ведущими от v к f(v), по возрастанию номера вершины.

Собственно алгоритм реверсивного поиска очень прост:

1. Выбрать произвольную вершину v
   
2. Если v≠f(v), то присвоить v←f(v) и перейти к шагу 1
   
3. Положить на стек вершину v
   
4. Пока стек не пуст:
   1. Снять со стека вершину u
      
   2. «Посетить» u
      
   3. Для каждой вершины w ∈ nei(u):
      • Если f(w)=u, то положить w на стек

Шаги 1 и 2 предназначены для обнаружения корня дерева, а шаги 3 и 4 обходят это дерево в глубину. Обойдя все вершины дерева, процедура обойдёт все вершины исходного графа. Обход дерева делается в направлении, противоположном возрастанию функции p, отсюда название алгоритма.

После этого примера может создаться впечатление, что алгоритм вообще не имеет смысла, т.к. все заботы, связанные с отбрасыванием уже посещённых вершин, переложены на функцию f, и посчитать её не проще, чем обойти все вершины графа. Это не так: на многих графах, заданных неявно с использованием терминов какой-либо предметной области, функция f тривиально формулируется в тех же терминах. Авторы в своей статье приводят алгоритмы для перебора:

• триангуляций точек на плоскости
• остовных деревьев графа
• остовных деревьев графа на плоскости с непересекающимися рёбрами
  
• связных индуцированных подграфов графа
• вершин n-мерного выпуклого многогранника, заданного гиперплоскостями граней
• и других объектов

(Кроме того, рассматривается модификация алгоритма, допускающая наличие нескольких «локальных максимумов» в графе поиска.)

Мы покажем алгоритм перебора всех поддеревьев произвольного графа G, основанный на реверсивном поиске. Множество вершин V графа поиска соответствует множеству поддеревьев G. Мы будем считать, что между вершинами u и w есть ребро, если u получается из w добавлением или удалением одного ребра из графа G. Допустим, что рёбра графа G как-то упорядочены. Будем считать, что u=f(w), если u получается из w удалением максимального ребра (не считая тех рёбер, после удаления которых получается два дерева вместо одного). Нетрудно понять, что вершина v^* в таком случае будет соответствовать пустому подграфу G.

Небольшой пример: построим граф поиска всех поддеревьев графа из трёх вершин:
Каждый узел графа поиска соответствует одному из поддеревьев нашего графа; пустое поддерево не является исключением.

Направления стрелок соответствуют удалению рёбер с максимальным номером в исходном графе.

Шаги 1 и 2 алгоритма перебора поддеревьев соответствуют шагам 3 и 4 общего алгоритма реверсивного поиска, т.к. известно, что начальное поддерево — пустое и искать его не надо. Кроме того, держать поддеревья на стеке не требуется; можно вместо поддерева класть на стек рёбра исходного графа. Каждое ребро кладётся на стек дважды: первый раз для добавления в поддерево, второй раз для удаления из него.

1. Для каждого ребра e графа G
   
   • Положить e на стек
2. S ← пустой граф
   
3. Пока стек не пуст:
   
   1. Снять ребро j со стека
      
   2. Если j ∈ S:
      
      • Удалить j из S
   3. Иначе:
      
      1. Добавить j в S
         
      2. «Посетить» S
         
      3. Положить j на стек
         
      4. Для каждого ребра h графа G, соседнего с одним из рёбер S и не принадлежащего S:
         
         • S’ ← S + h
           
         • Если S’ — дерево и если h — максимальное ребро S’, содержащее вершину степени 1, то положить h на стек
           

Поддерево S’ получается добавлением ребра h к S. «Соседи» S’ в графе поиска — это поддеревья, полученные удалением одного ребра из S’. Поскольку соседи также должны являться деревьями, то из S’ можно удалять только «висячие» рёбра, т.е. такие, которые имеют вершину со степенью 1. S=f(S’), если h является максимальным из всех таких рёбер. Можно сказать, что h должно быть максимальным ребром из всех, которые могли быть добавлены в S' на последнем шаге. В этом и только в этом случае мы переходим к поддереву S'. Это даёт гарантию, что ни одно поддерево не будет посещено дважды. При обходе в ширину или в глубину избежать повторений так просто не получилось бы.

[1] David Avis, Komei Fukuda. Reverse search for enumeration. Discrete applied mathematics 65, pp. 21-46, 1996.