Фактор графа G — это остовный подграф, то есть подграф, имеющий те же вершины, что и граф G. k-фактор графа — это остовный k-регулярный подграф, а k-факторизация разбивает рёбра графа на непересекающиеся k-факторы. Говорят, что граф G k-факторизуем, если он позволяет k-разбиение. В частности, множество рёбер 1-фактора — это совершенное паросочетание, а 1-разложение k-регулярного графа — это рёберная раскраска k цветами. 2-фактор — это набор циклов, которые покрывают все вершины графа.
1-факторизация
Если граф 1-факторизуем (то есть имеет 1-факторизацию), то он должен быть регулярным графом. Однако не все регулярные графы являются 1-факторизуемыми. k-регулярный граф является 1-факторизуемым, если его хроматический индекс равен k. Примеры таких графов:
- Любой регулярный двудольный граф[1][2]. С помощью теоремы Холла о свадьбах можно показать, что k-правильный двудольный граф содержит совершенное сочетание. Можно тогда удалить совершенное паросочетание и (k − 1)-регулярный двудольный граф и продолжить тот же процесс рекурсивно.
- Любой полный граф с чётным числом вершин (см. ниже)[3]. Однако имеются k-регулярные графы, хроматический индекс которых равен k + 1, и эти графы не 1-факторизуемы. Примеры таких графов:
- Любой регулярный граф с нечётным числом вершин.
- Граф Петерсена.
Полные графы
1-факторизация полного графа соответствует разбиению на пары в круговых турнирах. 1-факторизация полных графов является специальным случаем теоремы Бараньяи[en] относительно 1-факторизации полных гиперграфов.
Один из способов построения 1-факторизации полного графа помещает все вершины, кроме одной, на окружности, образуя правильный многоугольник, оставшаяся же вершина помещается в центр окружности. При этом расположении вершин процесс построения 1-фактора заключается в выборе ребра e, соединяющего центральную вершину с одной из вершин на окружности, затем выбираются все рёбра, перпендикулярные ребру e. 1-факторы, построенные таким образом, образуют 1-факторизацию графа.
Число различных 1-факторизаций K2, K4, K6, K8, … равно 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, … (последовательность A000438 в OEIS).
Гипотеза об 1-факторизации
Пусть G — k-регулярный граф с 2n вершинами. Если k достаточно велико, известно, что G должен быть 1-факторизуем:
- Если k = 2n − 1, то G является полным графом K2n, а потому 1-факторизуем (см. выше).
- Если k = 2n − 2, то G можно получить путём удаления совершенного паросочетания из K2n. Снова G является 1-факторизуемым.
- Четвинд и Хилтон[4] показали, что при k ≥ 12n/7 граф G 1-факторизуем.
Гипотеза об 1-факторизации[5] является давно выдвинутой гипотезой, утверждающей, что значение k ≈ n достаточно велико. Точная формулировка:
- Если n нечётно и k ≥ n, то G 1-факторизуем. Если n чётно и k ≥ n − 1, то G 1-факторизуем.
Гипотеза сильного заполнения[en] заключает в себе гипотезу об 1-факторизации.
Совершенная 1-факторизация
Совершенная пара 1-факторизаций — это пара 1-факторов, объединение которых даёт гамильтонов цикл.
Совершенная 1-факторизация (P1F) графа — это 1-факторизация, имеющая свойство, что любая пара 1-факторов является совершенной парой. Совершенная 1-факторизация не следует путать с совершенным паросочетанием (которое также называют 1-фактором).
В 1964 году Антон Котциг высказал предположение, что любой полный граф K2n, где n ≥ 2, имеет совершенную 1-факторизацию. Известно, что следующие графы имеют совершенные 1-факторизации[6]:
- Бесконечное семейство полных графов K2p, где p — нечётное простое (Андерсон и Накамура, независимо),
- Бесконечное семейство полных графов Kp + 1, где p — нечётное простое
- спорадически другие графы, включая K2n, где 2n ∈ {16, 28, 36, 40, 50, 126, 170, 244, 344, 730, 1332, 1370, 1850, 2198, 3126, 6860, 12168, 16808, 29792}. Есть и более свежие результаты здесь.
Если полный граф Kn + 1 имеет совершенную 1-факторизацию, то полный двудольный граф Kn,n также имеет совершенную 1-факторизацию[7].
2-факторизация
Если граф 2-факторизуем, то он должен быть 2k-регулярным для некоторого целого k. Юлиус Петерсен показал в 1891, что это необходимое условие является также достаточным — любой 2k-регулярный граф является 2-факторизуемым[8].
Если связный граф является 2k-регулярным и имеет чётное число рёбер, он также может быть k-факторизуем путём выбора двух факторов, являющихся чередующимися рёбрами эйлерова цикла[9]. Это относится только к связным графам, несвязные контрпримеры содержат несвязное объединение нечётных циклов или копий графа K2k+1.
Примечания
- ↑ Харари, 2003, с. 107, Теорема 9.2.
- ↑ Дистель, 2002, с. 48, Следстие 2.1.3.
- ↑ Харари, 2003, с. 85, Теорема 9.1.
- ↑ Chetwynd, Hilton, 1985.
- ↑ Chetwynd, Hilton, 1985;Niessen, 1994; Perkovic, Reed, 1997; West, 1985,
- ↑ Wallis, 1997, с. 125.
- ↑ Bryant, Maenhaut, Wanless, 2002, с. 328–342.
- ↑ Petersen, 1891, § 9, стр. 200; Харари, 2003, стр. 113, Теорема 9.9; См. доказательство в книге Дистель, 2002, стр. 49, Следствие 2.1.5
- ↑ Petersen, 1891, с. 198 §6.
Литература
- John Adrian Bondy, U. S. R. Murty. Section 5.1: "Matchings". // Graph Theory with Applications. — North-Holland, 1976. — ISBN 0-444-19451-7. Архивировано 16 июня 2012 года.
- A. G. Chetwynd, A. J. W. Hilton. Regular graphs of high degree are 1-factorizable // Proceedings of the London Mathematical Society. — 1985. — Т. 50, вып. 2. — С. 193–206. — DOI:10.1112/plms/s3-50.2.193..
- Рейнгард Дистель. Глава 2: Паросочетания // Теория графов. — Новосибирск: Издательство Института Математики, 2002. — ISBN 5-86134-101-X, УДК 519.17, ББК 22.17.
- Ф. Харари. Глава 9 Факторизация // Теория графов. — М.: Едиториал УРСС, 2003. — ISBN 5-354-00301-6.
- Thomas Niessen. How to find overfull subgraphs in graphs with large maximum degree // Discrete Applied Mathematics. — 1994. — Т. 51, вып. 1–2. — С. 117–125. — DOI:10.1016/0166-218X(94)90101-5..
- L. Perkovic, B. Reed. Edge coloring regular graphs of high degree // Discrete Mathematics. — 1997. — Т. 165–166. — С. 567–578. — DOI:10.1016/S0012-365X(96)00202-6..
- Julius Petersen. Die Theorie der regulären graphs // Acta Mathematica. — 1891. — Т. 15. — С. 193–220. — DOI:10.1007/BF02392606.
- Douglas B. West. 1-Factorization Conjecture (1985?). Open Problems – Graph Theory and Combinatorics. Проверено 9 января 2010.
- W. D. Wallis. One-factorizations. — Springer US, 1997. — Т. 390, вып. 1. — С. 125. — ISBN 978-0-7923-4323-3. — DOI:10.1007/978-1-4757-2564-3_16.
- One-factorization / Michiel Hazewinkel. — Springer, 2001. — ISBN 978-1-55608-010-4.
- Darryn Bryant, Barbara M. Maenhaut, Ian M. Wanless. A Family of Perfect Factorisations of Complete Bipartite Graphs // Journal of Combinatorial Theory. — 2002. — Т. 98, вып. 2. — С. 328–342. — ISSN 0097-3165. — DOI:10.1006/jcta.2001.3240.
- Weisstein, Eric W. Graph Factor (англ.) на сайте Wolfram MathWorld.
- Weisstein, Eric W. k-Factor (англ.) на сайте Wolfram MathWorld.
- Weisstein, Eric W. k-Factorable Graph (англ.) на сайте Wolfram MathWorld.
Литература для дальнейшего чтения
- Michael D. Plummer. Graph factors and factorization: 1985–2003: A survey // Discrete Mathematics. — 2007. — Т. 307, вып. 7–8. — С. 791–821. — DOI:10.1016/j.disc.2005.11.059.
 | Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .