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.

Текущая версия от 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.