146
правок
Изменения
Нет описания правки
{{Определение
|definition ='''Фактором ''' ''(англ. factor)'' [[Основные определения теории графов|графа]] <tex>G</tex> называется [[Остовные деревья: определения, лемма о безопасном ребре|остовный подграф ]] графа <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>-факторизуемым.
}}
{{Теорема
|statement=
[[Основные определения теории графов|Полный ]] граф <tex>K_{2n}</tex> <tex>1</tex>-факторизуем.
|proof=
[[Файл: Факторизация K6.png|thumb|360px|right|<tex>1</tex>-факторизация графа <tex>K_6</tex>]]
}}
== 2-факторизация ==
[[Файл: Факторизация K7.png|thumb|360px|right|<tex>2</tex>-факторизация графа <tex>K_7</tex>. Рёбра, отмеченные пунктиром, не пересекают другие рёбра при правильной [[Укладка графа на плоскости|укладке графа]].]]
Если граф <tex>2</tex>-факторизуем, то каждый его фактор должен быть объединением непересекающихся (по вершинам) циклов. Если <tex>2</tex>-фактор связен, то он является [[Гамильтоновы графы|гамильтоновым циклом]]. Поскольку в <tex>2</tex>-факторизуемом графе все вершины должны иметь чётные степени, то полный граф <tex>K_{2n}</tex> не является <tex>2</tex>-факторизуемым. Нечётные полные графы <tex>2</tex>-факторизуемы.
{{Теорема
Граф <tex>K_{2n+1}</tex> можно представить в виде суммы <tex>n</tex> гамильтоновых циклов.
|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>.
}}
== См. также ==
* [[Гамильтоновы графы]]
* [[Остовные деревья: определения, лемма о безопасном ребре|Остовные деревья]]
* [[Основные определения теории графов]]
== Источники информации ==
* Харари Фрэнк '''Теория графов''' Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]
