Изменения

{{Определение

}}

== 1-факторизация ==

{{Теорема

|statement=

Полный граф <tex>K_{2n}</tex> <tex>1</tex>-факторизуем.

|proof=

Нам нужно только указать разбиение множества рёбер <tex>E</tex> графа на <tex>(2n - 1)</tex> <tex>1</tex>-фактора. Для этого обозначим вершины графа <tex>G</tex> через <tex>v_1, v_2, \dots, v_{2n}</tex> и определим множества рёбер <tex>X_i = (v_iv_{2n}) \cup (v_{i - j}v_{i + j}; j = 1, 2, \dots, n - 1)</tex>, <tex>i = 1, 2, \dots, 2n - 1 </tex>, где каждый из индексов <tex>i - j</tex> и <tex>i + j</tex> является одним из чисел <tex>1, 2, \dots, 2n - 1</tex>; здесь сумма и разность берутся по модулю <tex>2n - 1</tex>. Легко видеть, что набор <tex>X_i</tex> даёт необходимое разбиение множества <tex>X</tex>, а сумма подграфов <tex>G_i</tex>, порождённых множествами <tex>X_i</tex>, является <tex>1</tex>-факторизацией графа <tex>K_{2n}</tex>.

}}

== 2-факторизация ==

{{Теорема

|statement =

|proof =

Для того чтобы в графе <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}[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>.

}}