Изменения
Нет описания правки
{{Определение
|definition = '''<tex>nk</tex>-фактор''' — [[Основные определения теории графов|регулярный]] остовный подграф степени <tex>nk</tex>. Если граф <tex>G</tex> представляет собой сумму <tex>nk</tex>-факторов, то их объединение называется <tex>nk</tex>-факторизацией, а сам граф <tex>G</tex> назыается <tex>nk</tex>-факторизуемым.
}}
{{Определение
|definition = Пусть задана функция <tex>f : V(G) \rightarrow \mathbb{N}</tex>, такая что <tex>\forall~v \in V(G):f(v)\leq \text{deg}(v)</tex>. Тогда остовный подграф <tex>G_f</tex> в котором степень каждой вершины <tex>v</tex> равна <tex>f(v)</tex> называется '''<tex>f</tex>-фактором'''.
}}
[[Файл:1-A-general-graph-G-with-a-3-regular-factor-2-A-general-graph-G-with-an-f-factor (1).png|700px|thumb|right| Примеры факторов в графе: (1) {{---}} <tex>3</tex>-фактор, (2) {{---}} <tex>f</tex>-фактор (значения <tex>f(v)</tex> указаны возле вершин)]]
== Задача о поиске произвольного <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>S(u)</tex> и <tex>S(w)</tex>, и соединим их ребром <tex>(e(u),e(w))</tex>. В результате каждой вершине <tex>v \in V(G)</tex> будет соответствовать множество <tex>S(v) \subset V(G^*)</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> образует полный двудольный граф.
[[Файл:A-general-graph-G-with-an-f-factor-and-the-corresponding-simple-graph-G-with-a.png|700px|thumb|centre| Граф <tex>G</tex> и соответствующий ему граф <tex>G^*</tex>]]
{{Теорема
|statement =
Граф <tex>G</tex> имеет <tex>f</tex>-фактор тогда и только тогда, когда соответствующий графу <tex>G</tex> и функции <tex>f</tex> граф <tex>G^*</tex> имеет совершенное паросочетание.
|proof =
<tex>\Rightarrow</tex>
Пусть граф <tex>G</tex> имеет <tex>f</tex>-фактор <tex>G_f</tex>. Построим паросочетание <tex>M</tex> для графа <tex>G^*</tex> следующим образом:
# Для каждого ребра <tex>(u,w)\in G_f</tex> добавим в <tex>M</tex> соответствующее ему ребро из <tex>G^*</tex> . Теперь для каждой вершины <tex>v \in V(g)</tex> <tex>f(v)</tex> вершин из множества <tex>S(v)</tex> покрыты <tex>M</tex> .
# Для каждой вершины <tex>v \in V(g)</tex> пусть <tex>R(v)\subset S(v)</tex> {{---}} множество вершин еще не покрытых <tex>M</tex>. <tex>R(v)\cup T(v)</tex> является полным двудольным графом, причем размер каждой из долей равен <tex>deg(v)-f(v)</tex>, следовательно этот граф имеет совершенное паросочетание <tex>M_v</tex>. Добавим каждое ребро из <tex>M_v</tex> в <tex>M</tex>.
В результате каждая вершина в <tex>G^*</tex> покрыта <tex>M</tex>, следовательно <tex>M</tex> является совершенным паросочетанием.
<tex>\Leftarrow</tex>
Пусть <tex>G^*</tex> имеет совершенное паросочетание <tex>M</tex>. Для каждой вершины <tex>v\in V(G)</tex> <tex>T(v)</tex> является независимым множеством и полностью покрыто <tex>M</tex>, следовательно множество <tex>R(v)\subset S(v)</tex> покрыто ребрами, концы которых лежат в <tex>T(v)</tex>, а значит каждая вершина из <tex>S(v)\setminus R(v)</tex> покрыта ребром, второй конец которого принадлежит <tex>S(w) : w \in V(G)</tex>, причем <tex>|S(v)\setminus R(v)| = deg(v)-(deg(v)-f(v))=f(v)</tex>. Поэтому если мы добавим в <tex>G_f</tex> все ребра соответствующие ребрам из <tex>M</tex> покрывающим <tex>S(v)\setminus R(v) : v \in V(G)</tex>, то есть все ребра из <tex>M</tex> концы которых лежат в множествах <tex>S</tex>, то степень каждой вершины <tex>v \in G_f</tex> будет равна <tex>f(v)</tex>, а значит <tex>G_f</tex> будет являться <tex>f</tex>-фактором.
}}
Из доказательства напрямую следует, что для нахождения <tex>f</tex>-фактора графа <tex>G</tex> достаточно найти совершенное паросочетание в графе <tex>G^*</tex>. Т.к. <tex>G^*</tex> в общем случае не является двудольным, для решения этой задачи можно воспользваться [https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%B6%D0%B0%D1%82%D0%B8%D1%8F_%D1%86%D0%B2%D0%B5%D1%82%D0%BA%D0%BE%D0%B2 Алгоритмом Эдмондса для поиска наибольшего паросочетания] работающим за время <tex>O(E \cdot V^2)</tex>. Построение графа <tex>G^*</tex> можно выполнить за время <tex>O(E+V)</tex>. Поэтому итоговая асимптотика {{---}} <tex>O(E \cdot V^2)</tex>
== 1-факторизация ==
* Харари Фрэнк '''Теория графов''' Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* [http://en.wikipedia.org/wiki/Graph_factorization Wikipedia — Graph factorization]
* Factors and Factorizations of Graphs: Proof Techniques in Factor Theory / Jin Akiyama, Mikio Kano. — Springer Science & Business Media, 2011. ISBN 3642219187, 9783642219184.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]
