146
правок
Изменения
Новая страница: «{{Определение |definition ='''Фактором ''' ''(англ. factor)'' графа <tex>G</tex> называется остовный подграф ...»
{{Определение
|definition ='''Фактором ''' ''(англ. factor)'' графа <tex>G</tex> называется остовный подграф графа <tex>G</tex>, не являющийся вполне несвязным.
}}
{{Определение
|definition = Граф <tex>G</tex> — сумма факторов <tex>G_i</tex>, если графы <tex>G_i</tex> не имеют попарно общих рёбер, а <tex>G</tex> является их объединением. Такое разложение называется '''факторизацией ''' ''(англ. factorization)'' графа <tex>G</tex>.
}}
{{Определение
|definition = '''<tex>n</tex>-фактор''' — регулярный остовный подграф степени <tex>n</tex>. Если граф <tex>G</tex> представляет собой сумму <tex>n</tex>-факторов, то их объединение называется <tex>n</tex>-факторизацией, а сам граф <tex>G</tex> назыается <tex>n</tex>-факторизуемым.
}}
== <tex>1</tex>-факторизация ==
{{Теорема
|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>.
}}
|definition ='''Фактором ''' ''(англ. factor)'' графа <tex>G</tex> называется остовный подграф графа <tex>G</tex>, не являющийся вполне несвязным.
}}
{{Определение
|definition = Граф <tex>G</tex> — сумма факторов <tex>G_i</tex>, если графы <tex>G_i</tex> не имеют попарно общих рёбер, а <tex>G</tex> является их объединением. Такое разложение называется '''факторизацией ''' ''(англ. factorization)'' графа <tex>G</tex>.
}}
{{Определение
|definition = '''<tex>n</tex>-фактор''' — регулярный остовный подграф степени <tex>n</tex>. Если граф <tex>G</tex> представляет собой сумму <tex>n</tex>-факторов, то их объединение называется <tex>n</tex>-факторизацией, а сам граф <tex>G</tex> назыается <tex>n</tex>-факторизуемым.
}}
== <tex>1</tex>-факторизация ==
{{Теорема
|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>.
}}
