Clique graph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Clique graph''' --- граф клик. The '''clique graph''' <math>k(G)</math> is the ''intersection graph'' of the set of all cliques of <math>G</math>. The '…») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Clique graph''' | '''Clique graph''' — ''[[граф клик]].'' | ||
The '''clique graph''' <math>k(G)</math> is the ''intersection graph'' of the | The '''clique graph''' <math>\,k(G)</math> is the ''[[intersection graph]]'' of the | ||
set of all cliques of <math>G</math>. The '''iterated clique graphs''' are | set of all [[clique|cliques]] of <math>\,G</math>. The '''[[iterated clique graph|iterated clique graphs]]''' are defined recursively by <math>\,k^{0}(G) = G</math> and <math>\,k^{n+1}(G) = k(k^{n}(G))</math>. A [[graph, undirected graph, nonoriented graph|graph]] <math>\,G</math> is said to be '''[[clique divergent]]''' (or '''[[k-Divergent graph|<math>\,k</math>-divergent]]''') if | ||
defined recursively by <math>k^{0}(G) = G</math> and <math>k^{n+1}(G) = k(k^{n}(G))</math>. | |||
A graph <math>G</math> is said to be '''clique divergent''' (or '''<math>k</math>-divergent''') if | |||
<math>\lim_{n \rightarrow \infty} |V(k^{n}(G)| = \infty.</math> | ::::::<math>\lim_{n \rightarrow \infty} |V(k^{n}(G)| = \infty.</math> | ||
A graph <math>G</math> is said to be '''<math>k</math>-convergent''' if <math>k^{n}(G) \cong | A graph <math>\,G</math> is said to be '''[[k-Convergent|<math>\,k</math>-convergent]]''' if <math>k^{n}(G) \cong k^{m}(G)</math> for some <math>n \neq m</math>; when <math>\,m = 0</math>, we say that <math>\,G</math> is '''[[k-invariant graph|<math>\,k</math>-invariant]]'''. <math>\,G</math> is '''[[k-Null graph|<math>\,k</math>-null]]''' if <math>\,k^{n}(G)</math> is trivial (one [[vertex]]) for some <math>\,n</math> (clearly, a special case of a <math>\,k</math>-covergent | ||
k^{m}(G)</math> for some <math>n \neq m</math>; when <math>m = 0</math>, we say that <math>G</math> is '''<math>k</math>-invariant'''. <math>G</math> is '''<math>k</math>-null''' if <math>k^{n}(G)</math> is trivial (one | graph). It is easy to see that every graph is either <math>\,k</math>-convergent or <math>\,k</math>-divergent. | ||
vertex) for some <math>n</math> (clearly, a special case of a <math>k</math>-covergent | |||
graph). It is easy to see that every graph is either <math>k</math>-convergent or | ==Литература== | ||
<math>k</math>-divergent. | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 10:47, 24 октября 2018
Clique graph — граф клик.
The clique graph [math]\displaystyle{ \,k(G) }[/math] is the intersection graph of the set of all cliques of [math]\displaystyle{ \,G }[/math]. The iterated clique graphs are defined recursively by [math]\displaystyle{ \,k^{0}(G) = G }[/math] and [math]\displaystyle{ \,k^{n+1}(G) = k(k^{n}(G)) }[/math]. A graph [math]\displaystyle{ \,G }[/math] is said to be clique divergent (or [math]\displaystyle{ \,k }[/math]-divergent) if
- [math]\displaystyle{ \lim_{n \rightarrow \infty} |V(k^{n}(G)| = \infty. }[/math]
A graph [math]\displaystyle{ \,G }[/math] is said to be [math]\displaystyle{ \,k }[/math]-convergent if [math]\displaystyle{ k^{n}(G) \cong k^{m}(G) }[/math] for some [math]\displaystyle{ n \neq m }[/math]; when [math]\displaystyle{ \,m = 0 }[/math], we say that [math]\displaystyle{ \,G }[/math] is [math]\displaystyle{ \,k }[/math]-invariant. [math]\displaystyle{ \,G }[/math] is [math]\displaystyle{ \,k }[/math]-null if [math]\displaystyle{ \,k^{n}(G) }[/math] is trivial (one vertex) for some [math]\displaystyle{ \,n }[/math] (clearly, a special case of a [math]\displaystyle{ \,k }[/math]-covergent graph). It is easy to see that every graph is either [math]\displaystyle{ \,k }[/math]-convergent or [math]\displaystyle{ \,k }[/math]-divergent.
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.