Изменения

|definition = '''<tex>nk</tex>-фактор''' — [[Основные определения теории графов|регулярный]] остовный подграф степени <tex>nk</tex>. Если граф <tex>G</tex> представляет собой сумму <tex>nk</tex>-факторов, то их объединение называется <tex>nk</tex>-факторизацией, а сам граф <tex>G</tex> назыается <tex>nk</tex>-факторизуемым.

 {{Утверждение|statement =Если граф <tex>2</tex>-факторизуем, то каждый его фактор должен быть объединением непересекающихся (по вершинам) [[Файл: Факторизация K7Основные определения теории графов|циклов]].png|thumbproof =Начнём обход <tex>2</tex>-фактора с какой-то вершины. Пойдём по одному из её рёбер и попадаем в смежную ей вершину. Далее идём по рёбрам, по которым мы ещё не ходили. Мы входим в вершину по одному ребру и выходим по другому, так как степень каждой вершины равна <tex>2</tex>, пока не вернёмся в первую вершину. Это цикл, так как в каждой вершине мы были только один раз. Если есть вершины, которые мы не посетили, то снова начинаем обход с любой из таких вершин. В вершины прежних циклов попасть нельзя, так как мы уже проходили по рёбрам этих вершин. Значит, циклы не пересекаются по вершинам.}} {{Теорема|360pxid=regular2factor|rightauthor=J. Petersen, 1981|about = О наличии <tex>2</tex>-факторизация графа фактора в регулярном графе чётной степени.|statement = Пусть <tex>G</tex> {{---}} [[Основные определения теории графов#defRegularGraph |регулярный граф]] чётной степени. Тогда в <tex>G</tex> есть <tex>K_72</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>2k</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>2G</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>K_{2n}3</tex> не является различных <tex>2</tex>-факторизуемым. Нечётные полные фактора, то есть разбиваемого на <tex>3</tex> рёберно непересекающихся [[Гамильтоновы графы #defCycle|гамильтоновых цикла]]]] Заметим, что если <tex>2</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>.