Клики
Максимальный полный подграф графа
называется кликой графа
; другими словами, клика графа
есть подмножество его вершин, такое, что между каждой парой вершин этого подмножества существует ребро и, кроме того, это подмножество не принадлежит никакому большому подмножеству с тем же свойством. Например, на рис. 12.2 показан граф и его клики.
Рис. 12.2. Граф G и все его клики
Клики графа представляют "естественные" группировки вершин, и определение клик графа полезно в кластерном анализе в таких областях, как информационный поиск и социология.
Содержание Назад Вперед