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

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