74
правки
Изменения
Нет описания правки
== Задача о поиске произвольного <tex>f</tex>-фактора ==
Сведем задачу о поиске <tex>f</tex>-фактора к задаче о поиске наибольшего паросочетания.
Пусть дан граф <tex>G</tex> и функция <tex>f : V(G) \rightarrow \mathbb{N}</tex>. Построим граф <tex>G^*</tex> следующим образом.
# Для каждого ребра <tex>(u,w)\in E(G)</tex> добавим в граф <tex>G^*</tex> две новых вершины <tex>e(u)</tex> и <tex>e(w)</tex>, соответствующие <tex>u</tex> и <tex>w</tex>, и соединим их ребром. В результате каждой вершине <tex>v \in V(G)</tex> будет соответствовать множество <tex>S(v) \subset V(G_fG^*)</tex> такое что <tex>|S(v)|=deg(v)</tex>; Каждому ребру <tex>(u,w) \in E(G)</tex> соответствует ребро <tex>(e(u),e(w))</tex>, причем ни для каких двух ребер из <tex>E(G)</tex> концы соответствующих им ребер в <tex>G^*</tex> не пересекаются.
# Для каждой вершины <tex>v\in V(G)</tex> добавим в <tex>G^*</tex> новые <tex>deg(v)-f(v)</tex> вершин, образующие множество <tex>T(v)</tex>. Каждую вершину из <tex>T(v)</tex> свяжем ребром с каждой вершиной из <tex>S(v)</tex>. В результате для каждой вершины <tex>v \in V(G)</tex> Множество <tex>S(v)\cup T(v)</tex> образует полный двудольный граф.
