Аноним

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.