Factorizarea graficului

Un factor al unui grafic G este un subgraf care se întinde , adică un subgraf care are aceleași vârfuri ca și graficul G . Factorul k al graficului este un k - subgraf obișnuit , iar k - factorizarea descompune marginile graficului în k -factori care nu se intersectează. Se spune că un grafic G este k -factorizabil dacă permite o k -partiție. În special, setul de muchii al unui factor 1 este o potrivire perfectă , iar descompunerea 1 a unui grafic k - obișnuit este o colorare a muchiei cu k culori. Un factor 2 este un set de cicluri care acoperă toate vârfurile graficului.

1-factorizare

Dacă un grafic este factorizabil 1 (adică are o factorizare 1), atunci trebuie să fie un grafic obișnuit . Cu toate acestea, nu toate graficele obișnuite sunt factorizabile 1. Un graf k -regular este 1-factorizabil dacă indicele său cromatic este k . Exemple de astfel de grafice:

Orice graf bipartit regulat [1] [2] . Teorema nunții lui Hall poate fi folosită pentru a arăta că un graf bipartit k -regular conține o potrivire perfectă. Se poate elimina apoi potrivirea perfectă și graficul bipartit ( k − 1)-regular și se poate continua același proces recursiv.
Orice grafic complet cu un număr par de vârfuri (vezi mai jos ) [3] .

Cu toate acestea, există k -grafice regulate al căror indice cromatic este k + 1, iar aceste grafice nu sunt factorizabile 1. Exemple de astfel de grafice:

Orice grafic regulat cu un număr impar de vârfuri.
Contele Petersen .

Grafice complete

Factorizarea 1 a unui grafic complet corespunde împerecherii în turneele round robin . Factorizarea 1 a grafurilor complete este un caz special al teoremei lui Baranyai privind 1-factorizarea hipergrafelor complete .

O modalitate de a construi o factorizare 1 a unui grafic complet plasează toate vârfurile, cu excepția unuia, pe cerc, formând un poligon regulat , în timp ce vârful rămas este plasat în centrul cercului. Cu acest aranjament de vârfuri, procesul de construire a unui factor 1 constă în alegerea unei muchii e care conectează vârful central cu unul dintre vârfurile de pe cerc, apoi sunt selectate toate muchiile perpendiculare pe muchia e . Factorii 1 construiți în acest fel formează o factorizare 1 a graficului.

Numărul de 1-factorizări distincte este 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, … ( secvența AE00438 ) . $K_{2},K_{4},K_{6},K_{8},\dots$

Conjectura 1-factorizare

Fie G un graf k -regulat cu 2n vârfuri. Dacă k este suficient de mare, se știe că G trebuie să fie 1 factorizabil:

Dacă , atunci G este un grafic complet și, prin urmare, factorizabil 1 (vezi mai sus ). $k=2n-1$ $K_{2n)$
Dacă , atunci G poate fi obținut prin eliminarea unei potriviri perfecte din . Din nou G este 1-factorizabil. $k=2n-2$ $K_{2n)$
Chetwynd și Hilton [4] au arătat că pentru , graficul G este 1-factorizabil. $k\geqslant {\tfrac {12n}{7)}$

Conjectura de 1-factorizare [5] este o presupunere de lungă durată care susține că valoarea este suficient de mare. Formulare exactă: $k\aproximativ n$

Dacă n este impar și , atunci G este factorizabil 1. Dacă n este par și , atunci G este 1-factorizabil. $k\geqslant n$ $k\geqslant n-1$

Conjectura de umplere grea include conjectura de factorizare 1.

1-factorizare perfectă

O pereche perfectă de 1-factorizări este o pereche de 1-factori a căror unire dă un ciclu hamiltonian .

O 1-factorizare perfectă (P1F) a unui grafic este o 1-factorizare care are proprietatea că orice pereche de 1-factori este o pereche perfectă. O 1-factorizare perfectă nu trebuie confundată cu o potrivire perfectă (numită și 1-factor).

În 1964, Anton Kotzig a presupus că orice grafic complet , unde , are o factorizare 1 perfectă. Se știe că următoarele grafice au 1-factorizări perfecte [6] : $K_{2n)$ $n \geqslant 2$

