Факторизация графа

1-факторизация графа Дезарга : каждый цветовой класс является 1-фактором .

Граф Петерсена можно разбить на 1-факторный (красный) и 2-факторный (синий). Однако граф не является 1-факторизуемым .

В теории графов фактор графа G — это остовной подграф , т. е . подграф, имеющий тот же набор вершин, что и G. K-фактор графа — это остовной k - регулярный подграф , а k -факторизация разбивает ребра графа на непересекающиеся k -факторы. Граф G называется k -факторизуемым , если он допускает k -факторизацию. В частности, 1-фактор — это совершенное паросочетание , а 1-факторизация k -регулярного графа — это правильная раскраска ребер в k цветов. 2-фактор — это набор циклов , который охватывает все вершины графа.

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

Если граф 1-факторизуем, то он должен быть регулярным графом . Однако не все регулярные графы 1-факторизуемы. K -регулярный граф 1-факторизуем, если он имеет хроматический индекс k ; примеры таких графов включают:

• Любой регулярный двудольный граф . ^[1] Теорема Холла о браке может быть использована для того, чтобы показать, что k -регулярный двудольный граф содержит идеальное паросочетание. Затем можно удалить идеальное паросочетание, чтобы получить ( k  − 1)-регулярный двудольный граф, и применять те же рассуждения повторно.
• Любой полный граф с четным числом узлов (см. ниже). ^[2]

Однако существуют также k -регулярные графы, имеющие хроматический индекс k  + 1, и эти графы не являются 1-факторизуемыми; примеры таких графов включают:

• Любой регулярный граф с нечетным числом узлов.
• Граф Петерсена .

Полные графики

1-факторизация K ₈ , в которой каждый 1-фактор состоит из ребра от центра до вершины семиугольника вместе со всеми возможными перпендикулярными ребрами

1-факторизация полного графа соответствует парам в круговом турнире . 1-факторизация полных графов является частным случаем теоремы Бараньяи об 1-факторизации полных гиперграфов .

Один из методов построения 1-факторизации полного графа на четном числе вершин заключается в размещении всех вершин, кроме одной, в правильном многоугольнике с оставшейся вершиной в центре. При таком расположении вершин один из способов построения 1-фактора графа состоит в выборе ребра e из центра к одной вершине многоугольника вместе со всеми возможными ребрами, которые лежат на линиях, перпендикулярных e . 1-факторы, которые можно построить таким образом, образуют 1-факторизацию графа.

Число различных 1-факторизаций K ₂ , K ₄ , K ₆ , K ₈ , ... равно 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, ... ( OEIS : A000438 ).

гипотеза 1-факторизации

Пусть G — k -регулярный граф с 2 n узлами. Если k достаточно велико, то известно, что G должен быть 1-факторизуемым:

• Если k  = 2 n  − 1, то G является полным графом K _{2 n} и, следовательно, 1-факторизуем (см. выше).
• Если k  = 2 n  − 2, то G можно построить, удалив совершенное паросочетание из K _{2 n} . Опять же, G является 1-факторизуемым.
• Четвинд и Хилтон (1985) показывают, что если k  ≥ 12 n /7, то G является 1-факторизуемым.

Гипотеза 1-факторизации ^[3] — давняя гипотеза , утверждающая, что k  ≈  n достаточно. В точных терминах гипотеза такова:

• Если n нечетно и k  ≥  n , то G является 1-факторизуемым. Если n четно и k  ≥  n  − 1, то G является 1-факторизуемым.

Из гипотезы о переполнении следует гипотеза об 1-факторизации.

Идеальная 1-факторизация

Совершенная пара из 1-факторизации — это пара 1-факторов, объединение которых индуцирует гамильтонов цикл .

Идеальная 1-факторизация (P1F) графа — это 1-факторизация, имеющая свойство, что каждая пара 1-факторов является идеальной парой. Идеальную 1-факторизацию не следует путать с идеальным соответствием (также называемым 1-фактором).

В 1964 году Антон Коциг предположил, что любой полный граф K _{2 n} , где n ≥ 2, имеет совершенную 1-факторизацию. На данный момент известно, что следующие графы имеют совершенную 1-факторизацию: ^[4]

• бесконечное семейство полных графов K _{2 p ,} где p — нечетное простое число (независимо от Андерсона и Накамуры),
• бесконечное семейство полных графов K _{p +1} , где p — нечетное простое число,
• и спорадические дополнительные результаты, включая K _{2 n} , где 2 n ∈ {16, 28, 36, 40, 50, 126, 170, 244, 344, 730, 1332, 1370, 1850, 2198, 3126, 6860, 12168, 16808, 29792}. Некоторые новые результаты собраны здесь.

