Факторизация графа
В теории графов фактором и графа 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-факторизация полного графа соответствует спариванию в круговом турнире . 1-факторизация полных графов является частным случаем теоремы Бараньи об 1-факторизации полных гиперграфов .
Один из методов построения 1-факторизации полного графа с четным числом вершин предполагает размещение всех вершин, кроме одной, в правильном многоугольнике с оставшейся вершиной в центре. При таком расположении вершин один из способов построения 1-фактора графа — выбрать ребро e от центра до единственной вершины многоугольника вместе со всеми возможными ребрами, лежащими на прямых, перпендикулярных e . 1-факторы, которые можно построить таким образом, образуют 1-факторизацию графа.
Число различных 1-факторизаций K 2 , K 4 , K 6 , K 8 , ... равно 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, ... ( OEIS : A0004 38 ).
Гипотеза об 1-факторизации
[ редактировать ]Пусть G — k -регулярный граф с 2n узлами . Если 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}. Некоторые новые результаты собраны здесь .
полный граф Kn + 1 имеет совершенную 1-факторизацию, то полный двудольный граф Kn n , Если также имеет совершенную 1-факторизацию. [5]
2-факторизация
[ редактировать ]Если граф 2-факторизуем, то он должен быть 2k - регулярным для некоторого целого числа k . Юлиус Петерсен показал в 1891 году, что это необходимое условие является также и достаточным: любой 2k - регулярный граф 2-факторизуем . [6]
Если связный граф является 2k - регулярным и имеет четное число ребер, его также можно разложить на k -факторы, выбрав каждый из двух факторов в качестве чередующегося подмножества ребер эйлерова обхода . [7] Это применимо только к связным графам; несвязные контрпримеры включают непересекающиеся объединения нечетных циклов или копий K 2 k +1 .
Проблема Обервольфаха касается существования 2-факторизации полных графов в изоморфные подграфы. Он спрашивает, для каких подграфов это возможно. Это известно, когда подграф связен (в этом случае он является гамильтоновым циклом и этим частным случаем является задача гамильтонова разложения ), но общий случай остается открытым .
Ссылки
[ редактировать ]- ^ Гарри (1969) , Теорема 9.2, с. 85. Дистель (2005) , следствие 2.1.3, с. 37.
- ^ Sick (1969) , Теорема 9.1, с. 85.
- ^ Четвинд и Хилтон (1985) . Ниссен (1994) . Перкович и Рид (1997) . Запад .
- ^ Уоллис, WD (1997), «16. Совершенные факторизации», Однофакторизация , Математика и ее приложения, том. 390 (1-е изд.), Springer US , с. 125, номер домена : 10.1007/978-1-4757-2564-3_16 , ISBN 978-0-7923-4323-3
- ^ Брайант, Дэррин; Менхаут, Барбара М.; Уэнлесс, Ян М. (май 2002 г.), «Семейство совершенных факторизаций полных двудольных графов», Journal of Combinatorial Theory , A, 98 (2): 328–342, doi : 10.1006/jcta.2001.3240 , ISSN 0097-3165
- ^ Петерсен (1891) , §9, с. 200. Харари (1969) , Теорема 9.9, с. 90. См. Дистель (2005) , следствие 2.1.5, с. 39 для доказательства.
- ^ Петерсен (1891) , §6, стр. 198.
Библиография
[ редактировать ]- Бонди, Джон Адриан ; Мурти, USR (1976), Теория графов с приложениями , Северная Голландия, ISBN 0-444-19451-7 , заархивировано из оригинала 13 апреля 2010 г. , получено 18 декабря 2019 г. , Раздел 5.1: «Сопоставления».
- Четвинд, AG ; Хилтон, AJW (1985), «Регулярные графы высокой степени 1-факторизуемы», Proceedings of the London Mathematical Society , 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), «Как найти переполненные подграфы в графах с большой максимальной степенью», Discrete Applied Mathematics , 51 (1–2): 117–125, doi : 10.1016/0166-218X(94)90101-5 .
- Перкович, Л.; Рид, Б. (1997), «Раскраска ребер регулярных графов высокой степени», Discrete Mathematics , 165–166: 567–578, doi : 10.1016/S0012-365X(96)00202-6 .
- Петерсен, Юлиус (1891), «Теория регулярных графов» (PDF) , Acta Mathematica , 15 : 193–220, doi : 10.1007/BF02392606 .
- Уэст, Дуглас Б. «Гипотеза 1-факторизации (1985?)» . Открытые проблемы – Теория графов и комбинаторика . Проверено 9 января 2010 г.
- Вайсштейн, Эрик В. «Граф-фактор» . Математический мир .
- Вайсштейн, Эрик В. «К-Фактор» . Математический мир .
- Вайсштейн, Эрик В. «k-факторный граф» . Математический мир .
Дальнейшее чтение
[ редактировать ]- Пламмер, Майкл Д. (2007), «Факторы графа и факторизация: 1985–2003: обзор», Discrete Mathematics , 307 (7–8): 791–821, doi : 10.1016/j.disc.2005.11.059 .