Jump to content

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

(Перенаправлено из гипотезы 1-факторизации )
1-факторизация графа Дезарга : каждый цветовой класс является 1-фактором .
График Петерсена можно разделить на однофакторный (красный) и двухфакторный (синий). Однако граф не является 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-факторизация К 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 : 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-факторизации полных графов в изоморфные подграфы. Он спрашивает, для каких подграфов это возможно. Это известно, когда подграф связен (в этом случае он является гамильтоновым циклом и этим частным случаем является задача гамильтонова разложения ), но общий случай остается открытым .

  1. ^ Гарри (1969) , Теорема 9.2, с. 85. Дистель (2005) , следствие 2.1.3, с. 37.
  2. ^ Sick (1969) , Теорема 9.1, с. 85.
  3. ^ Четвинд и Хилтон (1985) . Ниссен (1994) . Перкович и Рид (1997) . Запад .
  4. ^ Уоллис, WD (1997), «16. Совершенные факторизации», Однофакторизация , Математика и ее приложения, том. 390 (1-е изд.), Springer US , с. 125, номер домена : 10.1007/978-1-4757-2564-3_16 , ISBN  978-0-7923-4323-3
  5. ^ Брайант, Дэррин; Менхаут, Барбара М.; Уэнлесс, Ян М. (май 2002 г.), «Семейство совершенных факторизаций полных двудольных графов», Journal of Combinatorial Theory , 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.

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

[ редактировать ]

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

[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 85588b2d7a80ae4b4ff7d9a42e3c60b5__1721193720
URL1:https://arc.ask3.ru/arc/aa/85/b5/85588b2d7a80ae4b4ff7d9a42e3c60b5.html
Заголовок, (Title) документа по адресу, URL1:
Graph factorization - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)