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


Клики


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

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

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

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

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




Начало  Назад  Вперед



Книжный магазин