Deficiency of a graph

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

Deficiency of a graph --- дефицит графа.

Let M be a matching in a graph G. A vertex v is saturated by M if an edge of M is incident with v, otherwise v is said to be unsaturated.

The deficiency def(G) of the graph G is the number of vertices unsaturated by a maximum matching. Thus, if def(G) = 0, then G has a perfect matching.