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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
1-факторизація графа Дезарга — кожен клас кольорів є 1-фактором.
Граф Петерсена можна розбити на 1-фактор (червоний) та 2-фактор (синій). Однак, граф не є 1-факторизованим.

Фактор графа G — це кістяковий підграф, тобто підграф, що має ті ж вершини, що й граф G. k-Фактор графа — це кістяковий k-регулярний підграф, а k-факторизація розбиває ребра графа на неперетинні k-фактори. Кажуть, що граф G k-факторизований, якщо він дозволяє k-розбиття. Зокрема, множина ребер 1-фактора — це досконале парування, а 1-розклад k-регулярного графа — це реберне розфарбування k кольорами. 2-фактор — це набір циклів, які покривають усі вершини графа.

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

[ред. | ред. код]

Якщо граф 1-факторизований (тобто має 1-факторизацію), він має бути регулярним графом. Проте не всі регулярні графи є 1-факторизованими. k-Регулярний граф є 1-факторизованим, якщо його хроматичний індекс дорівнює k. Приклади таких графів:

Однак є k-регулярні графи, хроматичний індекс яких дорівнює k + 1, і ці графи не 1-факторизовані. Приклади таких графів:

Повні графи

[ред. | ред. код]
1-факторизація K8, у якому будь-який 1-фактор складається з ребра, що з'єднує центр із вершиною семикутника, і всіх ребер, перпендикулярних до цього ребра

1-факторизація повного графа відповідає розбиттю на пари в кругових турнірах. 1-факторизація повних графів є окремим випадком теореми Бараньяї про 1-факторизацію повних гіперграфів.

За одного зі способів побудови 1-факторизації повного графа всі вершини, крім однієї, поміщають на колі, утворюючи правильний многокутник, а вершину, що залишилася, поміщають у центр кола. За такого розташування вершин процес побудови 1-фактора полягає у виборі ребра e, що з'єднує центральну вершину з однією з вершин на колі, потім вибирають усі ребра, перпендикулярні до ребра e. 1-фактори, побудовані в такий спосіб, утворюють 1-факторизацію графа.

Число різних 1-факторизацій дорівнює 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, … (послідовність A000438 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).

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

[ред. | ред. код]

Нехай G — k-регулярний граф з 2 n вершинами. Якщо k досить велике, відомо, що G має бути 1-факторизованим:

  • Якщо , то G — повний граф , а тому 1-факторизований (див. вище).
  • Якщо , то G можна отримати видаленням досконалого парування з . Знову G є 1-факторизованим.
  • Четвінд і Гілтон[3] показали, що при граф G 1-факторизований.

Гіпотеза про 1-факторизацію[4] є давно висунутою гіпотезою, яка стверджує, що значення достатньо велике. Точне формулювання:

  • Якщо n непарне і , то G 1-факторизований. Якщо n парне і , то G 1-факторизований.

Гіпотеза сильного заповнення[en] включавє гіпотезу про 1-факторизацію.

Досконала 1-факторизація

[ред. | ред. код]

Досконала пара 1-факторизацій — це пара 1-факторів, об'єднання яких дає гамільтонів цикл.

Досконала 1-факторизація (P1F) графа — це 1-факторизація, яка має властивість, що будь-яка пара 1-факторів є досконалою парою. Досконалу 1-факторизацію не слід плутати з досконалим паруванням (яке також називають 1-фактором).

1964 року Антон Котціг[en] висловив припущення, що будь-який повний граф , де має досконалу 1-факторизацію. Відомо, що такі графи мають досконалі 1-факторизації[5]:

  • нескінченне сімейство повних графів , де p — непарне просте (Андерсон і Накамура, незалежно);
  • нескінченне сімейство повних графів де p — непарне просте;
  • спорадично інші графи, включно з , де . Свіжіші результати є тут.

Якщо повний граф має досконалу 1-факторизацію, то повний двочастковий граф також має досконалу 1-факторизацію[6].

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

[ред. | ред. код]

Якщо граф 2-факторизований, він має бути 2k-регулярним для деякого цілого k. 1891 року Юліус Петерсен показав, що ця необхідна умова є також достатньою — будь-який 2k-регулярний граф є 2-факторизованим[7].

