Лекция: Подструктуры графа

Определения

2.9.1. Клика

Кликой графа G=(V,E) называется любой полносвязный подграф графа G=(V,E).

Примеры

наибольшуюклику.

В данном примере имеется несколько клик с тремя вершинами (например, V={2,3,4}), однако наибольшая клика одна – V={3,4,5,6}

Рис.2.9.1. Клика и наибольшая клика графа

Меры

w(G) – число клики, равное числу вершин наибольшей клики.

Класс сложности

Нахождение клики графа относится к NP-полному классу, а проблема определения наибольшей клики – NP-тяжелая.

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

Существуют несколько типов эвристических алгоритмов решения проблемы наибольшей клики в полиномиальное время:

· последовательные жадные;

· локального исследования;

· генетические;

· нейронных сетей;

· муравьиные.

Простой алгоритм

Один из простейших жадных последовательных алгоритмов поиска максимальной клики носит английское название: 1-opt local search with add move for the MCP.

Введем следующие обозначения:

CC – текущая клика;

PA – множество вершин возможных добавлений, т.е. множество вершин, соединенных ребрами со всеми вершинами текущей клики СС;

degG(S)(v) – степень вершины vÎS в подграфе G(S), где SÎV.

1. Найти вершину v с max vÎPA{ degG(PA)(v) }(вершину с максимальной степенью);

2. Если имеется несколько вершин с той же степенью, то выбирается любая из них;

3. CC := CCÈv;

4. Построить множество PA и найти степени этого множества degG(PA)(i), iÎPA;

5. Повторить 1 до тех пор, пока PA:=0.

Задан граф и его таблица инцидентности:

deg1(G)=2;deg2(G)=2; deg3(G)=5; deg4(G)=4;deg5(G)=5; deg6(G)=6; deg7(G)=4;deg8(G)=3; deg9(G)=3

Шаг 1. Находим вершину с наибольшей степенью – вершину 6, ее степень равна 6.

Шаг 2. Текущая клика равна

СС:= 6

Шаг 3. Множество вершин, соединенных ребрами со всеми вершинами текущей клики (на первом шаге – это строка таблицы инцидентности для вершины 6), и их степени:

PA:= {1,3,4,5,7,8)

degG(PA): 2,5,4,5,4,3

Шаг 4. Выбираем из PA вершину с наибольшей степенью. Таких вершин две: 3 и 5. Произвольно выбираем вершину 3.

Шаг 5. Текущая клика равна:

СС:= {3,6}.

Шаг 6. Находим вершины, инцидентные ко всем вершинам текущей клики (имеющие ребра ко всем вершинам текущей клики):

PA:= {1,4,5}.

Их степени равны degG(PA): 2,4,5.

Шаг 7. Выбираем в РА вершину с наибольшей степенью – вершину 5.

Шаг 8. Текущая клика равна:

СС:= {3,5,6}.

Шаг 9. Находим вершины, инцидентные ко всем вершинам текущей клики (имеющие ребра ко всем вершинам текущей клики):