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

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
[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]-фактором.


Примеры факторов в графе: (1) — [math]3[/math]-фактор, (2) — [math]f[/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]S(u)[/math] и [math]S(w)[/math], и соединим их ребром [math](e(u),e(w))[/math]. В результате каждой вершине [math]v \in V(G)[/math] будет соответствовать множество [math]S(v) \subset V(G^*)[/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]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] следующим образом:

  1. Для каждого ребра [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] .
  2. Для каждой вершины [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] в общем случае не является двудольным, для решения этой задачи можно воспользваться Алгоритмом Эдмондса для поиска наибольшего паросочетания.