Дефицит двудольного графа

Дефицит двудольного графа (Deficiency of a bipartite graph) - для двудольного графа [math]\displaystyle{ G = (X,Y,E) }[/math] наибольшая из величин [math]\displaystyle{ \delta(A) = |A| - |N(A)| }[/math], где [math]\displaystyle{ A }[/math] --- произвольное подмножество [math]\displaystyle{ X }[/math], а [math]\displaystyle{ N(A) }[/math] --- подмножество вершин из [math]\displaystyle{ Y }[/math], смежных с вершинами из [math]\displaystyle{ A }[/math]. Говорят, что множество [math]\displaystyle{ A }[/math] является множеством без дефицита, если никакое его подмножество не имеет положительного дефицита. Понятие дефицита используется при доказательстве теорем о паросочетаниях для двудольных графов.

Литература

[Лекции],

[Оре]