Нам потрібно тільки вказати розбиття множини ребер графа на -Фактори. Для цього позначимо вершини графа через та визначимо безлічі ребер,, де кожен з індексів і є одним з чисел; тут сума і різниця беруться по модулю. Легко бачити, що набір дає необхідне розбиття множини, а сума подграфов, породжених множинами, є -факторізаціей графа.
[Ред] 2-факторизація
Якщо граф -факторізуем, то кожен його фактор повинен бути об'єднанням непересічних (по вершинах) циклів.
Почнемо обхід -Фактори з якоюсь вершини. Підемо по одному з її ребер і потрапляємо в суміжну їй вершину. Далі йдемо по ребрах, по яким ми ще не ходили. Ми входимо в вершину по одному ребру і виходимо по іншому, так як ступінь кожної вершини дорівнює, поки не повернемося в першу вершину. Це цикл, так як в кожній вершині ми були тільки один раз. Якщо є вершини, які ми не відвідали, то знову починаємо обхід з будь-якої з таких вершин. У вершини колишніх циклів потрапити не можна, так як ми вже проходили по ребрах цих вершин. Значить, цикли не перетинаються по вершинам.
Зауважимо, що якщо -фактор зв'язний, то він є гамільтоновим циклом.
Граф можна представити у вигляді суми гамільтонових циклів.
-факторизация графа. Ребра, відмічені пунктиром, не перетинають інші ребра при правильному укладанні графа.
Для того щоб в графі побудувати гамільтонових циклів, непересічних по ребрах, перенумеруем спочатку його вершини. На безлічі вершин задамо непересічних простих ланцюгів наступним чином: -ої вершини ланцюга є вершина, де, всі індекси наводяться до чисел по модулю. Гамильтонов цикл можна отримати, поєднавши вершину з кінцевими вершинами ланцюга.
[Ред] Зауваження
- Факторизация графів використовується як один із способів побудови покривають наборів, які використовуються при створенні тестів для програм з великою кількістю параметрів.
- -факторизация -Регулярно графа є реберної -розмальовка графа.