Фактор графа G — це кістяковий підграф, тобто підграф, що має ті ж вершини, що й граф G. k-Фактор графа — це кістяковий k-регулярний підграф, а k-факторизація розбиває ребра графа на неперетинні k-фактори. Кажуть, що граф G k-факторизований, якщо він дозволяє k-розбиття. Зокрема, множина ребер 1-фактора — це досконале парування, а 1-розклад k-регулярного графа — це реберне розфарбування k кольорами. 2-фактор — це набір циклів, які покривають усі вершини графа.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOHdMekF6TDBSbGMyRnlaM1ZsYzE5bmNtRndhRjh6WTI5c2IzSmZaV1JuWlM1emRtY3ZNakF3Y0hndFJHVnpZWEpuZFdWelgyZHlZWEJvWHpOamIyeHZjbDlsWkdkbExuTjJaeTV3Ym1jPS5wbmc=.png)
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOWhMMkU1TDFCbGRHVnljMlZ1TFdkeVlYQm9MV1poWTNSdmNuTXVjM1puTHpJd01IQjRMVkJsZEdWeWMyVnVMV2R5WVhCb0xXWmhZM1J2Y25NdWMzWm5MbkJ1Wnc9PS5wbmc=.png)
1-факторизація
Якщо граф 1-факторизований (тобто має 1-факторизацію), він має бути регулярним графом. Проте не всі регулярні графи є 1-факторизованими. k-Регулярний граф є 1-факторизованим, якщо його хроматичний індекс дорівнює k. Приклади таких графів:
- Будь-який регулярний двочастковий граф. За допомогою теореми Холла про весілля можна показати, що k-правильний двочастковий граф містить досконале парування. Можна тоді видалити досконале парування та (k − 1)-регулярний двочастковий граф і продовжити той самий процес рекурсивно.
- Будь-який повний граф із парним числом вершин (див. нижче).
Однак є k-регулярні графи, хроматичний індекс яких дорівнює k + 1, і ці графи не 1-факторизовані. Приклади таких графів:
- Будь-який регулярний граф з непарним числом вершин.
- Граф Петерсена.
Повні графи
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOWlMMkppTDBOdmJYQnNaWFJsTFdWa1oyVXRZMjlzYjNKcGJtY3VjM1puTHpJd01IQjRMVU52YlhCc1pYUmxMV1ZrWjJVdFkyOXNiM0pwYm1jdWMzWm5MbkJ1Wnc9PS5wbmc=.png)
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-факторизованим.
- Четвінд і Гілтон показали, що при
граф G 1-факторизований.
Гіпотеза про 1-факторизацію є давно висунутою гіпотезою, яка стверджує, що значення достатньо велике. Точне формулювання:
- Якщо n непарне і
, то G 1-факторизований. Якщо n парне і
, то G 1-факторизований.
[en] включавє гіпотезу про 1-факторизацію.
Досконала 1-факторизація
Досконала пара 1-факторизацій — це пара 1-факторів, об'єднання яких дає гамільтонів цикл.
Досконала 1-факторизація (P1F) графа — це 1-факторизація, яка має властивість, що будь-яка пара 1-факторів є досконалою парою. Досконалу 1-факторизацію не слід плутати з досконалим паруванням (яке також називають 1-фактором).
1964 року [en] висловив припущення, що будь-який повний граф , де
має досконалу 1-факторизацію. Відомо, що такі графи мають досконалі 1-факторизації:
- нескінченне сімейство повних графів
, де p — непарне просте (Андерсон і Накамура, незалежно);
- нескінченне сімейство повних графів
де p — непарне просте;
- спорадично інші графи, включно з
, де
. Свіжіші результати є тут.
Якщо повний граф має досконалу 1-факторизацію, то повний двочастковий граф
також має досконалу 1-факторизацію.
2-факторизація
Якщо граф 2-факторизований, він має бути 2k-регулярним для деякого цілого k. 1891 року (Юліус Петерсен) показав, що ця необхідна умова є також достатньою — будь-який 2k-регулярний граф є 2-факторизованим.
Якщо зв'язкний граф є 2 k-регулярним і має парне число ребер, він також може бути k-факторизованим вибором двох факторів, які складаються з почергових ребер ейлерового циклу. Це стосується лише зв'язкних графів, незв'язні контрприклади містять незв'язне об'єднання непарних циклів або копій графа K2k+1 .
Примітки
- Харари, 2003, с. 107, теорема 9.2.
- Харари, 2003, с. 85, теорема 9.1.
- Chetwynd, Hilton, 1985.
- Chetwynd, Hilton, 1985;Niessen, 1994; Perkovic, Reed, 1997; West, 1985
- Wallis, 1997, с. 125.
- Bryant, Maenhaut, Wanless, 2002, с. 328–342.
- Petersen, 1891, § 9, стор. 200; Харари, 2003, стор. 113, теорема 9.9; див. доведення в книзі Дистель, 2002, стор. 49, наслідок 2.1.5
- Petersen, 1891, с. 198 §6.
Література
- John Adrian Bondy, U. S. R. Murty. Section 5.1: "Matchings". // . — North-Holland, 1976. — . Архівна копія на сайті 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: ..
- Рейнгард Дистель. Глава 2: Паросочетания // Теория графов. — Новосибирск : Издательство Института Математики, 2002. — , УДК 519.17, ББК 22.17.
- Ф. Харари. Глава 9. Факторизация // Теория графов. — М. : Едиториал УРСС, 2003. — .
- Thomas Niessen. How to find overfull subgraphs in graphs with large maximum degree // Discrete Applied Mathematics. — 1994. — Т. 51, вип. 1—2. — С. 117—125. — DOI: ..
- L. Perkovic, B. Reed. Edge coloring regular graphs of high degree // . — 1997. — Т. 165—166. — С. 567—578. — DOI: ..
- Julius Petersen. Die Theorie der regulären graphs // . — 1891. — Т. 15. — С. 193—220. — DOI: .
- Douglas B. West. 1-Factorization Conjecture (1985?). Open Problems – Graph Theory and Combinatorics. Процитовано 9 січня 2010.
- W. D. Wallis. One-factorizations. — , 1997. — Т. 390, вип. 1. — С. 125. — . — DOI: .
- One-factorization / Michiel Hazewinkel. — Springer, 2001. — .
- 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: .
- 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 // . — 2007. — Т. 307, вип. 7—8. — С. 791—821. — DOI: .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет