Клики

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

$G$

называется кликой графа

$G$

; другими словами, клика графа

$G$

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

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

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

Содержание Назад Вперед