Faktorkritisk graf

En kvotkritisk graf (eller nästan matchande graf [1] [2] .) är en graf med n hörn där varje subgraf med n − 1 hörn har en perfekt matchning . (En perfekt matchning i en graf är en delmängd av kanter med egenskapen att var och en av grafens hörn är ändpunkten för exakt en kant från delmängden.)

En kombination som täcker alla hörn utom en kallas nästan perfekt matchning . På samma sätt är en kvotkritisk graf en graf där det finns nästan perfekta matchningar som inte innehåller någon av hörnen.

Exempel

Varje cykel med udda längd är faktorkritisk [1] , liksom alla kompletta grafer med ett udda antal hörn [3] . Mer generellt är alla Hamiltonska grafer med ett udda antal hörn kvotkritiska. Vänskapsgrafer (grafer som bildas genom att koppla ihop en uppsättning trianglar med en gemensam vertex) ger exempel på grafer som är faktorkritiska men inte Hamiltonska.

Om en graf G är kvotkritisk, så är den en Mychelskian av G . Till exempel är Grötzsch-grafen , Mycelskian för en cykel med fem hörn, kvotkritisk [4] .

Varje 2-vertex-ansluten klofri graf med ett udda antal hörn är kvotkritisk. Till exempel är grafen med 11 vertex som bildas av hörnen på en vanlig ikosaeder (grafen för en slingrande långsträckt femkantig pyramid ) både 2-kopplad och klofri, så den är kvotkritisk. Detta resultat följer direkt av den mer fundamentala satsen att varje sammankopplad klofri graf med ett jämnt antal hörn har en perfekt matchning [5] .

Beskrivning

Faktorkritiska grafer kan beskrivas på flera olika sätt, förutom att definieras som grafer vars borttagning av valfri vertex möjliggör perfekt matchning:

Egenskaper

Faktorkritiska grafer måste alltid ha ett udda antal hörn och måste vara 2-kantsanslutna (det vill säga de kan inte ha någon brygga ) [10] . De är dock inte nödvändigtvis vertex-2-anslutna . Vänskapsdiagram ger ett motexempel. En kvotkritisk graf kan inte vara tvådelad , eftersom i en nästan perfekt matchande tvådelad graf är de enda hörn som kan tas bort för att producera en perfekt matchande graf på den större sidan av den tvådelade grafen.

Varje vertex-2-kopplad faktorkritisk graf med m kanter har minst m olika nästan perfekta matchningar, och mer generellt har alla faktorkritiska grafer med m kanter och c - block (anslutna komponenter med 2 hörn) minst m − c + 1 olika nästan perfekta matchningar. Grafer för vilka dessa gränser är exakta kan beskrivas som att de har en öronnedbrytning av ett specifikt slag [3] .

Varje sammankopplad graf kan omvandlas till en faktorkritisk graf genom att dra ihop tillräckligt många kanter. Den minsta uppsättningen av kanter som måste sammandras för att göra en given graf G -faktor kritisk bildar en matroidbas , det faktum att en polynom-tid girig algoritm kan användas för att hitta den minsta viktade uppsättningen av kanter vars sammandragning gör att grafen faktor- kritisk kritisk [11] . En tidig algoritm för att dra ihop det minsta antalet (ovägda) kanter för att erhålla en kvotkritisk graf finns i Franks artikel [12] .

Applikationer

En blomma är en kvotkritisk subgraf av en större graf. Blommor spelar en nyckelroll i Edmonds algoritmer för att hitta den största matchningen och den minsta viktade perfekta matchningen i icke tvådelade grafer [13] .

I kombinatorik av polyedrar spelar kvotkritiska grafer en viktig roll för att beskriva aspekter av matchande polytoper i en given graf [1] [2] .

Generaliseringar och relaterade begrepp

En graf sägs vara k -faktor kritisk om någon delmängd av n − k hörn har en perfekt matchning. Med denna definition är en nästan kompatibel (en:hypomatchable) graf 1-faktor-kritisk [14] . Ännu mer generellt är en graf ( a , b ) -faktorkritisk om någon delmängd av n − k hörn har en r -faktor, det vill säga det är uppsättningen av hörn av en r - reguljär undergraf i den givna grafen.

När folk talar om en kritisk graf (utan k- ), menar de vanligtvis en graf vars borttagning av någon vertex leder till en minskning av antalet färger som behövs för att färga grafen . Begreppet kritikalitet används mycket mer allmänt i grafteorin för grafer där borttagandet av någon vertex ändrar någon egenskap hos grafen. En kombinationskritisk graf är en graf för vilken om du tar bort någon vertex inte ändrar storleken på den största matchningen . Enligt Gallai är kombinationskritiska grafer just grafer där vilken som helst kopplad komponent är kvotkritisk [15] . Komplementet av en kritisk graf är nödvändigtvis kombinationskritisk, ett faktum som Gallai använder för att bevisa en nedre gräns för antalet hörn av en kritisk graf [16] .


Utanför grafteorin har begreppet faktorkritik en utvidgning till matroider genom att definiera typen av öronnedbrytning på matroider. En matroid är faktorkritisk om den har en öronnedbrytning där alla öron är udda [17] .

Anteckningar

  1. ↑ 1 2 3 4 Pulleyblank, Edmonds, 1974 , sid. 214–242.
  2. ↑ 1 2 Cornuejols, Pulleyblank, 1983 , sid. 35–52.
  3. ↑ 12 Liu , Hao, 2002 , sid. 259–266.
  4. ↑ Došlić, 2005 , sid. 261–266.
  5. ↑ Favaron, Flandrin, Ryjáček, 1997 , sid. 271–278.
  6. ↑ Gallai, 1963 , sid. 135–139.
  7. ↑ Lovász, 1972 , sid. 279–280.
  8. ↑ Korte, Vygen, 2008 , sid. 235–241.
  9. ↑ Lou, Rao, 2004 , sid. 51–56.
  10. ↑ Seyffarth, 1993 , sid. 183–195.
  11. ↑ Szigeti, 1996 , sid. 233–241.
  12. ↑ Frank, 1993 , sid. 65–81.
  13. ↑ Edmonds, 1965 , sid. 449–467.
  14. ↑ Favaron, 1996 , sid. 41–51.
  15. ↑ Erdős, Furedi, Gould, Gunderson, 1995 , sid. 89–100.
  16. ↑ Gallai, 1963b , sid. 373–395.
  17. ↑ Szegedy, Szegedy, 2006 , sid. 353–377.

Litteratur