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

Не путать с Факторный график.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В Гипотеза 1-факторизации^[3] давний догадка в котором говорится, что k ≈ п достаточно. Точнее говоря, гипотеза такова:

• Если п это странно и k ≥ п, тогда г 1-факторизуема. Если п даже и k ≥ п - 1 тогда г 1-факторизуема.

В чрезмерная догадка следует гипотеза 1-факторизации.

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

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

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

В 1964 г. Антон Коциг предположил, что каждый полный график K_2п где п ≥ 2 имеет идеальную 1-факторизацию. Пока что известно, что следующие графы имеют идеальную 1-факторизацию:^[4]

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

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

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

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

Если связный граф равен 2k-регулярный и с четным числом ребер может также быть k-факторизованный, выбирая каждый из двух факторов как чередующееся подмножество ребер Эйлер тур.^[7] Это применимо только к связным графам; несвязные контрпримеры включают непересекающиеся объединения нечетных циклов или копий K_2k+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 США, п. 125, Дои:10.1007/978-1-4757-2564-3_16, ISBN  978-0-7923-4323-3
5. Брайант, Дэррин; Maenhaut, Barbara M .; Ванлесс, Ян М. (май 2002 г.), "Семейство совершенных факторизаций полных двудольных графов", Журнал комбинаторной теории, А, 98 (2): 328–342, Дои: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.

Рекомендации

• Бонди, Джон Адриан; Мурти, США. (1976), Теория графов с приложениями, Северная Голландия, ISBN  0-444-19451-7, заархивировано из оригинал на 2010-04-13, получено 2019-12-18, Раздел 5.1: «Соответствия».
• Четвинд, А.Г.; Хилтон, А. Дж. У. (1985), "Регулярные графы высокой степени 1-факторизуемы", Труды Лондонского математического общества, 50 (2): 193–206, Дои:10.1112 / плмс / с3-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, Дои:10.1016 / 0166-218X (94) 90101-5.
• Perkovic, L .; Рид, Б. (1997), "Краска ребер регулярных графов высокой степени", Дискретная математика, 165–166: 567–578, Дои:10.1016 / S0012-365X (96) 00202-6.
• Петерсен, Юлиус (1891), «Теория регулятивных графов», Acta Mathematica, 15: 193–220, Дои:10.1007 / BF02392606.
• Уэст, Дуглас Б. "Гипотеза 1-факторизации (1985?)". Открытые задачи - теория графов и комбинаторика. Получено 2010-01-09.
• Вайсштейн, Эрик В. «Фактор графика». MathWorld.
• Вайсштейн, Эрик В. «k-фактор». MathWorld.
• Вайсштейн, Эрик В. "k-Факторизуемый график". MathWorld.

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

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