O familie infinită de grafice complete , unde p este un prim impar (Anderson și Nakamura, independent), $K_{2p)$
O familie infinită de grafice complete , unde p este un prim impar $K_{p+1}$
sporadic alte grafice, inclusiv , unde . Există, de asemenea, rezultate mai recente aici . $K_{2n)$ ${\displaystyle 2n\in \{16,28,36,40,50,126,170,244,344,730,1332,1370,1850,2198,3126,6860,12168,16808,29792\)$

Dacă un graf complet are o 1-factorizare perfectă, atunci un graf complet bipartit are și o 1-factorizare perfectă [7] . $K_{n+1}$ $K_{{n,n}}$

2-factorizare

Dacă un grafic este factorizabil în 2, atunci trebuie să fie 2 k -regular pentru un întreg k . Julius Petersen a arătat în 1891 că această condiție necesară este, de asemenea, suficientă — orice graf regulat de 2k este factorizabil în 2 [8] .

Dacă un graf conectat este 2k -regular și are un număr par de muchii, el poate fi, de asemenea, k -factorizabil prin alegerea a doi factori care sunt muchii alternative ale ciclului Euler [9] . Acest lucru se aplică numai graficelor conectate, contraexemplele deconectate conțin o uniune deconectată de cicluri impare sau copii ale graficului K 2 k +1 .

Note

↑ Harari, 2003 , p. 107, Teorema 9.2.
↑ Distel, 2002 , p. 48, Corolarul 2.1.3.
↑ Harari, 2003 , p. 85, Teorema 9.1.
↑ Chetwynd, Hilton, 1985 .
↑ Chetwynd, Hilton, 1985 ; Niessen, 1994 ; Perkovic, Reed, 1997 ; Vest, 1985
↑ Wallis, 1997 , p. 125.
↑ Bryant, Maenhaut, Wanless, 2002 , p. 328–342.
↑ Petersen, 1891 , § 9, p. 200; Harari, 2003 , p. 113, Teorema 9.9; Vezi dovada din Distel, 2002 , p. 49, Corolarul 2.1.5
↑ Petersen, 1891 , p. 198 §6.

Literatură

John Adrian Bondy, USR Murty. Secțiunea 5.1: „Potriviri”. // Teoria graficelor cu aplicații . - Olanda de Nord, 1976. - ISBN 0-444-19451-7 . Arhivat pe 16 iunie 2012 la Wayback Machine
AG Chetwynd, AJW Hilton. Graficele obișnuite de grad înalt sunt factorizabile 1 // Proceedings of the London Mathematical Society. - 1985. - T. 50 , nr. 2 . - S. 193-206 . - doi : 10.1112/plms/s3-50.2.193 . .
Reinhard Distel. Capitolul 2: Potrivirea // Teoria graficelor. - Novosibirsk: Editura Institutului de Matematică, 2002. - ISBN 5-86134-101-X , UDC 519.17, LBC 22.17.
F. Harari. Capitolul 9 Factorizarea // Teoria graficelor. - M .: Editorial URSS, 2003. - ISBN 5-354-00301-6 .

Thomas Niessen. Cum să găsești subgrafe excesive în grafice cu grad maxim mare // Matematică aplicată discretă. - 1994. - T. 51 , nr. 1-2 . - S. 117-125 . - doi : 10.1016/0166-218X(94)90101-5 . .
L. Perkovic, B. Reed. Colorarea marginilor grafice regulate de grad înalt // Matematică discretă . - 1997. - T. 165-166 . - S. 567-578 . - doi : 10.1016/S0012-365X(96)00202-6 . .
Julius Peterson. Die Theorie der regulären graphs // Acta Mathematica . - 1891. - T. 15 . - S. 193-220 . - doi : 10.1007/BF02392606 .
Douglas B. West. 1-Conjectura de factorizare (1985?) . Probleme deschise - Teoria graficelor și combinatorie . Preluat: 9 ianuarie 2010. (nedefinit)
W. D. Wallis. factorizări unice. - Springer US , 1997. - T. 390 , nr. 1 . - S. 125 . - ISBN 978-0-7923-4323-3 . - doi : 10.1007/978-1-4757-2564-3_16 .
One-factorization / Michiel Hazewinkel. - Springer, 2001. - ISBN 978-1-55608-010-4 . (link indisponibil)
Darryn Bryant, Barbara M. Maenhaut, Ian M. Wanless. O familie de factorizări perfecte ale graficelor bipartite complete // Journal of Combinatorial Theory. - 2002. - T. 98 , nr. 2 . - S. 328-342 . — ISSN 0097-3165 . - doi : 10.1006/jcta.2001.3240 .

Weisstein, Eric W. Graph Factor la Wolfram MathWorld .
Weisstein, Eric W. k-Factor (engleză) pe site-ul Wolfram MathWorld .
Weisstein, Eric W. k -Factorable Graph la Wolfram MathWorld .

Lectură pentru lecturi suplimentare

Michael D. Plummer. Factori grafici și factorizare: 1985–2003: Un sondaj // Matematică discretă . - 2007. - T. 307 , nr. 7-8 . - S. 791-821 . - doi : 10.1016/j.disc.2005.11.059 .