logo search
Лекции ДМ

Двудольный граф. Условие существования двудольного графа

О

V1 V2

пределение. Граф G(V, X) называется двудольным, если множество его вершин можно разбить на два подмножества V1 и V2 таких, что V = V1  V2, V1  V2 = .Т.е. у любого ребра {v, w}  X , если v V1, то w  V2. Множества V1 и V2 называются долями графа. На рисунке представлен типичный двудольный граф.

Двудольные графы играют заметнуя роль в различных приложениях. С помощью двудольных графов решаются такие задачи, как назначение на должность, определение степени соответствия товара требованиям покупателей и другие аналогичные задачи на соответствия.

Сформулируем задачу назначения на должность.

Имеется m человек и m должностей. Любой человек может занимать некоторые из должностей в соответствии со своей квалификацией. Вопрос: можно назначение на должность произвести таким образом, чтобы занятая каждым человеком должность не противоречила его квалификации.

Сформулируем еще одну задачу, решаемую с помощью двудольного графа. Это задача назначения комиссии из представителей n специальностей из людей, проживающих в m городах, таким образом, чтобы в комиссию вошли хотя бы по одному представителю каждой специальности и хотя бы по одному жителю из каждого города. Причем требуется составить комиссию с наименьшим количеством членов.

Условие существования двудольного графа формулируется в следующем утверждении, которое примем без доказательства.

Граф G(V, X) двудольный  тогда и только тогда, когда все его простые циклы четной длины.

Если двудольный граф, в котором множеству V1 принадлежат m вершин, а множеству V2 – n вершин, полный, то он обозначается Кm,n . Приведем пример графа К3,3 .

  1.