Русская Википедия:Факторизация графа
Фактор графа G — это остовный подграф, то есть подграф, имеющий те же вершины, что и граф G. k-фактор графа — это остовный k-регулярный подграф, а k-факторизация разбивает рёбра графа на непересекающиеся k-факторы. Говорят, что граф G k-факторизуем, если он позволяет k-разбиение. В частности, множество рёбер 1-фактора — это совершенное паросочетание, а 1-разложение k-регулярного графа — это рёберная раскраска k цветами. 2-фактор — это набор циклов, которые покрывают все вершины графа.
1-факторизация
Если граф 1-факторизуем (то есть имеет 1-факторизацию), то он должен быть регулярным графом. Однако не все регулярные графы являются 1-факторизуемыми. k-регулярный граф является 1-факторизуемым, если его хроматический индекс равен k. Примеры таких графов:
- Любой регулярный двудольный графШаблон:SfnШаблон:Sfn. С помощью теоремы Холла о свадьбах можно показать, что k-правильный двудольный граф содержит совершенное сочетание. Можно тогда удалить совершенное паросочетание и (k − 1)-регулярный двудольный граф и продолжить тот же процесс рекурсивно.
- Любой полный граф с чётным числом вершин (см. ниже)Шаблон:Sfn.
Однако имеются k-регулярные графы, хроматический индекс которых равен k + 1, и эти графы не 1-факторизуемы. Примеры таких графов:
- Любой регулярный граф с нечётным числом вершин.
- Граф Петерсена.
Полные графы
1-факторизация полного графа соответствует разбиению на пары в круговых турнирах. 1-факторизация полных графов является специальным случаем теоремы Бараньяи относительно 1-факторизации полных гиперграфов.
Один из способов построения 1-факторизации полного графа помещает все вершины, кроме одной, на окружности, образуя правильный многоугольник, оставшаяся же вершина помещается в центр окружности. При этом расположении вершин процесс построения 1-фактора заключается в выборе ребра e, соединяющего центральную вершину с одной из вершин на окружности, затем выбираются все рёбра, перпендикулярные ребру e. 1-факторы, построенные таким образом, образуют 1-факторизацию графа.
Число различных 1-факторизаций <math>K_2, K_4, K_6, K_8, \dots</math> равно 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, … (Шаблон:OEIS).
Гипотеза об 1-факторизации
Пусть G — k-регулярный граф с 2n вершинами. Если k достаточно велико, известно, что G должен быть 1-факторизуем:
- Если <math>k = 2n - 1</math>, то G является полным графом <math>K_{2n}</math>, а потому 1-факторизуем (см. выше).
- Если <math>k=2n-2</math>, то G можно получить путём удаления совершенного паросочетания из <math>K_{2n}</math>. Снова G является 1-факторизуемым.
- Четвинд и ХилтонШаблон:Sfn показали, что при <math>k \geqslant \tfrac{12n}{7}</math> граф G 1-факторизуем.
Гипотеза об 1-факторизации[1] является давно выдвинутой гипотезой, утверждающей, что значение <math>k\approx n</math> достаточно велико. Точная формулировка:
- Если n нечётно и <math>k \geqslant n</math>, то G 1-факторизуем. Если n чётно и <math>k \geqslant n - 1</math>, то G 1-факторизуем.
Шаблон:Не переведено 5 заключает в себе гипотезу об 1-факторизации.
Совершенная 1-факторизация
Совершенная пара 1-факторизаций — это пара 1-факторов, объединение которых даёт гамильтонов цикл.
Совершенная 1-факторизация (P1F) графа — это 1-факторизация, имеющая свойство, что любая пара 1-факторов является совершенной парой. Совершенная 1-факторизация не следует путать с совершенным паросочетанием (которое также называют 1-фактором).
В 1964 году Антон Котциг высказал предположение, что любой полный граф <math>K_{2n}</math>, где <math>n \geqslant 2</math>, имеет совершенную 1-факторизацию. Известно, что следующие графы имеют совершенные 1-факторизацииШаблон:Sfn:
- Бесконечное семейство полных графов <math>K_{2p}</math>, где p — нечётное простое (Андерсон и Накамура, независимо),
- Бесконечное семейство полных графов <math>K_{p + 1}</math>, где p — нечётное простое
- спорадически другие графы, включая <math>K_{2n}</math>, где <math>2n \in \{16, 28, 36, 40, 50, 126, 170, 244, 344, 730, 1332, 1370, 1850, 2198, 3126, 6860, 12168, 16808, 29792\}</math>. Есть и более свежие результаты здесь.
Если полный граф <math>K_{n + 1}</math> имеет совершенную 1-факторизацию, то полный двудольный граф <math>K_{n,n}</math> также имеет совершенную 1-факторизациюШаблон:Sfn.
2-факторизация
Если граф 2-факторизуем, то он должен быть 2k-регулярным для некоторого целого k. Юлиус Петерсен показал в 1891, что это необходимое условие является также достаточным — любой 2k-регулярный граф является 2-факторизуемым[2].
Если связный граф является 2k-регулярным и имеет чётное число рёбер, он также может быть k-факторизуем путём выбора двух факторов, являющихся чередующимися рёбрами эйлерова циклаШаблон:Sfn. Это относится только к связным графам, несвязные контрпримеры содержат несвязное объединение нечётных циклов или копий графа K2k+1.
Примечания
Литература
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Статья
- Шаблон:Cite web
- Шаблон:Статья
- Шаблон:КнигаШаблон:Недоступная ссылка
- Шаблон:Статья
Литература для дальнейшего чтения
- ↑ Шаблон:Harvnb;Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb
- ↑ Шаблон:Harvnb, § 9, стр. 200; Шаблон:Harvnb, стр. 113, Теорема 9.9; См. доказательство в книге Шаблон:Harvnb, стр. 49, Следствие 2.1.5
