Clique polynomial: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Clique polynomial''' --- кликовый полином. Let <math>G</math> be a finite, simple graph and let <math>F</math> be a family of cliques. By a '''cl…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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. | |||
Текущая версия от 11:50, 11 ноября 2013
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.