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

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-факторизация K8 в котором каждый 1-фактор состоит из ребра от центра до вершины семиугольник вместе со всеми возможными перпендикулярными краями

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

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

Количество различных 1-факторизаций K2, K4, K6, K8, ... равно 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, ... OEIS: A000438.

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

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

  • Если k = 2п - 1, то г полный граф K2п, а значит, 1-факторизуемость (см. над).
  • Если k = 2п - 2, то г можно построить, удалив идеальное соответствие из K2п. Опять таки, г 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 г. Антон Коциг предположил, что каждый полный график K2п где п ≥ 2 имеет идеальную 1-факторизацию. Пока что известно, что следующие графы имеют идеальную 1-факторизацию:[4]

  • бесконечное семейство полных графов K2п где п - нечетное простое число (независимо от Андерсона и Накамуры),
  • бесконечное семейство полных графов Kп + 1 где п нечетное простое число,
  • и отдельные дополнительные результаты, в том числе K2п где 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] Это применимо только к связным графам; несвязные контрпримеры включают непересекающиеся объединения нечетных циклов или копий K2k+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.

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

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