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

Перейти к навигации Перейти к поиску
нет описания правки
(Новая страница: «'''Convex bipartite graph''' --- выпуклый двудольный граф. Let <math>G = (X,Y,E)</math> be a ''bipartite graph''. An ordering of <math>X</mat…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Convex bipartite graph''' --- выпуклый двудольный граф.  
'''Convex bipartite graph''' — ''[[выпуклый двудольный граф]].''


Let <math>G = (X,Y,E)</math> be a ''bipartite graph''. An ordering of <math>X</math> has
Let <math>\,G = (X,Y,E)</math> be a ''[[bipartite graph]]''. An ordering of <math>\,X</math> has
the '''adjacency property''' if for each <math>y \in Y</math> the neighbors of
the '''[[adjacency property]]''' if for each <math>\,y \in Y</math> the neighbors of <math>\,y</math> in <math>\,X</math> are consecutive in the ordering of <math>\,X</math>. A bipartite graph
<math>y</math> in <math>X</math> are consecutive in the ordering of <math>X</math>. A bipartite graph
<math>\,G</math> is called '''convex bipartite''' if there is an ordering of <math>\,X</math> or of <math>\,Y</math> that has the adjacency property. A bipartite graph <math>\,G = (X,Y,E)</math> is '''[[biconvex bipartite graph|biconvex]]''' if there is an ordering of <math>\,X</math> and <math>\,Y</math> with the
<math>G</math> is called '''convex bipartite''' if there is an ordering of <math>X</math> or of <math>Y</math>
adjacency property. Convex graphs contain the ''[[bipartite permutation graph|bipartite permutation graphs]]''.
that has the adjacency property. A bipartite graph <math>G = (X,Y,E)</math> is
 
'''biconvex''' if there is an ordering of <math>X</math> and <math>Y</math> with the
==Литература==
adjacency property. Convex graphs contain the ''bipartite permutation graphs''.
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Навигация