Cross

Материал из WikiGrapp
Перейти к:навигация, поиск

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

Given a bipartite graph B = (U \cup V,E), two non-adjacent edges e,e'\in E with e = (u_{1},v_{1}) and e' = (u_{2},v_{2}) are said to form a cross if (u_{1},v_{2}) \in E and (u_{2},v_{1}) \in E. 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 B is a set of edges E' \subseteq E with the property that no two edges e,e' \in E' are cross-adjacent. A cross-free coloring of B is a coloring of the edge set E subject to the restriction that no pair of cross-adjacent edges has the same color.

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

Литература

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