Введение
В теории графов фактор графа G — это остовный подграф, то есть подграф, имеющий то же множество вершин, что и G. K-фактор графа — это остовный K-регулярный подграф, а K-факторизация разбивает рёбра графа на непересекающиеся K-факторы. Граф G называется K-факторизуемым, если он допускает K-факторизацию. В частности, 1-фактор — это совершенное паросочетание, а 1-факторизация K-регулярного графа — это правильная раскраска рёбер K цветами. 2-фактор — это набор циклов, которые покрывают все вершины графа.
Полные графики
Факторизация полного графа на 1 соответствует спариваниям в турнире по круговой системе. Факторизация полных графов на 1 является частным случаем теоремы Бараньяи, касающейся факторизации полных гиперграфов на 1. Один из способов построения 1-факторизации полного графа на четном числе вершин заключается в размещении всех вершин, кроме одной, в правильном многоугольнике, а оставшуюся вершину – в центре. При таком расположении вершин один из способов построения 1-фактора графа – выбрать ребро e, соединяющее центр с одной из вершин многоугольника, вместе со всеми возможными ребрами, лежащими на прямых, перпендикулярных e. 1-факторы, которые могут быть построены таким образом, образуют 1-факторизацию графа. Количество различных 1-факторизаций для K2, K4, K6, K8 равно 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040.
1-факторизационная гипотеза
Пусть G – k-регулярный граф с 2n вершинами. Если k достаточно велико, то известно, что G должен быть 1-факторизуемым: Если k = 2n – 1, то G – это полный граф K2n и, следовательно, 1-факторизуем (см. выше). Если k = 2n – 2, то G можно построить, удалив совершенное паросочетание из K2n. Снова, G является 1-факторизуемым. Докажите, что если k ≥ 12n/7, то G является 1-факторизуемым. Гипотеза о 1-факторизации – это давняя гипотеза, утверждающая, что k ≈ n достаточно. В точных терминах, гипотеза формулируется так: Если n нечетно и k ≥ n, то G является 1-факторизуемым. Если n четно и k ≥ n – 1, то G является 1-факторизуемым. Гипотеза о переполненности влечет за собой гипотезу о 1-факторизации.
If k = 2n − 1, then G is the complete graph K2n, and hence 1 factorable (see above). If k = 2n − 2, then G can be constructed by removing a perfect matching from K2n. Again, G is 1 factorable. show that if k ≥ 12n/7, then G is 1 factorable. The 1 factorization conjecture is a long standing conjecture that states that k ≈ n is sufficient. In precise terms, the conjecture is:
If n is odd and k ≥ n, then G is 1 factorable. If n is even and k ≥ n − 1 then G is 1 factorable. The overfull conjecture implies the 1 factorization conjecture.
Двухфакторная выборка
Если граф 2-разложим, то он должен быть 2k-регулярным для некоторого целого k. Джулиус Петерсен в 1891 году показал, что это необходимое условие также достаточно: любой 2k-регулярный граф 2-разложим. Если связный граф 2k-регулярен и имеет четное число ребер, то он также может быть k-факторизован, выбирая каждый из двух факторов как чередующееся подмножество ребер эйлерова обхода. Это применимо только к связным графам; примерами контрпримеров для несвязных графов являются непересекающиеся объединения нечетных циклов или копий K2k+1. Проблема Обервольфаха касается существования 2-факторизаций полных графов на изоморфные подграфы. Она спрашивает, для каких подграфов это возможно. Это известно, когда подграф связен (в этом случае это гамильтонов цикл, и этот частный случай является задачей гамильтонова разложения), но общий случай остается нерешенным.