Комбинаторные алгоритмы для программистов

         

Клики


Максимальный полный подграф графа

называется кликой графа
; другими словами, клика графа
есть подмножество его вершин, такое, что между каждой парой вершин этого подмножества существует ребро и, кроме того, это подмножество не принадлежит никакому большому подмножеству с тем же свойством. Например, на рис. 12.2 показан граф и его клики.


Рис. 12.2.  Граф G и все его клики

Клики графа представляют "естественные" группировки вершин, и определение клик графа полезно в кластерном анализе в таких областях, как информационный поиск и социология.



Содержание раздела