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

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

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

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

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

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

• Повторно вывести вершину 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, если такой w нет )
  • Если множество более ранних соседей v (исключая сам w ) не является подмножеством множества более ранних соседей w , то граф не является хордовым.
• Если цикл завершается, не показывая, что граф не является хордовым, то он является хордовым.

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

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

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

То же свойство справедливо и для более широкого класса графов, дистанционно-наследуемых графов : дистанционно-наследуемые графы идеально упорядочиваемы, причем идеальный порядок задается обратным лексикографическому порядку, поэтому лексикографический поиск в ширину можно использовать в сочетании с жадными алгоритмами раскраски, чтобы оптимально раскрасить их за линейное время. ^[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 \сигма}$${\displaystyle v_{1}}$${\displaystyle 1\leq i<j<k\leq n}$${\ displaystyle v_ {i} \ in N (v_ {k}) \ setminus N (v_ {j})}$${\displaystyle m<i}$${\ displaystyle v_ {m} \ in N (v_ {j}) \ setminus N (v_ {k})}$

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