4634
правки
Chain graph: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Новая страница: «'''Chain graph''' --- цепной граф. A ''bipartite graph'' <math>G = (P,Q,E)</math> is called a '''chain graph''' if there is an ordering <math>\pi</math> …») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Chain graph''' | '''Chain graph''' — [[цепной граф]]. | ||
A ''bipartite graph'' <math>G = (P,Q,E)</math> is called a '''chain graph''' if there | A ''[[bipartite graph]]'' <math>\,G = (P,Q,E)</math> is called a '''chain graph''' if there | ||
is an ordering <math>\pi</math> of the vertices in <math>P</math>, <math>\pi: \; \{1, \ldots, | is an ordering <math>\,\pi</math> of the [[vertex|vertices]] in <math>\,P</math>, <math>\pi: \; \{1, \ldots, | ||
|P|\} \rightarrow P</math>, such that | |P|\} \rightarrow P</math>, such that | ||
| Строка 8: | Строка 8: | ||
N(\pi(|P|)).</math> | N(\pi(|P|)).</math> | ||
Here <math>N(v)</math> is a ''neighborhood''of <math>v</math>. It is known that <math>G</math> is a | Here <math>\,N(v)</math> is a ''neighborhood'' of <math>\,v</math>. It is known that <math>\,G</math> is a | ||
chain graph iff it does not contain an independent pair of edges (an | chain graph iff it does not contain an independent pair of [[edge|edges]] (an | ||
induced <math>2K_{2}</math>). | induced <math>\,2K_{2}</math>). | ||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||