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…») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 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>. | |||
Текущая версия от 10:44, 24 октября 2018
Clique — клика.
This is a subgraph [math]\displaystyle{ \,G[W] }[/math] induced by [math]\displaystyle{ W \subseteq V(G) }[/math] such that every pair of vertices is adjacent. The clique size of a clique [math]\displaystyle{ \,G[W] }[/math] is the number of vertices of [math]\displaystyle{ \,W }[/math]. The maximum clique size of a clique in [math]\displaystyle{ \,G }[/math], [math]\displaystyle{ \,\omega(G) }[/math], is called the clique number of [math]\displaystyle{ \,G }[/math]. The clique number [math]\displaystyle{ \,\Omega(G,w) }[/math] of a weighted graph is defined as the minimum weight of a clique in [math]\displaystyle{ \,G }[/math].
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.