2.9. Подструктуры графа

2

Определения

.9.1. Клика

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

В

Примеры

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

2



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

 3

4 



6

5 

 1

 8

7 



9

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

Меры

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

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

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

Точное решение

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

Эвристические алгоритмы

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

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

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

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

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

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

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

Один из простейших жадных последовательных алгоритмов поиска максимальной клики носит английское название: 1-optlocalsearchwithaddmovefortheMCP.

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

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

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

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

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

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

3. CC:=CCv;

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

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

Пример

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

max_vPA{deg_G(PA)(v) } для начала алгоритма

1

3

6

--

2

2

3

4

--

3

3

1

2

4

5

7

--

4

4

2

3

5

6

--

1

6

5

5

3

4

6

7

8

--

6

1

3

4

5

7

9

--

7

8

9

7

5

6

8

9

--

8

5

7

9

--

9

6

7

8

--

deg₁(G)=2;deg₂(G)=2; deg₃(G)=5;

deg₄(G)=4;deg₅(G)=5; deg₆(G)=6;

deg₇(G)=4;deg₈(G)=3; deg₉(G)=3

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

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

СС:= 6

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

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

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

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

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

СС:= {3,6}.

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

PA:= {1,4,5}.

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

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

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

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

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

PA:= {4}.

Степень вершины 4 равна четырем.

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

CC:={3,4,5,6}.

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

PA:= { }.

PAпусто, алгоритм стоп.

Найдена максимальная клика (возможно максимальная) клика. В этом можно убедиться, вернувшись к рис.2.9.1.