137
правок
Изменения
→2-факторизация
Будем строить граф <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|centerright|Пример регулярного графа чётной степени. В нём есть эйлеров цикл <tex>1</tex>{{---}}<tex>2</tex>{{---}}<tex>3</tex>{{---}}<tex>4</tex>{{---}}<tex>1</tex>]]
[[Файл:2-фактор(2).png|300px|thumb|centerright|Соответствующий ему граф <tex>H</tex>]]
