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

Лексикографічний пошук у ширину (Шаблон:Lang-en LBFS або Lex-BFS) — алгоритм упорядкування вершин графу. Алгоритм відрізняється від алгоритму пошуку в ширину і дає упорядкованішуШаблон:Невідомий термін послідовність вершин графу.

Алгоритм лексикографічного пошуку в ширину ґрунтується на ідеї Шаблон:Не перекладено і вперше його розробили Роуз, Тарджан і Люкер (1976). Детальніший огляд теми надав Шаблон:Нп (2004)Шаблон:Sfnp. Лексикографічний пошук у ширину використовується як частина в інших графічних алгоритмах, наприклад, розпізнавання хордальних графів, розфарбовування повністю розщеплюваних графів.

Приклад роботи алгоритму

Опис алгоритму

Для роботи алгоритму слід задати вершину графу, з якої починається обхід. Опис алгоритму виглядає так:

• Ініціалізувати послідовність множин вершин Σ що складається з однієї множини, яка містить усі вершини графу.
• Ініціалізувати порожню вихідну послідовність вершин.
• Поки Σ непорожня:
  • З першої множини в Σ взяти вершину v і видалити її з множини.
  • Якщо перша множина в Σ стала порожньою, видалити її з Σ.
  • Додати v в кінець вихідної послідовності вершин.
  • Для кожного ребра vw:
    • Визначити множину S в Σ яка містить w.
    • Якщо множина S ще не поділялася під час обробки v, створити нову порожню множину T і помістити її перед S у Σ.
    • Перемістити вершину w із S у T і, якщо S стала порожньою, видалити її з Σ.

Кожна вершина обробляється один раз, кожне ребро тестується тільки при обробці його двох вершин, і (в припущенні, що обробка операцій у послідовності множин Σ займає скінченний час) кожна ітерація внутрішнього циклу займає скінченний час. Отже, так само, як і для алгоритмів пошуку в глибину і пошуку в ширину, часова складність алгоритму є лінійною і становить $O(|V|+|E|)$.

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

Застосування

Алгоритм лексикографічного пошуку в ширину використовується для розпізнавання хордальних графів, розфарбовування цілком сепарабельних графів. Для розпізнавання графів порівнянності та інтервальних графів використовують багатомахові алгоритми (алгоритм лексикографічного пошуку в ширину з варіаціями застосовується кілька разів).

Література

• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation Архівна копія від 26 липня 2011 на Wayback Machine.
• Шаблон:Citation.