Graffaktorisering

En faktor af en graf G er en spændende undergraf, det vil sige en undergraf, der har de samme hjørner som grafen G . Grafens k - faktor er en spændende k - regulær undergraf, og k - faktorisering opdeler grafens kanter i ikke-skærende k -faktorer. En graf G siges at være k -faktoriserbar, hvis den tillader en k -partition. Især er sættet af kanter af en 1-faktor en perfekt matchning , og 1-dekomponeringen af en k - regulær graf er en kantfarvning med k farver. En 2-faktor er et sæt af cyklusser , der dækker alle hjørnerne af grafen.

1-faktorisering

Hvis en graf er 1-faktoriserbar (det vil sige, den har en 1-faktorisering), så skal den være en almindelig graf . Det er dog ikke alle almindelige grafer, der kan 1-faktoriseres. En k -regulær graf er 1-faktoriserbar, hvis dens kromatiske indeks er k . Eksempler på sådanne grafer:

Enhver regulær todelt graf [1] [2] . Halls bryllupssætning kan bruges til at vise, at en k - regulær todelt graf indeholder et perfekt match. Man kan derefter fjerne den perfekte matchning og den ( k − 1)-regulære bipartite graf og fortsætte den samme proces rekursivt.
Enhver komplet graf med et lige antal hjørner (se nedenfor ) [3] .

Der er dog k -regulære grafer, hvis kromatiske indeks er k + 1, og disse grafer er ikke 1-faktoriserbare. Eksempler på sådanne grafer:

Enhver almindelig graf med et ulige antal hjørner.
Grev Petersen .

Komplet grafer

1-faktoriseringen af en komplet graf svarer til parring i round robin-turneringer . 1-faktoriseringen af komplette grafer er et specialtilfælde af Baranyais sætning om 1-faktoriseringen af komplette hypergrafer .

En måde at konstruere en 1-faktorisering af en komplet graf på placerer alle hjørnerne på cirklen undtagen én og danner en regulær polygon , mens den resterende top er placeret i midten af cirklen. Med dette arrangement af toppunkter består processen med at konstruere en 1-faktor i at vælge en kant e , der forbinder det centrale toppunkt med en af toppunkterne på cirklen, derefter vælges alle kanter vinkelret på kanten e . 1-faktorerne konstrueret på denne måde danner en 1-faktorisering af grafen.

Antallet af distinkte 1-faktoriseringer er 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, … ( sequence A ) . $K_{2},K_{4},K_{6},K_{8},\dots$

1-faktoriseringsformodningen

Lad G være en k -regulær graf med 2n toppunkter. Hvis k er stor nok, er det kendt, at G skal være 1-faktoriserbar:

Hvis , så er G en komplet graf , og derfor 1-faktoriserbar (se ovenfor ). $k=2n-1$ ${\displaystyle K_{2n))$
Hvis , så G kan opnås ved at fjerne en perfekt matchning fra . Igen er G 1-faktoriserbar. $k=2n-2$ ${\displaystyle K_{2n))$
Chetwynd og Hilton [4] viste, at for , er grafen G 1-faktoriserbar. $k\geqslant {\tfrac {12n}{7))$

1-faktoriseringsformodningen [5] er en langvarig formodning, der hævder, at værdien er tilstrækkelig stor. Præcis formulering: $k\approx n$

Hvis n er ulige og , så er G 1-faktoriserbar. Hvis n er lige og , så er G 1-faktoriserbar. $k\geqslant n$ $k\geqslant n-1$

Den tunge udfyldende formodning inkluderer 1-faktoriseringsformodningen.

Perfekt 1-faktorisering

Et perfekt par 1-faktoriseringer er et par 1-faktorer, hvis forening giver en Hamiltonsk cyklus .

En perfekt 1-faktorisering (P1F) af en graf er en 1-faktorisering, der har den egenskab, at ethvert par af 1-faktorer er et perfekt par. En perfekt 1-faktorisering bør ikke forveksles med en perfekt matchning (også kaldet en 1-faktor).

I 1964 formodede Anton Kotzig, at enhver komplet graf , hvor , har en perfekt 1-faktorisering. Det er kendt, at følgende grafer har perfekte 1-faktoriseringer [6] : ${\displaystyle K_{2n))$ $n \geqslant 2$

En uendelig familie af komplette grafer , hvor p er et ulige primtal (Anderson og Nakamura uafhængigt af hinanden), ${\displaystyle K_{2p))$
En uendelig familie af komplette grafer , hvor p er et ulige primtal $K_{p+1}$
sporadisk andre grafer, herunder , hvor . Der er også nyere resultater her . ${\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\))$

