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

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

[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]; Каждому ребру [math](u,w) \in E(G)[/math] соответствует ребро [math](e(u),e(w))[/math], причем ни для каких двух ребер из [math]E(G)[/math] концы соответствующих им ребер в [math]G^*[/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]. В результате для каждой вершины [math]v \in V(G)[/math] Множество [math]S(v)\cup T(v)[/math] образует полный двудольный граф.

Граф [math]G[/math] и соответствующий ему граф [math]G^*[/math]

Теорема:

Граф [math]G[/math] имеет [math]f[/math]-фактор тогда и только тогда, когда соответствующий данным графу и функции граф [math]G^*[/math] имеет совершенное паросочетание.

Доказательство:

[math]\triangleright[/math]

[math]\Rightarrow[/math] Пусть граф [math]G[/math] имеет [math]f[/math]-фактор [math]G_f[/math]. Построим паросочетание [math]M[/math] для графа [math]G^*[/math] следующим образом: Для каждого ребра [math](u,w)\in G_f[/math] добавим в [math]M[/math] соответствующее ему ребро из [math]G^*[/math] . Теперь для каждой вершины [math]v \in V(g)[/math] [math]f(v)[/math] вершин из множества [math]S(v)[/math] покрыты [math]M[/math] . Для каждой вершины [math]v \in V(g)[/math] пусть [math]R(v)\subset S(v)[/math] - множество вершин еще не покрытых [math]M[/math]. [math]R(v)\cup T(v)[/math] является полным двудольным графом, причем размер каждой из долей равен [math]deg(v)-f(v)[/math], следовательно этот граф имеет совершенное паросочетание [math]M_v[/math]. Добавим каждое ребро из [math]M_v[/math] в [math]M[/math]. В результате каждая вершина в [math]G^*[/math] покрыта [math]M[/math], следовательно [math]M[/math] является совершенным паросочетанием. [math]\Leftarrow[/math] Пусть [math]G^*[/math] имеет совершенное паросочетание [math]M[/math]. Для каждой вершины [math]v\in V(G)[/math] [math]T(v)[/math] является независимым множеством и полностью покрыто [math]M[/math], следовательно множество [math]R(v)\subset S(v)[/math] покрыто ребрами, концы которых лежат в [math]T(v)[/math], а значит каждая вершина из [math]S(v)\setminus R(v)[/math] покрыта ребром, второй конец которого принадлежит [math]S(w) : w \in V(G)[/math], причем [math]|S(v)\setminus R(v)| = deg(v)-(deg(v)-f(v))=f(v)[/math]. Поэтому если мы добавим в [math]G_f[/math] все ребра соответствующие ребрам из [math]M[/math] покрывающим [math]S(v)\setminus R(v) : v \in V(G)[/math], то есть все ребра из [math]M[/math] концы которых лежат в множествах [math]S[/math], то степень каждой вершины [math]v \in G_f[/math] будет равна [math]f(v)[/math], а значит [math]G_f[/math] будет являться [math]f[/math]-фактором.

[math]\triangleleft[/math]

Из доказательства напрямую следует, что задача о поиске произвольного [math]f[/math]-фактора графа [math]G[/math] сводится к поиску совершенного паросочетания в графе [math]G^*[/math]. Т.к. [math]G^*[/math] в общем случае не является двудольным, для решения этой задачи можно воспользваться Алгоритмом Эдмондса для поиска наибольшего паросочетания.