Задача о паросочетаниях

Докажите, что задача о паросочетаниях (есть п мальчиков и п девочек, известно, какие нары согласны друг с другом танцевать надо определить, мол<но ли устроить танец, в котором все п мальчиков и п девочек соединены в пары) принадлежит NP и, более того, припадле-л<ит Р. [c.36]

Принадлежность задачи о паросочетаниях классу МР очевидна Мерлину достаточно разбить мальчиков и девочек на пары, после чего Артур сможет убедиться, что пар ровно п и все выбранные пары согласны танцевать. [c.158]

Доказательство ирниадлежностн Р будем проводить, переформулировав задачу в терминах теории графов. Есть двудо.льный граф (рёбра соединяют только вершины из разных долей), нужно проверить, существует ли совершенное паросочешание, т.е. такой набор рёбер, что каждая вершина инцидентна ровно одному ребру из набора (если каждая вершина графа инцидентна не более чем одному ребру из набора, то такой набор называется паросочетание.м, размер паросочетания — количество входящих в него рёбер). [c.158]

Итак, мы доказали, что задача о паросочетаниях принадлежит Р. Описанный выиге алгоритм ие оптимален, читателю предлагается подумать, как можно его ускорить. [c.160]

Для задачи о взвешенном паросочетании известны полиномиальные алгоритмы (см., например, [11, гл. И], где онисан алгоритм, основанный на идеях линейного нрограммировання). [c.187]

Справочник химика 21

Химия и химическая технология