Максимальная клика - это метод, используемый для поиска наибольшего кластера вершин, в котором каждая вершина соединена друг с другом. Давайте посмотрим на пример. Мы исследуем каждую вершину и посмотрим, какой будет наибольший кластер следующего графа.
Посмотрим на первую вершину. Вершина 1 соединена с вершинами 2, 4 и 6. Нам нужно убедиться, что каждая из этих вершин также соединена друг с другом.
- Связана ли вершина 2 с вершиной 4? да
- Связана ли вершина 2 с вершиной 6? да
- Связана ли вершина 4 с вершиной 6? да
Похоже, что все вершины соединены друг с другом, поэтому текущая максимальная клика, которую мы наблюдаем, состоит из 4 вершин: 1, 2, 4 и 6.
Давайте рассмотрим вершину 2. Вершина 2 соединена с вершинами 1, 4, 3 и 5. Нам нужно убедиться, что каждая из этих вершин также связана друг с другом.
- Связана ли вершина 1 с вершиной 3? Нет
Нет смысла продолжать. Похоже, мы не можем использовать эту вершину в качестве центральной точки создания max-clique. Чтобы вершина 2 была центром максимальной клики, все вершины должны быть соединены, как показано ниже.
Рассмотрим вершину 3. Вершина 3 соединена с вершинами 2 и 8.
- Связана ли вершина 2 с вершиной 8? Нет
Чтобы быть частью клики, должно существовать ребро, соединяющее вершины 2–8.
Давайте рассмотрим вершину 4. Вершина 4 соединена с вершинами 1, 2, 4, 5 и 6. Нам нужно убедиться, что каждая из этих вершин также связана друг с другом.
- Связана ли вершина 1 с вершиной 2? да
- Связана ли вершина 1 с вершиной 5? Нет
Мы не можем использовать вершину 4 в качестве центральной точки создания max-клики. Чтобы создать клику, вершина 1 должна иметь ребро к вершине 5.
Давайте рассмотрим вершину 5. Вершина 5 соединена с вершинами 2, 4, 6, 7 и 8. Нам нужно убедиться, что каждая из этих вершин также связана друг с другом.
- Связана ли вершина 4 с 6? да
- Связана ли вершина 4 с 7? Нет
Мы не можем использовать вершину 5 в качестве центральной точки создания max-клики. Чтобы создать клику, все вершины должны быть соединены, как показано ниже.
Давайте рассмотрим вершину 6. Вершина 6 соединена с вершинами 1, 2, 4, 5 и 7. Нам нужно убедиться, что каждая из этих вершин также связана друг с другом.
- Соединена ли вершина 1 с 2? да
- Соединена ли вершина 1 с 4? да
- Связана ли вершина 1 с 5? Нет
Мы не можем использовать вершину 6 как центральную точку создания max-клики. Чтобы создать клику, все вершины должны быть соединены, как показано ниже.
Давайте рассмотрим вершину 7. Вершина 7 соединена с вершинами 5 и 6. Нам нужно убедиться, что каждая из этих вершин также соединена друг с другом.
- Связана ли вершина 5 с 6? да
Вершины 5, 6 и 7 действительно образуют клику, однако мы уже нашли большую клику, чем эта, так что это не максимальная клика.
Давайте рассмотрим вершину 8. Вершина 8 соединена с вершинами 3 и 5. Нам нужно убедиться, что каждая из этих вершин также соединена друг с другом.
- Связана ли вершина 3 с 5? Нет
Мы не можем использовать вершину 8 как центральную точку создания max-клики. Чтобы создать клику, вершина 3 должна быть соединена с вершиной 5.
Мы закончили рассматривать каждую из вершин. Максимальная клика, которую нам удалось найти, - это клика, состоящая из вершин 1, 2, 4 и 6.
Если вам понравилось то, что вы прочитали, посмотрите мою книгу Иллюстративное введение в алгоритмы.
