Факторизация графов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 19: Строка 19:
 
Нам нужно только указать разбиение множества рёбер <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>.
 
Нам нужно только указать разбиение множества рёбер <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-факторизация ==
 +
 +
Если граф <tex>2</tex>-факторизуем, то каждый его фактор должен быть объединением непересекающихся (по вершинам) циклов. Если <tex>2</tex>-фактор связен, то он является гамильтоновым циклом. Поскольку в <tex>2</tex>-факторизуемом графе все вершины должны иметь чётные степени, то полный граф <tex>K_{2n}</tex> не является <tex>2</tex>-факторизуемым. Нечётные полные графы <tex>2</tex>-факторизуемы.
 +
{{Теорема
 +
|statement =
 +
Граф <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
 +
[[Категория: Алгоритмы и структуры данных]]

Версия 11:49, 5 декабря 2015

Определение:
Фактором (англ. 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]

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

Если граф [math]2[/math]-факторизуем, то каждый его фактор должен быть объединением непересекающихся (по вершинам) циклов. Если [math]2[/math]-фактор связен, то он является гамильтоновым циклом. Поскольку в [math]2[/math]-факторизуемом графе все вершины должны иметь чётные степени, то полный граф [math]K_{2n}[/math] не является [math]2[/math]-факторизуемым. Нечётные полные графы [math]2[/math]-факторизуемы.

Теорема:
Граф [math]K_{2n+1}[/math] можно представить в виде суммы [math]n[/math] гамильтоновых циклов.
Доказательство:
[math]\triangleright[/math]
Для того чтобы в графе [math]K_{2n+1}[/math] построить [math]n[/math] гамильтоновых циклов, непересекающихся по рёбрам, перенумеруем сначала его вершины [math]v_1, v_2, \dots, v_{2n+1}[/math]. На множестве вершин [math]v_1, v_2, \dots, v_{2n}[/math] зададим [math]n[/math] непересекающихся простых цепей [math]P_i=v_i v_{i-1} v_{i+1} v_{i-2} \dots v_{i+n-1}v_{i-n}[/math] следующим образом: [math]j[/math]-ой вершине цепи [math]P_i[/math] является вершина [math]v_k[/math], где [math]k=i+(-1)^{j+1}[j/2][/math], все индексы приводятся к числам [math]1, 2, \dots, 2n [/math] по модулю [math]2n[/math]. Гамильтонов цикл [math]Z_i[/math] можно получить, соединив вершину [math]v_{2n+1}[/math] с концевыми вершинами цепи [math]P_i[/math].
[math]\triangleleft[/math]

Источники информации

  • Харари Фрэнк Теория графов Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6