Якщо зв'язкний граф є 2 k-регулярним і має парне число ребер, він також може бути k-факторизованим вибором двох факторів, які складаються з почергових ребер ейлерового циклу[8]. Це стосується лише зв'язкних графів, незв'язні контрприклади містять незв'язне об'єднання непарних циклів або копій графа K2k+1 .

Примітки

[ред. | ред. код]
  1. Харари, 2003, с. 107, теорема 9.2.
  2. Харари, 2003, с. 85, теорема 9.1.
  3. Chetwynd, Hilton, 1985.
  4. Chetwynd, Hilton, 1985;Niessen, 1994; Perkovic, Reed, 1997; West, 1985
  5. Wallis, 1997, с. 125.
  6. Bryant, Maenhaut, Wanless, 2002, с. 328–342.
  7. Petersen, 1891, § 9, стор. 200; Харари, 2003, стор. 113, теорема 9.9; див. доведення в книзі Дистель, 2002, стор. 49, наслідок 2.1.5
  8. Petersen, 1891, с. 198 §6.

Література

[ред. | ред. код]
  • John Adrian Bondy, U. S. R. Murty. Section 5.1: "Matchings". // Graph Theory with Applications. — North-Holland, 1976. — ISBN 0-444-19451-7. Архівна копія на сайті Wayback Machine.
  • A. G. Chetwynd, A. J. W. Hilton. Regular graphs of high degree are 1-factorizable // Proceedings of the London Mathematical Society. — 1985. — Т. 50, вип. 2. — С. 193—206. — DOI:10.1112/plms/s3-50.2.193..
  • Рейнгард Дистель. Глава 2: Паросочетания // Теория графов. — Новосибирск : Издательство Института Математики, 2002. — ISBN 5-86134-101-X, УДК 519.17, ББК 22.17.
  • Ф. Харари. Глава 9. Факторизация // Теория графов. — М. : Едиториал УРСС, 2003. — ISBN 5-354-00301-6.
  • Thomas Niessen. How to find overfull subgraphs in graphs with large maximum degree // Discrete Applied Mathematics. — 1994. — Т. 51, вип. 1—2. — С. 117—125. — DOI:10.1016/0166-218X(94)90101-5..
  • L. Perkovic, B. Reed. Edge coloring regular graphs of high degree // Discrete Mathematics. — 1997. — Т. 165—166. — С. 567—578. — DOI:10.1016/S0012-365X(96)00202-6..
  • Julius Petersen. Die Theorie der regulären graphs // Acta Mathematica. — 1891. — Т. 15. — С. 193—220. — DOI:10.1007/BF02392606.
  • Douglas B. West. 1-Factorization Conjecture (1985?). Open Problems – Graph Theory and Combinatorics. Процитовано 9 січня 2010.
  • W. D. Wallis. One-factorizations. — Springer US, 1997. — Т. 390, вип. 1. — С. 125. — ISBN 978-0-7923-4323-3. — DOI:10.1007/978-1-4757-2564-3_16.
  • One-factorization / Michiel Hazewinkel. — Springer, 2001. — ISBN 978-1-55608-010-4.
  • Darryn Bryant, Barbara M. Maenhaut, Ian M. Wanless. A Family of Perfect Factorisations of Complete Bipartite Graphs // Journal of Combinatorial Theory. — 2002. — Т. 98, вип. 2. — С. 328—342. — (A). — ISSN 0097-3165. — DOI:10.1006/jcta.2001.3240.
  • Weisstein, Eric W. актор графа(англ.) на сайті Wolfram MathWorld.
  • Weisstein, Eric W. k-Фактор(англ.) на сайті Wolfram MathWorld.
  • Weisstein, Eric W. k-Факторизований граф(англ.) на сайті Wolfram MathWorld.
  • Michael D. Plummer. Graph factors and factorization: 1985–2003: A survey // Discrete Mathematics. — 2007. — Т. 307, вип. 7—8. — С. 791—821. — DOI:10.1016/j.disc.2005.11.059.