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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Unsaturated vertex''' --- свободная вершина. '''1.''' See '' Unary node''. '''2.''' A vertex <math>v</math> is ''' unsaturated''' by a '' mat…»)
 
(нет различий)

Текущая версия от 13:45, 18 августа 2011

Unsaturated vertex --- свободная вершина.

1. See Unary node.

2. A vertex [math]\displaystyle{ v }[/math] is unsaturated by a matching [math]\displaystyle{ M }[/math], if there is no edge of [math]\displaystyle{ M }[/math] incident with [math]\displaystyle{ v }[/math]. A matching [math]\displaystyle{ M }[/math] is called 1-factor (or a perfect matching), if there is no vertex of the graph unsaturated by [math]\displaystyle{ M }[/math].

The deficiency [math]\displaystyle{ def(G) }[/math] of [math]\displaystyle{ G }[/math] is the number of vertices unsaturated by a maximum matching of [math]\displaystyle{ G }[/math]. Observe that [math]\displaystyle{ def(G) = |V| - 2|M| }[/math] for any maximum matching [math]\displaystyle{ M }[/math] in [math]\displaystyle{ G }[/math].