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

'''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},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>.

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.

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>.

 

 

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