Анотація: Незалежні безлічі, кліки, вершинні покриття. Три завдання. Стратегія перебору для завдання про незалежне безлічі. Евристики для завдання про незалежне безлічі. Наближений алгоритм для задачі про вершинному покритті. Перебір максимальних незалежних множин.
Незалежні безлічі, кліки, вершинні покриття
У багатьох задачах на графах потрібно знайти якийсь максимум або мінімум, наприклад, найбільший підграф із заданою властивістю, або розбиття графа на найменше число частин, які відповідають якимось умовам, і т.д. У решти лекціях розглядаються кілька завдань такого роду, що вважаються класичними в теорії графів. Деякі з них відомі як NP-важкі, для них розглядаються Переборні алгоритми, прийоми раціоналізації, евристики і наближені алгоритми. Для інших завдань викладаються відомі ефективні алгоритми.
три завдання
Незалежним безліччю вершин графа називається будь-яка множина попарно не суміжні вершин, тобто безліч вершин, що породжує порожній підграф. Незалежна безліч називається максимальним, якщо воно не є власним підмножиною іншого незалежного безлічі, і найбільшим, якщо воно містить найбільшу кількість вершин. Число вершин в найбільшому незалежному безлічі графа 
позначається через 
і називається числом незалежності графа. Завдання про незалежний безлічі полягає в знаходженні найбільшого незалежного безлічі.
Клікою графа називається безліч вершин, що породжує повний підграф, тобто безліч вершин, кожні дві з яких суміжні. Число вершин в кліці найбільшого розміру називається Кликова числом графа і позначається через 
. Очевидно, завдання про незалежне безлічі перетворюється в задачу про кліці і навпаки простим переходом від даного графа до додаткового графу 
, так що 
.
Верхове покриття графа - це така безліч вершин, що кожне ребро графа інцидентне хоча б однієї з цих вершин. Найменше число вершин в верховому покритті графа позначається через 
і називається числом верхового покриття графа. У графі на Мал. 9.1 найбільшим незалежним безліччю є безліч 
, Найбільшою клікою - безліч 
, Найменшим верховим покриттям - безліч 
.
Між завданнями про незалежне дуже багато і про вершинному покритті теж є проста зв'язок завдяки такого факту.
Теорема 1. підмножина 
безлічі вершин графа є верховим покриттям тоді і тільки тоді, коли 
- незалежне безліч.
Доказ. якщо - верхове покриття, то всяке ребро містить хоча б одну вершину з безлічі і, отже, немає жодного ребра, що з'єднує дві вершини з безлічі 
. отже, - незалежне безліч. Назад, якщо - незалежне безліч, то немає ребер, що з'єднують вершини з і, отже, у кожного ребра одна або обидві вершини належать множині . отже, - верхове покриття.
З цієї теореми випливає, що 
для будь-якого графа з 
вершинами.
Таким чином, всі три завдання тісно пов'язані один з одним, так що досить навчитися вирішувати одну з них, і ми будемо вміти вирішувати інші дві. Разом з тим відомо, що ці завдання NP-повні. Для таких завдань не відомо ефективних алгоритмів, а накопичений до теперішнього часу досвід робить правдоподібним припущення про те, що таких алгоритмів і не існує. Проте, алгоритми для подібних завдань розроблялися і продовжують розроблятися, і в деяких випадках вони можуть бути корисні. Всі ці алгоритми в тій чи іншій формі здійснюють перебір варіантів (число яких може бути дуже великим). Далі розглянемо один із способів такого перебору для завдання про незалежне безлічі.