137
правок
Изменения
→2-факторизация
Пусть <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>
Объединим вершины <tex>v^-</tex> и <tex>v^+</tex> обратно в вершину <tex>v</tex>. Так как в графе <tex>H</tex> каждой вершине было инцидентно <tex>1</tex> ребро, то после объединения в графе <tex>G</tex> каждой вершине будет инцидентно <tex>2</tex> ребра.
Если <tex>G</tex> несвязен, то аналогичные рассуждения можно провести для каждой его [[Отношение связности, компоненты связности#def | компоненты связности]], и, таким образом, найти <tex>2</tex>-фактор в каждой его компоненте связности. Тогда каждой вершине каждой его компоненты связности будет инцидентно <tex>2</tex> ребра, значит, каждой вершине <tex>G</tex> будет инцидентно <tex>2</tex> ребра, значит, в <tex>G</tex> существует <tex>2</tex>-фактор.
}}