Если полный граф K _{n +1} имеет совершенную 1-факторизацию, то полный двудольный граф K _{n , n} также имеет совершенную 1-факторизацию. ^[5]

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

Если граф 2-факторизуем, то он должен быть 2 k -регулярным для некоторого целого числа k . Юлиус Петерсен показал в 1891 году, что это необходимое условие является также и достаточным: любой 2 k -регулярный граф 2-факторизуем . ^[6]

Если связный граф является 2 k -регулярным и имеет четное число ребер, его также можно разложить на k -факторы, выбрав каждый из двух множителей в качестве чередующегося подмножества ребер эйлерова цикла . ^[7] Это применимо только к связным графам; несвязные контрпримеры включают в себя непересекающиеся объединения нечетных циклов или копий K _{2 k  +1} .

Проблема Обервольфаха касается существования 2-факторизаций полных графов в изоморфные подграфы. Она спрашивает, для каких подграфов это возможно. Это известно, когда подграф связный (в этом случае он является гамильтоновым циклом , и этот частный случай является проблемой гамильтоновой декомпозиции ), но общий случай остается открытым .

Ссылки

1. Харари (1969), Теорема 9.2, с. 85. Дистель (2005), следствие 2.1.3, с. 37.
2. Харари (1969), Теорема 9.1, с. 85.
3. Четвинд и Хилтон (1985). Ниссен (1994). Перкович и Рид (1997). Запад.
4. Уоллис, У. Д. (1997), "16. Совершенные факторизации", Однофакторизации , Математика и ее приложения, т. 390 (1-е изд.), Springer US , стр. 125, doi :10.1007/978-1-4757-2564-3_16, ISBN 978-0-7923-4323-3
5. Брайант, Даррин; Мэнхаут, Барбара М.; Уонлесс, Ян М. (май 2002 г.), «Семейство совершенных факторизаций полных двудольных графов», Журнал комбинаторной теории , A, 98 (2): 328–342, doi : 10.1006/jcta.2001.3240 , ISSN  0097-3165
6. Петерсен (1891), §9, с. 200. Харари (1969), теорема 9.9, с. 90. См. Дистель (2005), следствие 2.1.5, с. 39 для доказательства.
7. Петерсен (1891), §6, с. 198.

Библиография

• Бонди, Джон Адриан ; Мёрти, USR (1976), Теория графов с приложениями, Северная Голландия, ISBN 0-444-19451-7, заархивировано из оригинала 2010-04-13 , извлечено 2019-12-18, Раздел 5.1: «Сопоставления».
• Четвинд, А.Г.; Хилтон, А.Дж.У. (1985), «Регулярные графы высокой степени являются 1-факторизуемыми», Труды Лондонского математического общества , 50 (2): 193–206, doi :10.1112/plms/s3-50.2.193.
• Дистель, Рейнхард (2005), Теория графов (3-е изд.), Springer , ISBN 3-540-26182-6, Глава 2: «Подбор, покрытие и упаковка». Электронное издание.
• Харари, Фрэнк (1969), Теория графов , Эддисон-Уэсли, ISBN 0-201-02787-9, Глава 9: «Факторизация».
• «Однофакторизация», Энциклопедия математики , EMS Press , 2001 [1994]
• Ниссен, Томас (1994), «Как найти переполненные подграфы в графах с большой максимальной степенью», Дискретная прикладная математика , 51 (1–2): 117–125, doi :10.1016/0166-218X(94)90101-5.
• Перкович, Л.; Рид, Б. (1997), «Раскраска рёбер регулярных графов высокой степени», Дискретная математика , 165–166: 567–578, doi :10.1016/S0012-365X(96)00202-6.
• Петерсен, Юлиус (1891), «Теория регулярных графов» (PDF) , Acta Mathematica , 15 : 193–220, doi : 10.1007/BF02392606.
• West, Douglas B. "1-Factorization Conjecture (1985?)". Открытые проблемы – Теория графов и комбинаторика . Получено 2010-01-09 .
• Вайсштейн, Эрик В. «Фактор графа». MathWorld .
• Вайсштейн, Эрик В. "k-фактор". MathWorld .
• Вайсштейн, Эрик В. "k-факторизуемый граф". MathWorld .

Дальнейшее чтение

• Пламмер, Майкл Д. (2007), «Факторы графа и факторизация: 1985–2003: обзор», Дискретная математика , 307 (7–8): 791–821, doi :10.1016/j.disc.2005.11.059.