Дефицит двудольного графа: различия между версиями

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

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

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