Graffaktorisering - Graph factorization
I grafteori , en faktor av en graf G är en överspännande subgraf , dvs en subgraf som har samma vertex uppsättning som G . En k- faktor för en graf är en spännande k - vanlig subgraf, och en k- faktorisering delar upp kanterna på grafen i ojämna k- faktorer. En graf G sägs vara k- faktor om den medger en k- faktorisering. I synnerhet är en 1-faktor en perfekt matchning och en 1-faktorisering av en k - vanlig graf är en kantfärgning med k- färger. En 2-faktor är en samling cykler som spänner över alla kurvor i grafen.
1-faktorisering
Om ett diagram är 1-faktor (dvs har en 1-faktorisering) måste det vara ett vanligt diagram . Men inte alla vanliga diagram är 1-faktor. Ett k- regelbundet diagram är 1-faktor om det har kromatiskt index k ; exempel på sådana grafer inkluderar:
- Varje vanlig bipartitgraf . Halls äktenskapssats kan användas för att visa att en k- regelbunden bipartitgraf innehåller en perfekt matchning. Man kan sedan ta bort den perfekta matchningen för att erhålla en ( k - 1) -regelbunden bipartitgraf och tillämpa samma resonemang upprepade gånger.
- Alla kompletta diagram med ett jämnt antal noder (se nedan ).
Det finns emellertid också k -regelbundna grafer som har kromatiskt index k + 1, och dessa grafer är inte 1-faktor; exempel på sådana grafer inkluderar:
- Alla vanliga diagram med ett udda antal noder.
- Den Petersen grafen .
Kompletta diagram
En 1-faktorisering av ett fullständigt diagram motsvarar parningar i en turnering . 1-faktoriseringen av kompletta grafer är ett speciellt fall av Baranyais teorem om 1-faktorisering av fullständiga hypergrafer .
En metod för att konstruera en 1-faktorisering av ett fullständigt diagram på ett jämnt antal hörn innefattar att placera alla utom en av hörnpunkterna på en cirkel och bilda en vanlig polygon med det återstående toppunktet i mitten av cirkeln. Med detta arrangemang av hörnpunkter är ett sätt att konstruera en 1-faktor i diagrammet att välja en kant e från centrum till ett enda polygonhörn tillsammans med alla möjliga kanter som ligger på linjer vinkelrätt mot e . De 1-faktorer som kan konstrueras på detta sätt bildar en 1-faktorisering av diagrammet.
Antalet distinkta 1-faktoriseringar av K 2 , K 4 , K 6 , K 8 , ... är 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, ... OEIS : A000438 .
1-faktorisering gissningar
Låt G vara ett k- regelbundet diagram med 2 n- noder. Om k är tillräckligt stort är det känt att G måste vara 1-faktor:
- Om k = 2 n - 1, är G hela grafen K 2 n och därmed 1-faktor (se ovan ).
- Om k = 2 n - 2 kan G konstrueras genom att ta bort en perfekt matchning från K 2 n . Återigen är G 1-faktor.
- Chetwynd & Hilton (1985) visar att om k ≥ 12n / 7, så är G 1-faktor.
Den 1-faktorisering gissningar är en långvarig förmodan att stater att k ≈ n är tillräcklig. I exakta termer är antagandet:
- Om n är udda och k ≥ n , är G 1-faktor. Om n är jämnt och k ≥ n - 1 är G 1-faktor.
Den överfulla antagandet innebär antagandet om 1-faktorisering.
Perfekt 1-faktorisering
Ett perfekt par från en 1-faktorisering är ett par 1-faktorer vars förening inducerar en Hamilton-cykel .
En perfekt 1-faktorisering (P1F) i en graf är en 1-faktorisering som har den egenskapen att varje par av 1-faktorer är ett perfekt par. En perfekt 1-faktorisering bör inte förväxlas med en perfekt matchning (även kallad 1-faktor).
1964 antog Anton Kotzig att varje komplett diagram K 2 n där n ≥ 2 har en perfekt 1-faktorisering. Hittills är det känt att följande grafer har en perfekt 1-faktorisering:
- den oändliga familjen med kompletta grafer K 2 p där p är en udda prim (av Anderson och även Nakamura, oberoende),
- den oändliga familjen med kompletta grafer K p + 1 där p är en udda prim,
- och sporadiska ytterligare resultat, inklusive K 2 n där två n ∈ {16, 28, 36, 40, 50, 126, 170, 244, 344, 730, 1332, 1370, 1850, 2198, 3126, 6860, 12168, 16808, 29792}. Några nyare resultat samlas här .
Om den fullständiga grafen K n + 1 har ett perfekt en-faktorisering, då den komplett bipartit graf K n , n också har en perfekt ett-faktorisering.
2-faktorisering
Om ett diagram är 2-faktor, måste det vara 2 k- regelbundet för vissa heltal k . Julius Petersen visade 1891 att detta nödvändiga tillstånd också är tillräckligt: varje 2 k- regelbunden graf är 2-faktor.
Om ett anslutet diagram är 2 k- regelbundet och har ett jämnt antal kanter kan det också k -faktureras genom att välja var och en av de två faktorerna för att vara en alternerande delmängd av kanterna på en Euler-turné . Detta gäller endast anslutna grafer; urkopplade motexempel inkluderar disjunkta unioner av udda cyklerna, eller kopior av K 2 k 1 .
Den Oberwolfach problem gäller förekomsten av 2-faktoriseringar av komplett graf i isomorfa subgrafer. Den frågar efter vilka underbilder detta är möjligt. Detta är känt när subgrafen ansluts (i vilket fall det är en Hamilton-cykel och detta speciella fall är problemet med Hamilton-nedbrytning ) men det allmänna fallet förblir olöst.
Anteckningar
Referenser
- Bondy, John Adrian ; Murty, USR (1976), Grafteori med applikationer , Nord-Holland, ISBN 0-444-19451-7, arkiverad från originalet 2010-04-13 , hämtad 18-12-2019, Avsnitt 5.1: "Matchningar".
- Chetwynd, AG ; Hilton, AJW (1985), "Regular charts of high degree are 1-factorizable", Proceedings of the London Mathematical Society , 50 (2): 193–206, doi : 10.1112 / plms / s3-50.2.193.
- Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer , ISBN 3-540-26182-6, Kapitel 2: "Matcha, täcka och packa". Elektronisk utgåva .
- Harary, Frank (1969), Graph Theory , Addison-Wesley, ISBN 0-201-02787-9, Kapitel 9: "Faktorisering".
- "One-factorization" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
- Niessen, Thomas (1994), "How to find overfull subgraphs in charts with large maximum degree", Discrete Applied Mathematics , 51 (1–2): 117–125, doi : 10.1016 / 0166-218X (94) 90101-5.
- Perkovic, L .; Reed, B. (1997), "Kantfärgning av vanliga grafer av hög grad", Diskret matematik , 165–166: 567–578, doi : 10.1016 / S0012-365X (96) 00202-6.
- Petersen, Julius (1891), "Die Theorie der regulären graphs", Acta Mathematica , 15 : 193–220, doi : 10.1007 / BF02392606.
- West, Douglas B. "1-Factorization Conjecture (1985?)" . Öppna problem - Grafteori och kombinatorik . Hämtad 2010-01-09 .
- Weisstein, Eric W. "Graffaktor" . MathWorld .
- Weisstein, Eric W. "k-Factor" . MathWorld .
- Weisstein, Eric W. "k-Factorable Graph" . MathWorld .
Vidare läsning
- Plummer, Michael D. (2007), "Graffaktorer och faktorisering: 1985–2003: En undersökning", Diskret matematik , 307 (7–8): 791–821, doi : 10.1016 / j.disc.2005.11.059.