Лексикографический поиск в ширину

В информатике лексикографический поиск в ширину или Lex-BFS — это с линейным временем для упорядочивания вершин графа алгоритм . Алгоритм отличается от поиска в ширину , но он создает порядок, соответствующий поиску в ширину.

Алгоритм лексикографического поиска в ширину основан на идее уточнения разделов и впервые был разработан Дональдом Дж. Роузом, Робертом Э. Тарджаном и Джорджем С. Люкером ( 1976 ). Более подробный обзор этой темы представлен Корнейлом (2004) .Он использовался в качестве подпрограммы в других графовых алгоритмах, включая распознавание хордальных графов и оптимальную раскраску дистанционно -наследственных графов .

Фон

Алгоритм поиска в ширину обычно определяется следующим процессом:

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

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

• Повторно выведите вершину v , выбирая на каждом шаге вершину v , которая еще не была выбрана и у которой есть предшественник (вершина, имеющая ребро к v ) как можно раньше в выводе.

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

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

Итак, когда две вершины v и w имеют одного и того же самого раннего предшественника, раньше, чем любые другие невыбранные вершины,стандартный алгоритм поиска в ширину упорядочит их произвольно. Вместо этого в этом случае алгоритм LexBFS будет выбирать между v и w на основе порядка вывода их последних предшественников.Если только у одного из них есть второй по рангу предшественник, который уже был выведен, выбирается именно этот.Если и v, и w имеют одного и того же второго по рангу предшественника, то связь разрывается путем рассмотрения их третьего по рангу предшественника и так далее.

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

Алгоритм

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

• Инициализируйте последовательность наборов Σ, чтобы она содержала один набор, содержащий все вершины.
• Инициализируйте выходную последовательность вершин как пустую.
• Пока Σ непусто:
  • Найдите и удалите вершину v из первого множества в Σ
  • Если первое множество в Σ теперь пусто, удалите его из Σ.
  • Добавьте v в конец выходной последовательности.
  • Для каждого ребра vw такого, что w все еще принадлежит множеству S в Σ:
    • Если набор S, содержащий w, еще не был заменен во время обработки v , создайте новый пустой набор замены T и поместите его перед S в последовательности; в противном случае пусть T будет множеством до S .
    • Переместите w из S в T , и если это приведет к тому, что S станет пустым, удалите S из Σ.

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

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

Приложения

Хордальные графы

Граф G считается хордальным, если его вершины имеют идеальный порядок исключения , такой порядок, что для любой вершины v соседи, которые встречаются позже в упорядочении, образуют клику. В хордальном графе обратным лексикографическому порядку всегда является идеальный порядок исключения. Следовательно, можно проверить, является ли граф хордальным за линейное время, с помощью следующего алгоритма:

• Используйте лексикографический поиск в ширину, чтобы найти лексикографический порядок G.
• Для каждой вершины v :
  • Пусть w будет соседом v , встречающимся до v , как можно ближе к v в последовательности.
    • (Перейти к следующей вершине v, такой вершины нет ) если
  • Если набор более ранних соседей v (исключая сам w ) не является подмножеством множества более ранних соседей w , граф не является хордальным.
• Если цикл завершается, не показывая, что граф не хордальный, то он хордальный.

Это приложение послужило первоначальной мотивацией, которая побудила Роуза, Тарьяна и Люкера (1976) разработать алгоритм лексикографического поиска в ширину.

Раскраска графа

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

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

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

Другие приложения

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

Заказ LexBFS

Перечисление вершин графа называется упорядочиванием LexBFS, если оно является возможным результатом применения LexBFS к этому графу.

Позволять $G=(V,E)$ быть графиком с $n$ вершины. Напомним, что $N(v)$ множество соседей $v$.Позволять $\sigma =(v_{1},\dots ,v_{n})$ быть перечислением вершин $V$.Перечисление $\sigma$ это порядок LexBFS (с исходным кодом $v_{1}$), если для всех $1\leq i<j<k\leq n$ с $v_{i}\in N(v_{k})\setminus N(v_{j})$, существует $m<i$ такой, что $v_{m}\in N(v_{j})\setminus N(v_{k})$.

Ссылки

• Брандштедт, Андреас ; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, ISBN  0-89871-432-Х .
• Бретшер, Анна; Корнейл, Дерек ; Хабиб, Мишель; Пол, Кристоф (2008), «Простой алгоритм распознавания кографов LexBFS с линейным временем» , SIAM Journal on Discrete Mathematics , 22 (4): 1277–1296, CiteSeerX   10.1.1.188.5016 , doi : 10.1137/060664690 .
• Корнейл, Дерек Г. (2004), «Лексикографический поиск в ширину - опрос», Теоретико-графовые методы в информатике: 30-й международный семинар, WG 2004, Бад-Хоннеф, Германия, 21–23 июня 2004 г., Пересмотренные статьи , Лекция Заметки по информатике, том. 3353, Springer-Verlag, стр. 1–19, номер документа : 10.1007/978-3-540-30559-0_1 .
• Хабиб, Мишель; МакКоннелл, Росс; Пол, Кристоф; Вьенно, Лоран (2000), «Lex-BFS и уточнение разделов с приложениями к транзитивной ориентации, распознаванию интервальных графов и тестированию последовательных», Theoretical Computer Science , 234 (1–2): 59–84, doi : 10.1016/S0304 -3975(97)00241-7 .
• Роуз, диджей; Тарьян, RE ; Люкер, Г.С. (1976), «Алгоритмические аспекты исключения вершин на графах», SIAM Journal on Computing , 5 (2): 266–283, doi : 10.1137/0205021 .