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

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

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

• Любой регулярный двудольный граф . С помощью теоремы Холла о свадьбах можно показать, что k -правильный двудольный граф содержит совершенное сочетание. Можно тогда удалить совершенное паросочетание и ( k − 1)-регулярный двудольный граф и продолжить тот же процесс рекурсивно.
• Любой полный граф с чётным числом вершин (см. ) .

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

• Любой регулярный граф с нечётным числом вершин.
• Граф Петерсена .

Полные графы

1-факторизация полного графа соответствует разбиению на пары в круговых турнирах . 1-факторизация полных графов является специальным случаем теоремы Бараньяи относительно 1-факторизации полных гиперграфов .

Один из способов построения 1-факторизации полного графа помещает все вершины, кроме одной, на окружности, образуя правильный многоугольник , оставшаяся же вершина помещается в центр окружности. При этом расположении вершин процесс построения 1-фактора заключается в выборе ребра e , соединяющего центральную вершину с одной из вершин на окружности, затем выбираются все рёбра, перпендикулярные ребру e . 1-факторы, построенные таким образом, образуют 1-факторизацию графа.

Число различных 1-факторизаций ${\displaystyle 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-факторизуем:

• Если ${\displaystyle k=2n-1}$ , то G является полным графом ${\displaystyle K_{2n}}$ , а потому 1-факторизуем (см. ).
• Если ${\displaystyle k=2n-2}$ , то G можно получить путём удаления совершенного паросочетания из ${\displaystyle K_{2n}}$ . Снова G является 1-факторизуемым.
• Четвинд и Хилтон показали, что при ${\displaystyle k\geqslant {\tfrac {12n}{7}}}$ граф G 1-факторизуем.

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

• Если n нечётно и ${\displaystyle k\geqslant n}$ , то G 1-факторизуем. Если n чётно и ${\displaystyle k\geqslant n-1}$ , то G 1-факторизуем.

заключает в себе гипотезу об 1-факторизации.

Совершенная 1-факторизация

Совершенная пара 1-факторизаций — это пара 1-факторов, объединение которых даёт гамильтонов цикл .

Совершенная 1-факторизация (P1F) графа — это 1-факторизация, имеющая свойство, что любая пара 1-факторов является совершенной парой. Совершенная 1-факторизация не следует путать с совершенным паросочетанием (которое также называют 1-фактором).

В 1964 году Антон Котциг высказал предположение, что любой полный граф ${\displaystyle K_{2n}}$ , где ${\displaystyle n\geqslant 2}$ , имеет совершенную 1-факторизацию. Известно, что следующие графы имеют совершенные 1-факторизации :

• Бесконечное семейство полных графов ${\displaystyle K_{2p}}$ , где p — нечётное простое (Андерсон и Накамура, независимо),
• Бесконечное семейство полных графов ${\displaystyle K_{p+1}}$ , где p — нечётное простое
• спорадически другие графы, включая ${\displaystyle K_{2n}}$ , где ${\displaystyle 2n\in \{16,28,36,40,50,126,170,244,344,730,1332,1370,1850,2198,3126,6860,12168,16808,29792\}}$ . Есть и более свежие результаты .

Если полный граф ${\displaystyle K_{n+1}}$ имеет совершенную 1-факторизацию, то полный двудольный граф ${\displaystyle K_{n,n}}$ также имеет совершенную 1-факторизацию .

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

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

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

Примечания

Литература

Литература для дальнейшего чтения