4634
правки
Clique: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Новая страница: «'''Clique''' --- клика. This is a subgraph <math>G[W]</math> induced by <math>W \subseteq V(G)</math> such that every pair of vertices is adjacent. The '''c…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Clique''' | '''Clique''' — ''[[клика]].'' | ||
This is a subgraph <math>G[W]</math> induced by <math>W \subseteq V(G)</math> such that every pair of | This is a [[subgraph]] <math>\,G[W]</math> induced by <math>W \subseteq V(G)</math> such that every pair of [[vertex|vertices]] is [[adjacent vertices|adjacent]]. The '''[[clique size]]''' of a clique <math>\,G[W]</math> is the number of vertices of <math>\,W</math>. The maximum clique size of a clique in <math>\,G</math>, <math>\,\omega(G)</math>, is called the '''[[clique number]]''' of <math>\,G</math>. The clique number <math>\,\Omega(G,w)</math> of a ''[[weighted graph]]'' is defined as the minimum weight of a clique in <math>\,G</math>. | ||
vertices is adjacent. The '''clique size''' of a clique <math>G[W]</math> is the | |||
number of vertices of <math>W</math>. The maximum clique size of a clique in <math>G</math>, | ==Литература== | ||
<math>\omega(G)</math>, is called the '''clique number''' of <math>G</math>. | |||
The clique number | * Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | ||
<math>\Omega(G,w)</math> of a ''weighted graph'' is defined as the minimum | |||
weight of a clique in <math>G</math>. | |||