Faktor-kritisk graf

En kvotientkritisk graf (eller næsten matchende graf [1] [2] .) er en graf med n toppunkter, hvor hver undergraf med n − 1 toppunkter har en perfekt match . (En perfekt matchning i en graf er en delmængde af kanter med den egenskab, at hver af grafens toppunkter er endepunktet for nøjagtigt en kant fra delmængden.)

En kombination, der dækker alle hjørner undtagen én, kaldes en næsten perfekt matchning . På samme måde er en kvotientkritisk graf en graf, hvor der er næsten perfekte matchninger, der ikke indeholder nogen af ​​hjørnerne.

Eksempler

Enhver cyklus af ulige længde er faktorkritisk [1] , ligesom enhver komplet graf med et ulige antal hjørner [3] . Mere generelt er enhver Hamilton -graf med et ulige antal hjørner kvotientkritisk. Venskabsgrafer (grafer dannet ved at forbinde et sæt trekanter med et fælles toppunkt) giver eksempler på grafer, der er faktorkritiske, men ikke Hamiltonske.

Hvis en graf G er kvotientkritisk, så er den en Mychelskian af G . For eksempel er Grötzsch-grafen , Mycelskian for en cyklus med fem toppunkter, kvotientkritisk [4] .

Enhver 2-vertex-forbundet klofri graf med et ulige antal hjørner er kvotientkritisk. For eksempel er grafen med 11 hjørner dannet af hjørnerne af et regulært icosahedron (grafen af ​​en snoet aflang femkantet pyramide ) både 2-forbundet og klofri, så den er kvotientkritisk. Dette resultat følger direkte af det mere fundamentale teorem, at enhver forbundet klofri graf med et lige antal hjørner har en perfekt match [5] .

Beskrivelse

Faktorkritiske grafer kan beskrives på flere forskellige måder, bortset fra at være defineret som grafer, hvis fjernelse af ethvert toppunkt tillader perfekt matchning:

Egenskaber

Faktorkritiske grafer skal altid have et ulige antal hjørner og skal være 2-kantforbundne (det vil sige, de kan ikke have nogen bro ) [10] . De er dog ikke nødvendigvis vertex-2-forbundne . Venskabsgrafer giver et modeksempel. En kvotientkritisk graf kan ikke være todelt , for i en næsten perfekt matchende todelt graf er de eneste hjørner, der kan fjernes for at producere en perfekt matchende graf, på den større side af den todelte graf.

Enhver toppunkt-2-forbundet faktorkritisk graf med m kanter har mindst m forskellige næsten perfekte matchninger, og mere generelt har enhver faktorkritisk graf med m kanter og c blokke (forbundne komponenter af 2 hjørner) mindst m − c + 1 forskellige næsten perfekte matchninger. Grafer, for hvilke disse grænser er nøjagtige, kan beskrives som havende en ørenedbrydning af en bestemt art [3] .

Enhver forbundet graf kan omdannes til en faktorkritisk graf ved at trække nok kanter sammen. Det minimumssæt af kanter, der skal kontraheres for at gøre en given graf G -faktor kritisk, danner en matroide basis , det faktum, at en polynomial-tids grådig algoritme kan bruges til at finde det mindste vægtede sæt af kanter, hvis sammentrækning gør grafen faktor- kritisk kritisk [11] . En tidlig algoritme til kontrahering af minimumsantallet af (uvægtede) kanter for at opnå en kvotientkritisk graf kan findes i Franks papir [12] .

Ansøgninger

En blomst er en kvotientkritisk undergraf af en større graf. Blomster spiller en nøglerolle i Edmonds algoritmerne for at finde den største matchning og den mindst vægtede perfekte matchning i ikke-todelte grafer [13] .

I kombinatorik af polyedre spiller kvotientkritiske grafer en vigtig rolle i beskrivelsen af ​​facetter af matchende polytoper af en given graf [1] [2] .

Generaliseringer og relaterede begreber

En graf siges at være k -faktor kritisk, hvis en delmængde af n − k hjørner har en perfekt match. Med denne definition er en næsten kompatibel (en:hypomatchable) graf 1-faktor-kritisk [14] . Endnu mere generelt er en graf ( a , b ) -faktor-kritisk, hvis en delmængde af n − k hjørner har en r -faktor, det vil sige, at den er mængden af ​​hjørner af en r - regulær undergraf i den givne graf.

Når folk taler om en kritisk graf (uden k- ), mener de normalt en graf, hvis fjernelse af ethvert toppunkt fører til et fald i antallet af farver, der er nødvendige for at farve grafen . Begrebet kritikalitet bruges meget mere udbredt i grafteori til grafer, hvor fjernelse af ethvert toppunkt ændrer en eller anden egenskab ved grafen. En kombinationskritisk graf er en graf, for hvilken fjernelse af ethvert toppunkt ikke ændrer størrelsen på den største matchende . Ifølge Gallai er kombinationskritiske grafer netop grafer, hvor enhver forbundet komponent er kvotientkritisk [15] . Komplementet af en kritisk graf er nødvendigvis kombinationskritisk, en kendsgerning brugt af Gallai til at bevise en nedre grænse for antallet af hjørner af en kritisk graf [16] .


Uden for grafteorien har begrebet faktorkritik en udvidelse til matroider ved at definere typen af ​​ørenedbrydning på matroider. En matroidea er faktorkritisk, hvis den har en ørenedbrydning, hvor alle ører er ulige [17] .

Noter

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

Litteratur