Факторизация графов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 17 промежуточных версий 4 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition ='''Фактором ''' ''(англ. factor)'' [[Основные определения теории графов|графа]] <tex>G</tex> называется остовный подграф графа <tex>G</tex>, не являющийся вполне несвязным.
+
|definition ='''Фактором ''' ''(англ. factor)'' [[Основные определения теории графов|графа]] <tex>G</tex> называется [[Остовные деревья: определения, лемма о безопасном ребре|остовный подграф]] графа <tex>G</tex>, имеющий хотя бы одно ребро.
 
}}
 
}}
  
Строка 8: Строка 8:
  
 
{{Определение
 
{{Определение
|definition = '''<tex>n</tex>-фактор''' — регулярный остовный подграф степени <tex>n</tex>. Если граф <tex>G</tex> представляет собой сумму <tex>n</tex>-факторов, то их объединение называется <tex>n</tex>-факторизацией, а сам граф <tex>G</tex> назыается <tex>n</tex>-факторизуемым.
+
|definition = '''<tex>k</tex>-фактор''' — [[Основные определения теории графов|регулярный]] остовный подграф степени <tex>k</tex>. Если граф <tex>G</tex> представляет собой сумму <tex>k</tex>-факторов, то их объединение называется <tex>k</tex>-факторизацией, а сам граф <tex>G</tex> назыается <tex>k</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-факторизация ==
 
== 1-факторизация ==
 
{{Теорема  
 
{{Теорема  
 
|statement=
 
|statement=
Полный граф <tex>K_{2n}</tex> <tex>1</tex>-факторизуем.
+
[[Основные определения теории графов|Полный]] граф <tex>K_{2n}</tex> <tex>1</tex>-факторизуем.
 
|proof=
 
|proof=
 
[[Файл: Факторизация K6.png|thumb|360px|right|<tex>1</tex>-факторизация графа <tex>K_6</tex>]]
 
[[Файл: Факторизация K6.png|thumb|360px|right|<tex>1</tex>-факторизация графа <tex>K_6</tex>]]
Строка 21: Строка 57:
 
== 2-факторизация ==
 
== 2-факторизация ==
  
Если граф <tex>2</tex>-факторизуем, то каждый его фактор должен быть объединением непересекающихся (по вершинам) циклов. Если <tex>2</tex>-фактор связен, то он является гамильтоновым циклом. Поскольку в <tex>2</tex>-факторизуемом графе все вершины должны иметь чётные степени, то полный граф <tex>K_{2n}</tex> не является <tex>2</tex>-факторизуемым. Нечётные полные графы <tex>2</tex>-факторизуемы.  
+
{{Утверждение
 +
|statement =
 +
Если граф <tex>2</tex>-факторизуем, то каждый его фактор должен быть объединением непересекающихся (по вершинам) [[Основные определения теории графов|циклов]].
 +
|proof =
 +
Начнём обход <tex>2</tex>-фактора с какой-то вершины. Пойдём по одному из её рёбер и попадаем в смежную ей вершину. Далее идём по рёбрам, по которым мы ещё не ходили. Мы входим в вершину по одному ребру и выходим по другому, так как степень каждой вершины равна <tex>2</tex>, пока не вернёмся в первую вершину. Это цикл, так как в каждой вершине мы были только один раз. Если есть вершины, которые мы не посетили, то снова начинаем обход с любой из таких вершин. В вершины прежних циклов попасть нельзя, так как мы уже проходили по рёбрам этих вершин. Значит, циклы не пересекаются по вершинам.
 +
}}
 +
 
 +
{{Теорема
 +
|id=regular2factor
 +
|author=J. Petersen, 1981
 +
|about = О наличии <tex>2</tex>-фактора в регулярном графе чётной степени.
 +
|statement = Пусть <tex>G</tex> {{---}} [[Основные определения теории графов#defRegularGraph |регулярный граф]] чётной степени. Тогда в <tex>G</tex> есть <tex>2</tex>-фактор.
 +
|proof =
 +
Пусть <tex>G</tex> {{---}} <tex>2k</tex>-регулярный граф, пусть <tex>G</tex> [[Отношение связности, компоненты связности#connected_graph | связен]].
 +
 
 +
Согласно [[Эйлеровость графов#eulerTheorem | критерию эйлеровости]] граф <tex>G</tex> имеет эйлеров цикл <tex>v_0e_1 \cdots e_lv_l</tex>, где <tex>v_0 = v_l</tex>.
 +
 
 +
Будем строить граф <tex>H</tex> следующим образом: разделим каждую вершину графа <tex>G</tex> <tex>v</tex> на две, назовём их <tex>v^-</tex> и <tex>v^+</tex>. Заменим каждое ребро в эйлеровом обходе <tex>v_iv_{i+1}</tex> на ребро <tex>v_i^-v_{i+1}^+</tex>
 +
 
 +
[[Файл:2-фактор(1).png|300px|thumb|right|Пример регулярного графа чётной степени. В нём есть эйлеров цикл <tex>1</tex>{{---}}<tex>2</tex>{{---}}<tex>3</tex>{{---}}<tex>4</tex>{{---}}<tex>1</tex>]]
 +
 
 +
[[Файл:2-фактор(2).png|300px|thumb|right|Соответствующий ему граф <tex>H</tex>]]
 +
 
 +
 
 +
Получившийся граф является <tex>k</tex>-регулярным, и по [[Рёберная раскраска двудольного графа#lem2 | лемме о существовании совершенного паросочетания в регулярном двудольном графе]] в нём есть совершенное паросочетание, то есть <tex>1</tex>-фактор.
 +
 
 +
Объединим вершины <tex>v^-</tex> и <tex>v^+</tex> обратно в вершину <tex>v</tex>. Так как в графе <tex>H</tex> каждой вершине было инцидентно <tex>1</tex> ребро, то после объединения в графе <tex>G</tex> каждой вершине будет инцидентно <tex>2</tex> ребра.
 +
 
 +
Если <tex>G</tex> несвязен, то аналогичные рассуждения можно провести для каждой его [[Отношение связности, компоненты связности#def2 | компоненты связности]], и, таким образом, найти <tex>2</tex>-фактор в каждой его компоненте связности. Тогда каждой вершине каждой его компоненты связности будет инцидентно <tex>2</tex> ребра, значит, каждой вершине <tex>G</tex> будет инцидентно <tex>2</tex> ребра, значит, в <tex>G</tex> существует <tex>2</tex>-фактор.
 +
}}
 +
 
 +
[[Файл:Факторизация K7 разбиение.png|300px|thumb|right| Пример графа, имеющего <tex>3</tex> различных <tex>2</tex>-фактора, то есть разбиваемого на <tex>3</tex> рёберно непересекающихся [[Гамильтоновы графы#defCycle|гамильтоновых цикла]]]]
 +
 
 +
Заметим, что если <tex>2</tex>-фактор связен, то он является [[Гамильтоновы графы|гамильтоновым циклом]].
 +
 
 
{{Теорема
 
{{Теорема
 
|statement =  
 
|statement =  
Граф <tex>K_{2n+1}</tex> можно представить в виде суммы <tex>n</tex> [[Гамильтоновы графы|гамильтоновых циклов]].
+
Граф <tex>K_{2n+1}</tex> можно представить в виде суммы <tex>n</tex> гамильтоновых циклов.
 
|proof =  
 
|proof =  
[[Файл: Факторизация K7.png|thumb|360px|right|<tex>2</tex>-факторизация графа <tex>K_7</tex>]]
+
[[Файл: Факторизация K7.png|thumb|360px|right|<tex>2</tex>-факторизация графа <tex>K_7</tex>. Рёбра, отмеченные пунктиром, не пересекают другие рёбра при правильной [[Укладка графа на плоскости|укладке графа]].]]Для того чтобы в графе <tex>K_{2n+1}</tex> построить <tex>n</tex> гамильтоновых циклов, непересекающихся по рёбрам, перенумеруем сначала его вершины <tex>v_1, v_2, \dots, v_{2n+1}</tex>. На множестве вершин <tex>v_1, v_2, \dots, v_{2n}</tex> зададим <tex>n</tex> непересекающихся простых цепей <tex>P_i=v_i v_{i-1} v_{i+1} v_{i-2} \dots v_{i+n-1}v_{i-n}</tex> следующим образом: <tex>j</tex>-ой вершине цепи <tex>P_i</tex> является вершина <tex>v_k</tex>, где <tex>k=i+(-1)^{j+1}\dfrac{j}{2}</tex>, все индексы приводятся к числам <tex>1, 2, \dots, 2n </tex> по модулю <tex>2n</tex>. Гамильтонов цикл <tex>Z_i</tex> можно получить, соединив вершину <tex>v_{2n+1}</tex> с концевыми вершинами цепи <tex>P_i</tex>.  
Для того чтобы в графе <tex>K_{2n+1}</tex> построить <tex>n</tex> гамильтоновых циклов, непересекающихся по рёбрам, перенумеруем сначала его вершины <tex>v_1, v_2, \dots, v_{2n+1}</tex>. На множестве вершин <tex>v_1, v_2, \dots, v_{2n}</tex> зададим <tex>n</tex> непересекающихся простых цепей <tex>P_i=v_i v_{i-1} v_{i+1} v_{i-2} \dots v_{i+n-1}v_{i-n}</tex> следующим образом: <tex>j</tex>-ой вершине цепи <tex>P_i</tex> является вершина <tex>v_k</tex>, где <tex>k=i+(-1)^{j+1}[j/2]</tex>, все индексы приводятся к числам <tex>1, 2, \dots, 2n </tex> по модулю <tex>2n</tex>. Гамильтонов цикл <tex>Z_i</tex> можно получить, соединив вершину <tex>v_{2n+1}</tex> с концевыми вершинами цепи <tex>P_i</tex>.  
 
 
}}
 
}}
 +
 +
== Замечания ==
 +
* Факторизация графов используется как один из способов построения покрывающих наборов, используемых при создании тестов для программ с большим количеством параметров.
 +
* <tex>1</tex>-факторизация <tex>k</tex>-регулярного графа является рёберной [[Раскраска графа|<tex>k</tex>-раскраской графа]].
 +
== См. также ==
 +
* [[Гамильтоновы графы]]
 +
* [[Остовные деревья: определения, лемма о безопасном ребре|Остовные деревья]]
 +
* [[Основные определения теории графов]]
  
 
== Источники информации ==
 
== Источники информации ==
 
* Харари Фрэнк '''Теория графов''' Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
 
* Харари Фрэнк '''Теория графов''' Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 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.
 +
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Основные определения теории графов]]

Текущая версия на 19:23, 4 сентября 2022

Определение:
Фактором (англ. factor) графа [math]G[/math] называется остовный подграф графа [math]G[/math], имеющий хотя бы одно ребро.


Определение:
Граф [math]G[/math] — сумма факторов [math]G_i[/math], если графы [math]G_i[/math] не имеют попарно общих рёбер, а [math]G[/math] является их объединением. Такое разложение называется факторизацией (англ. factorization) графа [math]G[/math].


Определение:
[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] в общем случае не является двудольным, для решения этой задачи можно воспользваться Алгоритмом Эдмондса для поиска наибольшего паросочетания работающим за время [math]O(E \cdot V^2)[/math]. Построение графа [math]G^*[/math] можно выполнить за время [math]O(E+V)[/math]. Поэтому итоговая асимптотика — [math]O(E \cdot V^2)[/math]

1-факторизация

Теорема:
Полный граф [math]K_{2n}[/math] [math]1[/math]-факторизуем.
Доказательство:
[math]\triangleright[/math]
[math]1[/math]-факторизация графа [math]K_6[/math]
Нам нужно только указать разбиение множества рёбер [math]E[/math] графа на [math](2n - 1)[/math] [math]1[/math]-фактора. Для этого обозначим вершины графа [math]G[/math] через [math]v_1, v_2, \dots, v_{2n}[/math] и определим множества рёбер [math]X_i = (v_iv_{2n}) \cup (v_{i - j}v_{i + j}; j = 1, 2, \dots, n - 1)[/math], [math]i = 1, 2, \dots, 2n - 1 [/math], где каждый из индексов [math]i - j[/math] и [math]i + j[/math] является одним из чисел [math]1, 2, \dots, 2n - 1[/math]; здесь сумма и разность берутся по модулю [math]2n - 1[/math]. Легко видеть, что набор [math]X_i[/math] даёт необходимое разбиение множества [math]X[/math], а сумма подграфов [math]G_i[/math], порождённых множествами [math]X_i[/math], является [math]1[/math]-факторизацией графа [math]K_{2n}[/math].
[math]\triangleleft[/math]

2-факторизация

Утверждение:
Если граф [math]2[/math]-факторизуем, то каждый его фактор должен быть объединением непересекающихся (по вершинам) циклов.
[math]\triangleright[/math]
Начнём обход [math]2[/math]-фактора с какой-то вершины. Пойдём по одному из её рёбер и попадаем в смежную ей вершину. Далее идём по рёбрам, по которым мы ещё не ходили. Мы входим в вершину по одному ребру и выходим по другому, так как степень каждой вершины равна [math]2[/math], пока не вернёмся в первую вершину. Это цикл, так как в каждой вершине мы были только один раз. Если есть вершины, которые мы не посетили, то снова начинаем обход с любой из таких вершин. В вершины прежних циклов попасть нельзя, так как мы уже проходили по рёбрам этих вершин. Значит, циклы не пересекаются по вершинам.
[math]\triangleleft[/math]
Теорема (J. Petersen, 1981, О наличии [math]2[/math]-фактора в регулярном графе чётной степени.):
Пусть [math]G[/math]регулярный граф чётной степени. Тогда в [math]G[/math] есть [math]2[/math]-фактор.
Доказательство:
[math]\triangleright[/math]

Пусть [math]G[/math][math]2k[/math]-регулярный граф, пусть [math]G[/math] связен.

Согласно критерию эйлеровости граф [math]G[/math] имеет эйлеров цикл [math]v_0e_1 \cdots e_lv_l[/math], где [math]v_0 = v_l[/math].

Будем строить граф [math]H[/math] следующим образом: разделим каждую вершину графа [math]G[/math] [math]v[/math] на две, назовём их [math]v^-[/math] и [math]v^+[/math]. Заменим каждое ребро в эйлеровом обходе [math]v_iv_{i+1}[/math] на ребро [math]v_i^-v_{i+1}^+[/math]

Пример регулярного графа чётной степени. В нём есть эйлеров цикл [math]1[/math][math]2[/math][math]3[/math][math]4[/math][math]1[/math]
Соответствующий ему граф [math]H[/math]


Получившийся граф является [math]k[/math]-регулярным, и по лемме о существовании совершенного паросочетания в регулярном двудольном графе в нём есть совершенное паросочетание, то есть [math]1[/math]-фактор.

Объединим вершины [math]v^-[/math] и [math]v^+[/math] обратно в вершину [math]v[/math]. Так как в графе [math]H[/math] каждой вершине было инцидентно [math]1[/math] ребро, то после объединения в графе [math]G[/math] каждой вершине будет инцидентно [math]2[/math] ребра.

Если [math]G[/math] несвязен, то аналогичные рассуждения можно провести для каждой его компоненты связности, и, таким образом, найти [math]2[/math]-фактор в каждой его компоненте связности. Тогда каждой вершине каждой его компоненты связности будет инцидентно [math]2[/math] ребра, значит, каждой вершине [math]G[/math] будет инцидентно [math]2[/math] ребра, значит, в [math]G[/math] существует [math]2[/math]-фактор.
[math]\triangleleft[/math]
Пример графа, имеющего [math]3[/math] различных [math]2[/math]-фактора, то есть разбиваемого на [math]3[/math] рёберно непересекающихся гамильтоновых цикла

Заметим, что если [math]2[/math]-фактор связен, то он является гамильтоновым циклом.

Теорема:
Граф [math]K_{2n+1}[/math] можно представить в виде суммы [math]n[/math] гамильтоновых циклов.
Доказательство:
[math]\triangleright[/math]
[math]2[/math]-факторизация графа [math]K_7[/math]. Рёбра, отмеченные пунктиром, не пересекают другие рёбра при правильной укладке графа.
Для того чтобы в графе [math]K_{2n+1}[/math] построить [math]n[/math] гамильтоновых циклов, непересекающихся по рёбрам, перенумеруем сначала его вершины [math]v_1, v_2, \dots, v_{2n+1}[/math]. На множестве вершин [math]v_1, v_2, \dots, v_{2n}[/math] зададим [math]n[/math] непересекающихся простых цепей [math]P_i=v_i v_{i-1} v_{i+1} v_{i-2} \dots v_{i+n-1}v_{i-n}[/math] следующим образом: [math]j[/math]-ой вершине цепи [math]P_i[/math] является вершина [math]v_k[/math], где [math]k=i+(-1)^{j+1}\dfrac{j}{2}[/math], все индексы приводятся к числам [math]1, 2, \dots, 2n [/math] по модулю [math]2n[/math]. Гамильтонов цикл [math]Z_i[/math] можно получить, соединив вершину [math]v_{2n+1}[/math] с концевыми вершинами цепи [math]P_i[/math].
[math]\triangleleft[/math]

Замечания

  • Факторизация графов используется как один из способов построения покрывающих наборов, используемых при создании тестов для программ с большим количеством параметров.
  • [math]1[/math]-факторизация [math]k[/math]-регулярного графа является рёберной [math]k[/math]-раскраской графа.

См. также

Источники информации

  • Харари Фрэнк Теория графов Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
  • 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.