Clique graph: различия между версиями

'''Clique graph''' — ''[[граф клик]].''

The '''clique graph''' <math>\,k(G)</math> is the ''[[intersection graph]]'' of the

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

::::::<math>\lim_{n \rightarrow \infty} |V(k^{n}(G)| = \infty.</math>

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

graph). It is easy to see that every graph is either <math>\,k</math>-convergent or <math>\,k</math>-divergent.

 

 

* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.