Лексикографический поиск в ширину - Lexicographic breadth-first search

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

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

Фон

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

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

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

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

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

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

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

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

Алгоритм

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

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

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

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

Приложения

Хордовые графы

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

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

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

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

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

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

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

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

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

LexBFS заказ

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

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