Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Не путать с факторным графиком .
1-факторизация графа Дезарга : каждый цветовой класс является 1-фактором.
Граф Петерсена можно разделить на 1-факторный (красный) и 2-факторный (синий). Однако этот граф не факторизуем по одному.

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

1-факторизация [ править ]

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

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

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

Полные графики [ править ]

1-факторизация K 8, в которой каждый 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 :  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-факторизуема.
  • Chetwynd & Hilton (1985) показывают, что если k  ≥ 12n / 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 к -регулярному графу 2-факторизуем. [6]

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

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

Заметки [ править ]

  1. ^ Харари (1969) , теорема 9.2, стр. 85. Diestel (2005) , Corollary 2.1.3, p. 37.
  2. ^ Харари (1969) , теорема 9.1, стр. 85.
  3. Перейти ↑ Chetwynd & Hilton (1985) . Ниссен (1994) . Перкович и Рид (1997) . Запад .
  4. ^ Уоллис, WD (1997), "16. Совершенные факторизации", Однофакторизации , математика и ее приложения, 390 (1 изд.), Springer US , p. 125, DOI : 10.1007 / 978-1-4757-2564-3_16 , ISBN 978-0-7923-4323-3
  5. ^ Брайант, Даррин; Maenhaut, Barbara M .; Wanless, Ian M. (май 2002), "Семейство Идеальных факторизаций полных двудольных графов", Журнал комбинаторной теории , A, 98 (2): 328-342, DOI : 10,1006 / jcta.2001.3240 , ISSN 0097-3165 
  6. ^ Петерсен (1891) , §9, стр. 200. Harary (1969) , теорема 9.9, с. 90. См. Diestel (2005) , Corollary 2.1.5, p. 39 для доказательства.
  7. ^ Петерсен (1891) , §6, стр. 198.

Ссылки [ править ]

  • Бонди, Джон Адриан ; Мурти, USR (1976), Теория графов с приложениями , Северная Голландия, ISBN 0-444-19451-7, заархивировано из оригинала 13 апреля 2010 г. , получено 18 декабря 2019 г., Раздел 5.1: «Соответствия».
  • Chetwynd, AG ; Hilton, AJW (1985), "Обычные графики высокой степени являются 1-факторизуемая", Труды Лондонского математического общества , 50 (2): 193-206, DOI : 10.1112 / ПНИЛ / s3-50.2.193.
  • Дистель, Рейнхард (2005), Теория графов (3-е изд.), Springer , ISBN 3-540-26182-6, Глава 2: «Комплектация, покрытие и упаковка». Электронное издание .
  • Харари, Франк (1969), теория графов , Addison-Wesley, ISBN 0-201-02787-9, Глава 9: «Факторизация».
  • "Однофакторизация" , Энциклопедия математики , EMS Press , 2001 [1994]
  • Нейссно, Томас (1994), "Как найти Overfull подграфов в графах с большой максимальной степенью", дискретная Прикладная математика , 51 (1-2): 117-125, DOI : 10.1016 / 0166-218X (94) 90101-5.
  • Perkovic, L .; Рид, Б. (1997), "Край окраски регулярные графы высокой степени", дискретная математика , 165-166: 567-578, DOI : 10.1016 / S0012-365X (96) 00202-6.
  • Петерсен, Джулиус (1891), "Die Théorie дер regulären графов", Acta Mathematica , 15 : 193-220, DOI : 10.1007 / BF02392606.
  • Уэст, Дуглас Б. "Гипотеза 1-факторизации (1985?)" . Открытые задачи - теория графов и комбинаторика . Проверено 9 января 2010 .
  • Вайсштейн, Эрик В. «Графический фактор» . MathWorld .
  • Вайсштейн, Эрик В. «k-фактор» . MathWorld .
  • Вайсштейн, Эрик В. «k-Факторизуемый граф» . MathWorld .

Дальнейшее чтение [ править ]

  • Пламмер, Майкл Д. (2007), "Graph факторы и факторизация: 1985-2003: Исследование А", Дискретная математика , 307 (7-8): 791-821, DOI : 10.1016 / j.disc.2005.11.059.