Дефицит двудольного графа

Материал из WikiGrapp
Версия от 14:36, 13 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Дефицит двудольного графа''' (''Deficiency of a bipartite graph'') - для двудольного графа <...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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

Литература

[Лекции],

[Оре]