Graffaktorisering - Graph factorization

1-faktorisering av Desargues-diagram : varje färgklass är en 1-faktor.

Petersens graf kan delas upp i en 1-faktor (röd) och en 2-faktor (blå). Grafen är dock inte 1-faktor.

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

1-faktorisering av K ₈ i vilken varje 1-faktor består av en kant från centrum till en toppunkt av en heptagon tillsammans med alla möjliga vinkelräta kanter

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 ₂ , K ₄ , K ₆ , K ₈ , ... ä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

Vidare läsning