Convex bipartite graph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Convex bipartite graph''' --- выпуклый двудольный граф. Let <math>G = (X,Y,E)</math> be a ''bipartite graph''. An ordering of <math>X</mat…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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. | |||
Текущая версия от 12:50, 24 января 2017
Convex bipartite graph — выпуклый двудольный граф.
Let [math]\displaystyle{ \,G = (X,Y,E) }[/math] be a bipartite graph. An ordering of [math]\displaystyle{ \,X }[/math] has the adjacency property if for each [math]\displaystyle{ \,y \in Y }[/math] the neighbors of [math]\displaystyle{ \,y }[/math] in [math]\displaystyle{ \,X }[/math] are consecutive in the ordering of [math]\displaystyle{ \,X }[/math]. A bipartite graph [math]\displaystyle{ \,G }[/math] is called convex bipartite if there is an ordering of [math]\displaystyle{ \,X }[/math] or of [math]\displaystyle{ \,Y }[/math] that has the adjacency property. A bipartite graph [math]\displaystyle{ \,G = (X,Y,E) }[/math] is biconvex if there is an ordering of [math]\displaystyle{ \,X }[/math] and [math]\displaystyle{ \,Y }[/math] with the adjacency property. Convex graphs contain the bipartite permutation graphs.
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.