Аноним

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

Материал из WEGA
нет описания правки
(Новая страница: «'''Clique polynomial''' --- кликовый полином. Let <math>G</math> be a finite, simple graph and let <math>F</math> be a family of cliques. By a '''cl…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Clique polynomial''' --- кликовый полином.  
'''Clique polynomial''' — ''[[кликовый полином]].''


Let <math>G</math> be a finite, simple graph and let <math>F</math> be a family of
Let <math>\,G</math> be a [[finite graph|finite]], [[simple graph]] and let <math>\,F</math> be a family of [[clique|cliques]]. By a '''[[clique cover]]''' of <math>\,G</math> we mean a ''[[spanning subgraph]]'' of <math>\,G</math>, each component of which is a member of <math>\,F</math>. With each element <math>\,\alpha</math> of <math>\,F</math> we associate an indeterminate (or weight) <math>\,w_{\alpha}</math> and with each cover <math>\,C</math> of <math>\,G</math> we associate the weight
cliques. By a '''clique cover''' of <math>G</math> we mean a ''spanning subgraph'' of <math>G</math>, each component of which is a member of <math>F</math>. With
each element <math>\alpha</math> of <math>F</math> we associate an indeterminate (or weight)
<math>w_{\alpha}</math> and with each cover <math>C</math> of <math>G</math> we associate the weight


<math>w(C) = \prod_{\alpha \in C} w_{\alpha}.</math>
:::::<math>w(C) = \prod_{\alpha \in C} w_{\alpha}.</math>


The '''clique polynomial''' of <math>G</math> is
The '''clique polynomial''' of <math>\,G</math> is then:
then:


<math> K(G;\vec{w}) = \sum_{C} w(C),</math>
:::::<math> K(G;\vec{w}) = \sum_{C} w(C),</math>


where the sum is taken over all the covers <math>C</math> of <math>G</math> and <math>\vec{w}</math> is
where the sum is taken over all the covers <math>\,C</math> of <math>\,G</math> and <math>\,\vec{w}</math> is the vector of indeterminates <math>\,w_{\alpha}</math>. If, for all <math>\,\alpha</math>, we set <math>\,w_{\alpha} = w</math>, then the resulting polynomial in the single
the vector of indeterminates <math>w_{\alpha}</math>. If, for all <math>\alpha</math>, we
variable <math>\,w</math> is called a '''simple clique polynomial''' of  <math>\,G</math>.
set <math>w_{\alpha} = w</math>, then the resulting polynomial in the single
variable <math>w</math> is called a '''simple clique polynomial''' of  <math>G</math>.


Denote by <math>S(n,k)</math> the Stirling numbers of the second kind. Then
Denote by <math>\,S(n,k)</math> the Stirling numbers of the second kind. Then


<math>K(K_{n};w) = \sum_{k=0}^{n} S_{n,k}w^{k}.</math>
:::::<math>K(K_{n};w) = \sum_{k=0}^{n} S_{n,k}w^{k}.</math>
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.