Індукований граф та індукована ширина завдання УО
Введемо поняттяіндукованого графатаіндукованої ширини(induced width) задачі УО, важливі для застосування структурних методів розв'язання задач УО. Індукована ширина визначається термінах графа обмежень завдання УО.
Використовуємо поняття упорядкування графа чи завдання УО.
Визначення 10.4. Розглянемо граф або завдання УО , де .Упорядкуваннямдля графа чи завдання УО називається бієкція.
Упорядкування відповідає вершинам або змінним, які переглядаються в порядку . Якщо дві змінні з'єднані в графі рубом, іноді корисно уявити першу змінну, яка стоїть раніше в упорядкуванні, у вигляді «батька», а другу як «сина» першої вершини.
Перед визначенням індукованої ширини введемо простіше поняттяшириниграфа.
Визначення 10.5. Нехай - граф, а - деяке впорядкування вершин цього графа.Шириноювершини для цього впорядкування називається число вершин, з'єднаних з і попередніх їй в цьому упорядкуванні (тобто число батьків). Шириною графа для упорядкування називається максимальна ширина всіх вершин цього упорядкування. І, нарешті, шириною графа називається мінімальна ширина для всіх упорядкувань. Наприклад, дерево має ширину 1, а повний граф з вершинами має ширину. Введемо далі такі визначення:
Визначення 10.6. Шириною завдання УО для цього упорядкування називається ширина його графа обмежень для цього впорядкування, а ширина ЗУО визначається як ширина її графа обмежень.
Введемо поняття індукованого графа стосовно даного упорядкування.
Визначення 10.7. Для даного графа і впорядкування , індукований граф визначається як граф з мінімальною кількістю ребер , таких що , і якщо , , , , і , то.
Індукований граф може бути побудований за один прохід, обробляючи вершини вихідного графа у зворотному порядку; тобто спочатку з'єднуємо батьків останньої вершини, потім батьків передостанньої вершини тощо.
Визначення 10.8. Індукована ширина графа по відношенню до впорядкування - це ширина індукованого графа по відношенню до цього впорядкування.
Індукована ширина графа – це його мінімальна індукована ширина за всіма впорядкуваннями.
Індукована ширина завдання УО по відношенню до впорядкування - це індукована ширина її графа обмежень щодо цього впорядкування, а індукована ширина завдання УО - це індукована ширина її графа обмежень. Синонім індукованої ширини – деревоподібна ширина (див. розділ 8.5.3).
Відомо, що дана задача УО при заданому упорядкуванні може бути вирішена за час, експонентний від індукованої ширини по відношенню до цього впорядкування.
Хордальні графи
Граф називаєтьсяхордальним, якщо кожен цикл довжини 4 має хорду.
Багато важких графових завдань легко вирішуються на хордальних графах. Обчислення індукованої ширини досить просто для хордальних графів. Наприклад, знаходження всіх максимальних клік у графі, що є NP-повним завданням на графах загального вигляду, легко зробити для хордальних графів. Це завдання (пошук максимальних клік у хордальних графах) полегшується за рахунок використання процедури впорядкуванняmax-cardinality.
Упорядкуванняmax-cardinality[7]графа впорядковує вершини, починаючи з першої, згідно з таким правилом: перша вершина вибирається довільно. Після цього наступної вибирається вершина, з'єднана з максимальним числом вже впорядкованих вершин і т.д. Можна, можливопоказати, що впорядкування max-cardinality може бути використане для розпізнавання хордальних графів. Саме, граф - хордальний, тоді і тільки тоді, коли при впорядкуванні max-cardinality кожна вершина разом з її предками утворює кліку. Таким чином можна перерахувати всі максимальні кліки, що відповідають кожній вершині (записуючи множини, що складаються з кожної вершини та її батьків, і визначаючи потім максимальний розмір кліки). Зауважимо, що у хордальному графі є трохи більше клік, які з вершин та його предків.
Крім того, при використанні впорядкування max-cardinality хордального графа, упорядкований граф ідентичний його індукованому графу і, отже, його ширина дорівнює його індукованій ширині. Справедливо
Пропозиція. Якщо - індукований граф графа для деякого впорядкування, тоді граф - хордальний.