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