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

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. Приклади таких графів:

• Будь-який регулярний двочастковий графШаблон:Sfn. За допомогою теореми Холла про весілля можна показати, що k-правильний двочастковий граф містить досконале парування. Можна тоді видалити досконале парування та (k − 1)-регулярний двочастковий граф і продовжити той самий процес рекурсивно.
• Будь-який повний граф із парним числом вершин (див. нижче)Шаблон:Sfn.

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

• Будь-який регулярний граф з непарним числом вершин.
• Граф Петерсена.

Повні графи

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

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

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

Число різних 1-факторизацій $K_2,K_4,K_6,K_8,\dots$ дорівнює 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, … (Шаблон:OEIS).

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

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

• Якщо $k=2n-1$, то G — повний граф $K_{2n}$, а тому 1-факторизований (див. вище).
• Якщо $k=2n-2$, то G можна отримати видаленням досконалого парування з $K_{2n}$. Знову G є 1-факторизованим.
• Четвінд і ГілтонШаблон:Sfn показали, що при $k⩾\frac{12n}{7}$ граф G 1-факторизований.

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

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

Шаблон:Не перекладено включавє гіпотезу про 1-факторизацію.

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

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

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

1964 року Шаблон:Нп висловив припущення, що будь-який повний граф $K_{2n}$, де $n⩾2$ має досконалу 1-факторизацію. Відомо, що такі графи мають досконалі 1-факторизаціїШаблон:Sfn:

• нескінченне сімейство повних графів $K_{2p}$, де p — непарне просте (Андерсон і Накамура, незалежно);
• нескінченне сімейство повних графів $K_{p+1}$ де p — непарне просте;
• спорадично інші графи, включно з $K_{2n}$, де $2n\in \{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-факторизаціюШаблон:Sfn.

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

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

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

Література

• Шаблон:Книга Шаблон:Wayback
• Шаблон:Стаття.
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття.
• Шаблон:Стаття.
• Шаблон:Стаття
• Шаблон:Cite web
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:MathWorld
• Шаблон:MathWorld
• Шаблон:MathWorld
• Шаблон:Стаття