Hvis en komplet graf har en perfekt 1-faktorisering, så har en komplet todelt graf også en perfekt 1-faktorisering [7] . $K_{n+1}$ $K_{{n,n}}$

2-faktorisering

Hvis en graf er 2-faktoriserbar, så skal den være 2 k -regulær for et heltal k . Julius Petersen viste i 1891, at denne nødvendige betingelse også er tilstrækkelig - enhver 2k -regulær graf er 2-faktoriserbar [8] .

Hvis en forbundet graf er 2k -regular og har et lige antal kanter, kan den også være k -faktoriserbar ved at vælge to faktorer, der er alternerende kanter af Euler-cyklussen [9] . Dette gælder kun for forbundne grafer, afbrudte modeksempler indeholder en afbrudt forening af ulige cyklusser eller kopier af grafen K 2 k +1 .

Noter

↑ Harari, 2003 , s. 107, sætning 9.2.
↑ Distel, 2002 , s. 48, konsekvens 2.1.3.
↑ Harari, 2003 , s. 85, sætning 9.1.
↑ Chetwynd, Hilton, 1985 .
↑ Chetwynd, Hilton, 1985 ; Niessen, 1994 ; Perkovic, Reed, 1997 ; West, 1985
↑ Wallis, 1997 , s. 125.
↑ Bryant, Maenhaut, Wanless, 2002 , s. 328-342.
↑ Petersen, 1891 , § 9, s. 200; Harari, 2003 , s. 113, sætning 9.9; Se beviset i Distel, 2002 , s. 49, Corollary 2.1.5
↑ Petersen, 1891 , s. 198 §6.

Litteratur

John Adrian Bondy, USR Murty. Afsnit 5.1: "Matchinger". // Grafteori med applikationer . - Nord-Holland, 1976. - ISBN 0-444-19451-7 . Arkiveret 16. juni 2012 på Wayback Machine
AG Chetwynd, AJW Hilton. Regelmæssige grafer af høj grad er 1-faktoriserbare // Proceedings of the London Mathematical Society. - 1985. - T. 50 , no. 2 . - S. 193-206 . - doi : 10.1112/plms/s3-50.2.193 . .
Reinhard Distel. Kapitel 2: Matching // Grafteori. - Novosibirsk: Publishing House of the Institute of Mathematics, 2002. - ISBN 5-86134-101-X , UDC 519.17, LBC 22.17.
F. Harari. Kapitel 9 Faktorisering // Grafteori. - M .: Redaktionel URSS, 2003. - ISBN 5-354-00301-6 .

Thomas Niessen. Sådan finder du overfyldte undergrafer i grafer med stor maksimal grad // Diskret anvendt matematik. - 1994. - T. 51 , no. 1-2 . - S. 117-125 . - doi : 10.1016/0166-218X(94)90101-5 . .
L. Perkovic, B. Reed. Kantfarve regelmæssige grafer af høj grad // Diskret matematik . - 1997. - T. 165-166 . - S. 567-578 . - doi : 10.1016/S0012-365X(96)00202-6 . .
Julius Petersen. Die Theorie der regulären graphs // Acta Mathematica . - 1891. - T. 15 . - S. 193-220 . - doi : 10.1007/BF02392606 .
Douglas B. West. 1-faktoriseringsformodning (1985?) . Åbne problemer - Grafteori og kombinatorik . Hentet: 9. januar 2010. (ubestemt)
W. D. Wallis. en-faktoriseringer. - Springer US , 1997. - T. 390 , no. 1 . - S. 125 . - ISBN 978-0-7923-4323-3 . - doi : 10.1007/978-1-4757-2564-3_16 .
En-faktorisering / Michiel Hazewinkel. - Springer, 2001. - ISBN 978-1-55608-010-4 . (utilgængeligt link)
Darryn Bryant, Barbara M. Maenhaut, Ian M. Wanless. En familie af perfekte faktoriseringer af komplette bipartite grafer // Journal of Combinatorial Theory. - 2002. - T. 98 , no. 2 . - S. 328-342 . — ISSN 0097-3165 . - doi : 10.1006/jcta.2001.3240 .

Weisstein, Eric W. Graph Factor hos Wolfram MathWorld .
Weisstein, Eric W. k-Factor (engelsk) på Wolfram MathWorld -webstedet .
Weisstein, Eric W. k -Factorable Graph hos Wolfram MathWorld .

Læsning for yderligere læsning

Michael D. Plummer. Graffaktorer og faktorisering: 1985–2003: En undersøgelse // Diskret matematik . - 2007. - T. 307 , no. 7-8 . - S. 791-821 . - doi : 10.1016/j.disc.2005.11.059 .