Кіріспе
Графтар теориясында, G графигінің факторы – бұл G графигімен бірдей төбелер жиынына ие субграф. Графтың k факторы – бұл k реттелі кеңейтілген субграф, ал k факторлануы графтың қабырғаларын бөлек k факторларға бөледі. G графигі k'' факторлы болады, егер ол k факторлануға ие болса. Атап айтқанда, 1 фактор – бұл толық шайқас, ал k реттелі графтың 1 факторлануы – k' түспен дұрыс қабырға бояуы. 2 фактор – бұл графтың барлық төбелерін қамтитын циклдар жиынтығы.
Толық графиктер
Толық графтың 1-факторлануы дөңгелек робин турниріндегі жұптастыруларға сәйкес келеді. Толық графтардың 1-факторлануы – толық гиперграфтардың 1-факторлануына қатысты Бараньяи теоремасының ерекше жағдайы. Жұп санындағы төбелері бар толық графтың 1-факторлануын құрудың бір әдісі – төбелердің біреуін қоспағанда, барлық төбелерді дұрыс көпбұрышқа орналастыру, ал қалған төбесін ортаға қою. Мұндай төбелер орналасуымен графтың 1-факторын құрудың бір жолы – ортадан бір көпбұрыш төбесіне дейінгі e қабырғасын және e-ге перпендикуляр түзулерде жатқан барлық мүмкін қабырғаларды таңдау. Осылай құрастырылған 1-факторлар графтың 1-факторлануын құрайды. K2, K4, K6, K8 графтарының әртүрлі 1-факторлануларының саны 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040-қа тең.
1-факторлау болжамы
G 2n түйіні бар k реттелі график болсын. Егер 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-факторлау
Егер граф 2-еселенген болса, онда ол кейбір k бүтін саны үшін 2k-тұрақты болуы керек. Джулиус Петерсен 1891 жылы осы қажетті шарттың жеткілікті екенін де көрсетті: кез келген 2k-тұрақты граф 2-еселенген. Егер байланысты граф 2k-тұрақты болса және шеттерінің саны жұп болса, онда Эйлер айналымының шеттерінен кезектесіп алынған екі жиынтықты фактор ретінде таңдау арқылы k-факторлануы мүмкін. Бұл тек байланысты графтарға ғана қатысты; үзіліссіз қарсы мысалдарға тақ циклдердің немесе K2k+1 көшірмелерінің біріккен жиындары кіреді. Обервольфах проблемасы толық графтардың изоморфты кішіграфтарға 2-факторлануының болуымен айналысады. Ол қандай кішіграфтар үшін мұндай факторлау мүмкін екенін сұрайды. Кішіграф байланысты болған жағдайда бұл мәселе белгілі (онда ол Гамильтон циклы болып табылады және бұл ерекше жағдай Гамильтон ыдырау проблемасы), бірақ жалпы жағдай әлі де ашық күйде.