Факторизация графов

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

Фактором (англ. factor) графа [math]G[/math] называется остовный подграф графа [math]G[/math], не являющийся вполне несвязным.

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

Граф [math]G[/math] — сумма факторов [math]G_i[/math], если графы [math]G_i[/math] не имеют попарно общих рёбер, а [math]G[/math] является их объединением. Такое разложение называется факторизацией (англ. factorization) графа [math]G[/math].

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

[math]n[/math]-фактор — регулярный остовный подграф степени [math]n[/math]. Если граф [math]G[/math] представляет собой сумму [math]n[/math]-факторов, то их объединение называется [math]n[/math]-факторизацией, а сам граф [math]G[/math] назыается [math]n[/math]-факторизуемым.

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

Теорема:

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

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]