Размер максимального соответствия в двудольном графике

Ответы:

13

Для двудольного графа G=(U,V,E) и максимального соответствия M группы G помощью теоремы Кенига мы видим, что |M|=|C|где C является минимальной вершиной покрытия для G . Ваше утверждение - это просто верхняя граница размера возможного соответствия, а не строгое равенство.

Изображение на странице википедии представляет собой хороший контрпример к вашей заявке. Мы видим, что , а .|M|=6min(|U|,|V|)=7

введите описание изображения здесь

Однако в случае полного двудольного графа ваше утверждение выполнено.Kn,m

Николас Манкузо
источник
9

Нет. Например, рассмотрим случай, когда две стороны не связаны или случай, когда большая группа узлов подключена к одному и тому же узлу:|E|=0

U=u1,u2,...,un

V=v1,v2,...,vn

v 1 U 1 , v 2 U 1 , . , , v п U 1E=u1v1,u2v1,...unv1, v1u1,v2u1,...vnu1

hugomg
источник
конечно. Человек в следующий раз, мне нужно сначала подумать, прежде чем спросить что-то здесь.
УльтраДжон