Cross: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''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}…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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.