Дефицит двудольного графа: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Дефицит двудольного графа''' (''Deficiency of a bipartite graph'') - для двудольного графа <...) |
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>G = (X,Y,E)</math> наибольшая из величин <math>\delta(A) | --- подмножество [[вершина|вершин]] из <math>Y</math>, [[смежные вершины|смежных]] с вершинами из <math>A</math>. Говорят, что множество <math>A</math> является множеством без дефицита, если никакое его подмножество не имеет положительного дефицита. Понятие дефицита используется при доказательстве теорем о паросочетаниях для двудольных графов. | ||
= |A| - |N(A)|</math>, где <math>A</math> --- произвольное подмножество <math>X</math>, а <math>N(A)</math> | |||
--- подмножество вершин из <math>Y</math>, смежных с вершинами из <math>A</math>. Говорят, | |||
что множество <math>A</math> является множеством без дефицита, если никакое его | |||
подмножество не имеет положительного дефицита. Понятие дефицита | |||
используется при доказательстве теорем о паросочетаниях для | |||
двудольных графов. | |||
==Литература== | ==Литература== | ||
[Лекции], | [Лекции], | ||
[Оре] | [Оре] | ||
Версия от 18:24, 14 октября 2009
Дефицит двудольного графа (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] является множеством без дефицита, если никакое его подмножество не имеет положительного дефицита. Понятие дефицита используется при доказательстве теорем о паросочетаниях для двудольных графов.
Литература
[Лекции],
[Оре]