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

Материал из WikiGrapp
Перейти к:навигация, поиск

Дефицит двудольного графа (Deficiency of a bipartite graph) — для двудольного графа G = (X,Y,E) наибольшая из величин \delta(A) = |A| - |N(A)|, где A — произвольное подмножество X, а N(A) — подмножество вершин из Y, смежных с вершинами из A. Говорят, что множество A является множеством без дефицита, если никакое его подмножество не имеет положительного дефицита. Понятие дефицита используется при доказательстве теорем о паросочетаниях для двудольных графов.

Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
  • Оре О. Теория графов. — М.: Наука, 1968.