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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Cross''' --- скрещивание. Given a bipartite graph <math>B = (U \cup V,E)</math>, two non-adjacent edges <math>e,e' \in E</math> with <math>e = (u_{1}…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Cross''' --- скрещивание.  
'''Cross''' — ''[[скрещивание]].''


Given a bipartite graph <math>B = (U \cup V,E)</math>, two non-adjacent edges <math>e,e'
Given a [[bipartite graph]] <math>B = (U \cup V,E)</math>, two non-[[adjacent edges]] <math>e,e'\in E</math> with <math>e = (u_{1},v_{1})</math> and <math>e' = (u_{2},v_{2})</math> are said to form a '''cross''' if <math>(u_{1},v_{2}) \in E</math> and <math>(u_{2},v_{1}) \in E</math>.
\in E</math> with <math>e = (u_{1},v_{1})</math> and <math>e' = (u_{2},v_{2})</math> are said to
Two [[edge|edges]] are said to be '''[[cross-adjacent edges|cross-adjacent]]''' if either they are adjacent (i.e. share a common [[node]]) or they form a cross. A '''[[cross-free matching]]''' in <math>B</math> is a set of edges <math>E' \subseteq E</math> with the property that no two edges <math>e,e' \in E'</math> are cross-adjacent. A '''[[cross-free coloring]]''' of <math>B</math> is a ''coloring'' of the edge set <math>E</math> subject to the restriction that no pair of cross-adjacent edges has the same color.
form a '''cross''' if <math>(u_{1},v_{2}) \in E</math> and <math>(u_{2},v_{1}) \in E</math>.
Two edges are said to be '''cross-adjacent''' if either they are
adjacent (i.e. share a common node) or they form a cross. A '''cross-free matching''' in <math>B</math> is a set of edges <math>E' \subseteq E</math> with
the property that no two edges <math>e,e' \in E'</math> are cross-adjacent. A
'''cross-free coloring''' of <math>B</math> is a ''coloring'' of the edge set
<math>E</math> subject to the restriction that no pair of cross-adjacent edges
has the same color.


The '''cross-chromatic index''', <math>\chi^{\ast}(B)</math>, of <math>B</math> is the
The '''[[cross-chromatic index]]''', <math>\chi^{\ast}(B)</math>, of <math>B</math> is the minimum number of colors required to get a cross-free coloring of <math>B</math>. The '''[[cross-free matching number]]''' of <math>B</math>, <math>m^{\ast}(B)</math>, is defined as the edge cardinality of the maximum cross-free matching in <math>B</math>.
minimum number of colors required to get a cross-free coloring of <math>B</math>.
 
The '''cross-free matching number''' of <math>B</math>, <math>m^{\ast}(B)</math>, is defined as
==Литература==
the edge cardinality of the maximum cross-free matching in <math>B</math>.
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Текущая версия от 16:26, 7 ноября 2018

Crossскрещивание.

Given a bipartite graph [math]\displaystyle{ B = (U \cup V,E) }[/math], two non-adjacent edges [math]\displaystyle{ e,e'\in E }[/math] with [math]\displaystyle{ e = (u_{1},v_{1}) }[/math] and [math]\displaystyle{ e' = (u_{2},v_{2}) }[/math] are said to form a cross if [math]\displaystyle{ (u_{1},v_{2}) \in E }[/math] and [math]\displaystyle{ (u_{2},v_{1}) \in E }[/math]. Two edges are said to be cross-adjacent if either they are adjacent (i.e. share a common node) or they form a cross. A cross-free matching in [math]\displaystyle{ B }[/math] is a set of edges [math]\displaystyle{ E' \subseteq E }[/math] with the property that no two edges [math]\displaystyle{ e,e' \in E' }[/math] are cross-adjacent. A cross-free coloring of [math]\displaystyle{ B }[/math] is a coloring of the edge set [math]\displaystyle{ E }[/math] subject to the restriction that no pair of cross-adjacent edges has the same color.

The cross-chromatic index, [math]\displaystyle{ \chi^{\ast}(B) }[/math], of [math]\displaystyle{ B }[/math] is the minimum number of colors required to get a cross-free coloring of [math]\displaystyle{ B }[/math]. The cross-free matching number of [math]\displaystyle{ B }[/math], [math]\displaystyle{ m^{\ast}(B) }[/math], is defined as the edge cardinality of the maximum cross-free matching in [math]\displaystyle{ B }[/math].

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.