Аноним

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

Материал из WEGA
нет описания правки
(Новая страница: «'''Clique graph''' --- граф клик. The '''clique graph''' <math>k(G)</math> is the ''intersection graph'' of the set of all cliques of <math>G</math>. The '…»)
 
Нет описания правки
 
Строка 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.