Szigorúan akkordális grafikon

Egy irányítatlan G gráfot szigorúan akkordnak nevezünk , ha akkordális , és G -ben minden páros hosszúságú ( ) ciklusnak van páratlan húrja , vagyis egy éle, amely a ciklus két csúcsát páratlan távolságra (>1) köti össze. [1] .

Leírás

A szigorúan akkordális gráfokat a tiltott gráfok olyan gráfokként írják le, amelyek nem tartalmaznak háromnál hosszabb generált ciklust vagy generált részgráfként egy n -napot ( ) [2] [3] [4] . Az n -Sun egy akkordgráf, amelynek 2n csúcsa két részhalmazra van osztva, és úgy, hogy a W - ből származó w i csúcsoknak pontosan két szomszédja van, u i és . n - A Nap nem lehet szigorúan akkord, mivel a ciklusnak ... nincsenek páratlan akkordjai.

A szigorúan akkordális gráfok olyan gráfokként írhatók le, amelyeknek szigorú tökéletes kiküszöbölési sorrendje van, olyan csúcsrenddel, hogy bármely csúcs szomszédai, amelyek sorrendben később jönnek, egy klikket alkotnak , és úgy, hogy bármely , ha a sorrend i -edik csúcsa szomszédos k -edik és l -edik csúcs , valamint j -edik és k -edik csúcs szomszédos, akkor a j -edik és az l -edik csúcsnak is szomszédosnak kell lennie [3] [5] .

Egy gráf akkor és csak akkor szigorúan akkordális, ha bármely generált részgráfja rendelkezik egy egyszerű csúcsgal, vagyis olyan csúcsgal, amelynek szomszédai lineárisan vannak rendezve a befogadási sorrend szerint [3] [6] . Ezenkívül egy gráf akkor és csak akkor szigorúan akkordális, ha akkor és csak akkor, ha minden öt vagy annál hosszabb ciklusnak van 2 akkordú háromszöge, azaz egy háromszög, amelyet két akkord és a ciklus éle alkot [7] .

Egy gráf akkor és csak akkor szigorúan akkordális, ha bármelyik generált részgráfja duál akkordgráf [8] .

Szigorúan akkord gráfok írhatók le a teljes részgráfok számával , amelyekhez egy él tartozik [9] . Egy másik leírást ad a cikk De Caria és McKee [10] .

Elismerés

Egy egyszerű csúcs ismételt megkeresésével és eltávolításával meghatározható, hogy egy gráf szigorúan akkord-e polinomiális időben . Ha ez a folyamat kiküszöböli a gráf összes csúcsát, akkor a gráfnak szigorúan akkordnak kell lennie. Ellenkező esetben a folyamat nem talál egy részgráfot egyszerű csúcs nélkül, és ebben az esetben az eredeti gráf nem lehet szigorúan akkord. Szigorúan akkord gráf esetén a csúcsok eltávolításának sorrendjét szigorú tökéletes eliminációs sorrendnek nevezzük [3] .

Ismertek olyan alternatív algoritmusok, amelyek meg tudják határozni, hogy egy gráf szigorúan akkord-e, és ha igen, akkor hatékonyabban, időben konstruálhat szigorú tökéletes eliminációs sorrendet egy n csúcsú és m élű gráfra [11] [12] [13] .

Alosztályok

Fontos (a filogenetika alapján ) alosztály a k - levél fokok osztálya , vagyis a fa leveleiből két levél éllel való összekötésével kialakított gráfok, ha a fában a távolság nem haladja meg a k -t . A levélfok olyan gráf, amely egy k -levél foka valamilyen k esetén . Mivel a szigorúan akkord gráfok fokai szigorúan akkordálisak, a fák pedig szigorúan akkordálisak, ebből következik, hogy a levélfokozatok szigorúan akkordálisak. Ezek alkotják az erősen akkordális gráfok saját alosztályát, amely viszont a klasztergráfokat 2 lapos hatványként [14] tartalmazza . A szigorúan akkord gráfok másik fontos alosztálya az intervallumgráfok . Branstedt, Hudt, Mancini és Wagner [15] kimutatta, hogy az intervallumgráfok és az irányított gyökérutak nagyobb osztálya levélhatványok.

Algoritmikus problémák

Mivel az erősen akkordális gráfok akkordálisak és duálisakkordok is , különböző NP-teljes problémák, mint például a független halmazprobléma, a klikkprobléma , a színezés , a klikkfedési probléma , a domináló halmaz és a Steiner-minimálfa probléma hatékonyan megoldhatók erősen akkordális gráfok esetén. A gráfizomorfizmus probléma GI-teljes [16] szigorúan akkord gráfok esetén [17] . A Hamilton-ciklusok keresése továbbra is NP-teljes probléma a szigorúan akkordális felosztású gráfok esetében [18] .

Jegyzetek

  1. ↑ Brandstädt, Le, Spinrad, 1999 , p. 43. Meghatározás 3.4.1.
  2. ↑ Chang, 1982 .
  3. ↑ 1 2 3 4 Farber, 1983 .
  4. ↑ Brandstädt, Le, Spinrad, 1999 , p. 112, 7.2.1. Tétel.
  5. ↑ Brandstädt, Le, Spinrad, 1999 , p. 77, 5.5.1. Tétel.
  6. ↑ Brandstädt, Le, Spinrad, 1999 , p. 78, 5.5.2. Tétel.
  7. ↑ Dahlhaus, Manuel, Miller, 1998 .
  8. ↑ Brandstädt, Dragan, Chepoi, Voloshin, 1998 , p. 444, 3. következmény.
  9. ↑ McKee, 1999 .
  10. ↑ De Caria, McKee, 2014 .
  11. ↑ Lubiw, 1987 .
  12. ↑ Paige, Tarjan, 1987 .
  13. ↑ Spinrad, 1993 .
  14. ↑ Nishimura, Ragde, Thilikos, 2002 .
  15. ↑ Brandstädt, Hundt, Mancini, Wagner, 2010 .
  16. ↑ A cikk egy új teljességi osztályt mutat be - Graph Izomorfizmus teljesség
  17. ↑ Uehara, Toda, Nagoya, 2005 .
  18. ↑ Müller, 1996 .

Irodalom