137
правок
Изменения
→2-факторизация
}}
== 2-факторизация ==
{{Утверждение
|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 | связен]].
Будем строить граф <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>
}}
[[Файл:Факторизация K7 разбиение.png|300px|thumb|left| Пример графа, имеющего <tex>3</tex> различных <tex>2</tex>-фактора, то есть разбиваемого на <tex>3</tex> рёберно непересекающихся [[Гамильтоновы графы#defCycle|гамильтоновых цикла]]]]
Заметим, что если <tex>2</tex>-фактор связен, то он является [[Гамильтоновы графы|гамильтоновым циклом]].
