Chain graph: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
(Новая страница: «'''Chain graph''' --- цепной граф. A ''bipartite graph'' <math>G = (P,Q,E)</math> is called a '''chain graph''' if there is an ordering <math>\pi</math> …»)
 
Нет описания правки
 
Строка 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.

Навигация