Дефицит двудольного графа: различия между версиями
Перейти к навигации
Перейти к поиску
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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> является множеством без дефицита, если никакое его подмножество не имеет положительного дефицита. Понятие дефицита используется при доказательстве теорем о паросочетаниях для двудольных графов. | ||
==Литература== | ==Литература== | ||
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990. | |||
* Оре О. Теория графов. — М.: Наука, 1968. | |||
Текущая версия от 13:39, 4 февраля 2011
Дефицит двудольного графа (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.