Tényezőkritikus grafikon

A hányadoskritikus gráf (vagy majdnem egyező gráf [1] [2] .) egy n csúcsú gráf , amelyben minden n − 1 csúcsú részgráf tökéletes illeszkedéssel rendelkezik . (A tökéletes illeszkedés egy gráfban élek olyan részhalmaza, amelynek tulajdonsága, hogy a gráf minden csúcsa a részhalmazból pontosan egy él végcsúcsa.)

Az egy kivételével minden csúcsot lefedő kombinációt majdnem tökéletes illeszkedésnek nevezzük . Így ekvivalens, hányados-kritikus gráf az, amelyben szinte tökéletes egyezések vannak, amelyek nem tartalmazzák egyik csúcsot sem.

Példák

Bármely páratlan hosszúságú ciklus faktorkritikus [1] , akárcsak minden páratlan számú csúcsot tartalmazó teljes gráf [3] . Általánosságban elmondható, hogy minden páratlan számú csúcsú Hamilton -gráf hányadoskritikus. A barátsággráfok (háromszöghalmazok közös csúcsával való összekapcsolásával képzett gráfok) példákat adnak olyan gráfokra, amelyek faktorkritikusak, de nem hamiltoni.

Ha egy G gráf hányadoskritikus, akkor G Mychelski - je . Például a Grötzsch-gráf , egy öt csúcsú ciklus Mycelski-gráfja hányadoskritikus [4] .

Bármely 2-csúcshoz kapcsolódó , páratlan számú csúcsú, körmök nélküli gráf hányadoskritikus. Például a szabályos ikozaéder csúcsaiból alkotott 11 csúcsú gráf ( egy kanyargósan megnyúlt ötszögletű piramis gráfja ) egyszerre 2-összefüggésben van, és karmoktól mentes, tehát hányadoskritikus. Ez az eredmény egyenesen következik abból az alapvetőbb tételből, hogy bármely páros számú csúcsú összekapcsolt körmök nélküli gráf tökéletes illeszkedéssel rendelkezik [5] .

Leírás

A faktorkritikus gráfok többféleképpen is leírhatók, azon kívül, hogy olyan gráfokként határozhatók meg, amelyek bármely csúcsának eltávolítása lehetővé teszi a tökéletes illeszkedést:

Tulajdonságok

A faktorkritikus gráfoknak mindig páratlan csúcsszámúaknak kell lenniük, és 2 élhez kell kapcsolódniuk (azaz nem lehet hídjuk ) [10] . Ezek azonban nem feltétlenül 2-es csúcshoz kapcsolódnak . A barátság grafikonjai ellenpéldát adnak. A hányadoskritikus gráf nem lehet bipartit , mert egy közel tökéletesen illeszkedő bipartit gráfban az egyetlen csúcsok, amelyek eltávolításával tökéletesen illeszkedő gráfot kaphatunk, a bipartit gráf nagyobbik oldalán találhatók.

Bármely 2-es csúcshoz kapcsolódó, m élű faktorkritikus gráfnak legalább m különböző, majdnem tökéletes illeszkedése van, és általánosságban minden olyan faktorkritikus gráfnak, amely m éllel és c blokkkal (2 csúcs összekapcsolt összetevői) rendelkezik, legalább m − c + 1 különböző szinte tökéletes párosítás. Azok a grafikonok, amelyekre ezek a határok pontosak, úgy írhatók le, mint amelyek egy meghatározott típusú fülfelbontást tartalmaznak [3] .

Bármely összefüggő gráf faktorkritikus gráftá alakítható elegendő él összehúzásával . Az a minimális élhalmaz, amelyet össze kell zsugorítani, hogy egy adott gráf G faktorkritikus legyen, matroid bázist képez , az a tény, hogy egy polinomiális idejű mohó algoritmussal megkereshetjük azt a legkisebb súlyozott élhalmazt, amelynek összehúzódása a gráftényezőt kritikus.kritikus [11] . Frank [12] cikkében található egy korai algoritmus a (súlyozatlan) élek minimális számának összehúzására, hogy egy hányadoskritikus gráfot kapjunk .

Alkalmazások

A virág egy nagyobb gráf hányadoskritikus részgráfja . A virágok kulcsszerepet játszanak az Edmonds algoritmusokban , hogy megtalálják a legnagyobb illesztést és a minimális súlyozott tökéletes illeszkedést nem kétoldalú gráfokban [13] .

A poliéderek kombinatorikájában a hányadoskritikus gráfok fontos szerepet játszanak egy adott gráf illeszkedő politópjainak aspektusainak leírásában [1] [2] .

Általánosítások és kapcsolódó fogalmak

Egy gráfot k -tényezős kritikusnak nevezünk, ha n − k csúcsból álló bármely részhalmaz tökéletes illeszkedést mutat. Ezzel a definícióval egy majdnem kompatibilis (en:hypomatchable) gráf 1-faktoros kritikus [14] . Még általánosabban, egy gráf ( a , b ) -tényezőkritikus, ha n − k csúcsból álló bármely részhalmaz rendelkezik r -faktorral, vagyis az adott gráf egy r - szabályos részgráfjának csúcskészlete .

Amikor az emberek kritikus gráfról beszélnek ( k- nélkül), akkor általában olyan gráfra gondolnak, amelynek bármely csúcsának eltávolítása a gráf színezéséhez szükséges színek számának csökkenéséhez vezet . A kritikusság fogalmát sokkal szélesebb körben használják a gráfelméletben olyan gráfok esetében, amelyekben bármely csúcs eltávolítása megváltoztatja a gráf valamely tulajdonságát. A kombinációkritikus gráf olyan gráf, amelynél a csúcsok eltávolítása nem változtatja meg a legnagyobb egyezés méretét . Gallai szerint a kombinációkritikus gráfok pontosan olyan gráfok, amelyekben bármely kapcsolódó komponens hányadoskritikus [15] . Egy kritikus gráf komplementere szükségképpen kombinációs kritikus, ezt a tényt Gallai használta a kritikus gráf csúcsainak számának alsó korlátjának bizonyítására [16] .


A gráfelméleten kívül a faktorkritikusság fogalma kiterjed a matroidokra is azáltal, hogy meghatározza a füldekompozíció típusát a matroidokon. Egy matroid faktorkritikus, ha olyan füldekompozíciója van, amelyben minden fül páratlan [17] .

Jegyzetek

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

Irodalom