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.

Текущая версия от 10:47, 24 октября 2018

Clique polynomialкликовый полином.

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

[math]\displaystyle{ w(C) = \prod_{\alpha \in C} w_{\alpha}. }[/math]

The clique polynomial of [math]\displaystyle{ \,G }[/math] is then:

[math]\displaystyle{ K(G;\vec{w}) = \sum_{C} w(C), }[/math]

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

Denote by [math]\displaystyle{ \,S(n,k) }[/math] the Stirling numbers of the second kind. Then

[math]\displaystyle{ K(K_{n};w) = \sum_{k=0}^{n} S_{n,k}w^{k}. }[/math]

Литература

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