Graft

Материал из WikiGrapp
Версия от 16:09, 16 мая 2011; Glk (обсуждение | вклад) (Новая страница: «'''Graft''' --- графт. Let <math>G = (A,B;E)</math> be a bipartite connected graph and <math>T \subseteq A \cup B</math> be a subset of vertices of even cardi…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Graft --- графт.

Let [math]\displaystyle{ G = (A,B;E) }[/math] be a bipartite connected graph and [math]\displaystyle{ T \subseteq A \cup B }[/math] be a subset of vertices of even cardinality. The pair [math]\displaystyle{ (G,T) }[/math] is called a bipartite graft. An edge set [math]\displaystyle{ F \subseteq E }[/math] is a [math]\displaystyle{ T }[/math]-join if [math]\displaystyle{ T =\{ v \in A \cup B: \; d_{F}(v) \mbox{ is odd}\} }[/math]. The minimum size of a [math]\displaystyle{ T }[/math]-join is denoted by [math]\displaystyle{ \tau(G,T) }[/math]. We mention that a bipartite graft [math]\displaystyle{ (G,T) }[/math] always contains a [math]\displaystyle{ T }[/math]-join.