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

Дефицит двудольного графа (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] является множеством без дефицита, если никакое его подмножество не имеет положительного дефицита. Понятие дефицита используется при доказательстве теорем о паросочетаниях для двудольных графов.

Литература

• Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.

• Оре О. Теория графов. — М.: Наука, 1968.