4624
правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Дефицит двудольного графа''' (''Deficiency of a bipartite graph'') - для двудольного графа <...) |
KEV (обсуждение | вклад) Нет описания правки |
||
(не показана 1 промежуточная версия этого же участника) | |||
Строка 1: | Строка 1: | ||
'''Дефицит двудольного графа''' (''Deficiency of a bipartite graph'') | '''Дефицит двудольного графа''' (''[[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> является множеством без дефицита, если никакое его подмножество не имеет положительного дефицита. Понятие дефицита используется при доказательстве теорем о паросочетаниях для двудольных графов. | ||
для двудольного графа <math>G = (X,Y,E)</math> наибольшая из величин <math>\delta(A) | |||
= |A| - |N(A)|</math>, где <math>A</math> | |||
что множество <math>A</math> является множеством без дефицита, если никакое его | |||
подмножество не имеет положительного дефицита. Понятие дефицита | |||
используется при доказательстве теорем о паросочетаниях для | |||
двудольных графов. | |||
==Литература== | ==Литература== | ||
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990. | |||
* Оре О. Теория графов. — М.: Наука, 1968. |