Обсуждение:Факторизация графов

Определение:

[math]k[/math]-фактор — регулярный остовный подграф степени [math]k[/math]. Если граф [math]G[/math] представляет собой сумму [math]k[/math]-факторов, то их объединение называется [math]k[/math]-факторизацией, а сам граф [math]G[/math] назыается [math]k[/math]-факторизуемым.

Определение:

Пусть задана функция [math]f : V(G) \rightarrow \mathbb{N}[/math], такая что [math]\forall~v \in V(G):f(v)\leq \text{deg}(v)[/math]. Тогда остовный подграф [math]G_f[/math] в котором степень каждой вершины [math]v[/math] равна [math]f(v)[/math] называется [math]f[/math]-фактором.

Задача о поиске произвольного [math]f[/math]-фактора

Пусть дан граф [math]G[/math] и функция [math]f : V(G) \rightarrow \mathbb{N}[/math]. Построим граф [math]G^*[/math] следующим образом.

1. Для каждого ребра [math](u,w)\in E(G)[/math] добавим в граф [math]G^*[/math] две новых вершины [math]e(u)[/math] и [math]e(w)[/math], соответствующие [math]u[/math] и [math]w[/math], и соединим их ребром. В результате каждой вершине [math]v \in V(g)[/math] будет соответствовать множество [math]S(v) \subset V(G_f^*)[/math] такое что [math]|S(v)|=deg(v)[/math].
2. Для каждой вершины [math]v\in V(G)[/math] добавим в [math]G^*[/math] новые [math]deg(v)-f(v)[/math] вершин, образующие множество [math]T(v)[/math]. Каждую вершину из [math]T(v)[/math] свяжем ребром с каждой вершиной из [math]S(v)[/math]