Klikkösszeg

Két síkbarajzolható gráf és a Wagner-gráf klikkösszege, aminek eredménye egy K₅-minormentes gráf.

A matematika, azon belül a gráfelmélet területén a klikkösszeg (clique-sum) két gráfot klikkjeiknél összeragasztással összekombináló művelet, a topológia összefüggő összeg műveletével analóg módon. Ha két gráf, G and H tartalmaznak azonos méretű klikkeket, akkor G és H klikkösszegének képzéséhez a két klikk egymásnak megfelelő csúcsait azonosítjuk, majd esetleg kitöröljük a klikk néhány élét. Egy k-klikkösszeg olyan klikkösszeg-művelet, melyben a klikkek legfeljebb k csúcsból állnak. Lehetséges kettőnél több gráf klikkösszegét vagy k-klikkösszegét is képezni a kétváltozós művelet ismételt alkalmazásával.

Különböző szerzők eltérő véleményen vannak abban, hogy mely éleket kellene eltávolítani a művelet folyamán. Egyes kontextusokban, mint a merev körű vagy a lekötött gráfok dekompozíciója során nincs szükség élek törlésére. Máshol, például a gráfok 3-csúcsösszefüggő komponensekre való SPQR-fafelbontása során az összes élt el kell távolítani. Néhány más kontextusban pedig, például az egyszerű gráfok minorzárt családjainak gráfminor-tételénél a művelet részeként megadják az eltávolítandó élek halmazát is.

Kapcsolódó fogalmak

A klikk-összeg művelet szoros kapcsolatban áll a faszélességgel: ha két gráf faszélessége legfeljebb k, akkor k-klikkösszegüké sem lehet nagyobb. Minden fa felírható éleinek 1-klikkösszegeként. Minden soros-párhuzamos gráf, vagy általánosabban minden legfeljebb 2 faszélességű gráf előáll háromszögek 2-klikkösszegeként. Ezek a fajta állítások nagyobb k értékekre is igazak: minden, legfeljebb k faszélességű gráf előállítható legfeljebb k + 1 csúcsú gráfok k-klikkösszegeként.

Közeli kapcsolat van továbbá a klikkösszeg-művelet és a gráfok összefüggősége között: ha egy gráf nem (k + 1)-szeresen csúcsösszefüggő (tehát található benne olyan k csúcsból álló halmaz, melynek eltávolításával a gráf szétesik), akkor előállítható kisebb gráfok k-klikkösszegeként. Például egy kétszeresen összefüggő gráf SPQR-fája a gráf háromszorosan összefüggő komponenseinek 2-klikkösszegként való reprezentációja.

Gráfszerkezet-elméleti alkalmazásai

Lekötött gráf, ami egy maximális síkgráf (sárga) és két merev körű gráf (piros és kék) klikk-összeg művelettel való összeragasztásával lett előállítva.

A klikkösszeg fontos szerepet játszik a gráfszerkezet-elméletben, ahol egyes gráfcsaládok karakterizálására alkalmas – azon az alapon, hogy mely gráfcsaládok tagjai állíthatók elő egyszerűbb gráfok klikkösszegeként. Az első ilyen jellegű eredmény (Wagner 1937) egy tétele volt, aki bizonyította, hogy a K₅ teljes gráfot minorként nem tartalmazó gráfok felírhatók síkbarajzolható gráfoknak a 8 csúcsú Wagner-gráffal való 3-klikkösszegeként; ezzel a strukturális tétellel megmutatható, hogy a négyszíntétel ekvivalens a Hadwiger-sejtés k = 5 esetével. A merev körű gráfok pontosan azok a gráfok, melyek klikkek klikkösszegeként élek törlése nélkül előállnak. A lekötött gráfok, ezen belül a gráfok, melyeknek minden legalább négy hosszúságú feszített köre a gráf minimális szeparátora (eltávolításával a gráf szétesik, és a kör semelyik valódi részhalmaza nem rendelkezik ezzel a tulajdonsággal), pedig éppen a klikkek és maximális síkgráfok klikkösszegeként állnak elő, szintén éltörlés nélkül. (Johnson & McKee 1996) a merev körű gráfok és soros-párhuzamos gráfok klikkösszegeivel karakterizálják az olyan parciális mátrixokat, melyek rendelkeznek pozitív definit kiegészítésekkel.

Bármely minorzárt gráfcsaládnak megadható a klikkösszeg-felbontása: bármely minorzárt gráfcsalád tagjai előállíthatok olyan gráfok klikkösszegeként, melyek korlátos génuszú felületekbe vannak „majdnem beágyazva” (nearly embedded) – ami azt jelenti, hogy a beágyazás kihagyhat néhány ún „apex”-et (itt: csúcs, ami csúcsok valamely önkényesen meghatározott részhalmazához csatlakozhat) és néhány „vortex”-et (alacsony útszélességű gráfok, amik a felületre történő beágyazás tartományait helyettesítik). Ezek a karakterizációk fontos eszközei a minorzárt gráfcsaládok NP-teljes optimalizációs problémáihoz készült közelítő algoritmusok, illetve szubexponenciális idejű pontos algoritmusok konstrukciójának.

Általánosítások

A klikkösszegek elmélete általánosítható gráfokról matroidokra. A Seymour-féle felbontási tétel (Seymour's decomposition theorem) úgy karakterizálja a reguláris matroidokat (a teljesen unimoduláris mátrixokkal reprezentálható matroidokat), mint grafikus matroidok (a gráf feszítőfáit reprezentáló matroidok) kografikus matroidok és egy bizonyos tízelemű matroid 3-összegei.

Fordítás

• Ez a szócikk részben vagy egészben a Clique-sum című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• Demaine, Erik D.; Fomin, Fedor V. & Hajiaghayi, MohammedTaghi et al. (2005), "Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs", Journal of the ACM 52 (6): 866–893, DOI 10.1145/1101821.1101823.
• Demaine, Erik D.; Hajiaghayi, MohammedTaghi & Nishimura, Naomi et al. (2004), "Approximation algorithms for classes of graphs excluding single-crossing graphs as minors", Journal of Computer and System Sciences 69 (2): 166–195, DOI 10.1016/j.jcss.2003.12.001.
• Demaine, Erik D.; Hajiaghayi, MohammedTaghi & Kawarabayashi, Ken-ichi (2005), "Algorithmic graph minor theory: decomposition, approximation, and coloring", Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, pp. 637–646, doi:10.1109/SFCS.2005.14.
• Diestel, Reinhard (1987), "A separation property of planar triangulations", Journal of Graph Theory 11 (1): 43–52, DOI 10.1002/jgt.3190110108.
• Kříž, Igor & Thomas, Robin (1990), "Clique-sums, tree-decompositions and compactness", Discrete Mathematics 81 (2): 177–185, DOI 10.1016/0012-365X(90)90150-G.
• Johnson, Charles R. & McKee, Terry A. (1996), "Structural conditions for cycle completable graphs", Discrete Mathematics 159 (1–3): 155–160, DOI 10.1016/0012-365X(95)00107-8.
• Lovász, László (2006), "Graph minor theory", Bulletin of the American Mathematical Society 43 (1): 75–86, DOI 10.1090/S0273-0979-05-01088-8.
• Robertson, N. & Seymour, P. D. (2003), "Graph minors XVI. Excluding a non-planar graph", Journal of Combinatorial Theory, Series B 89 (1): 43–76, DOI 10.1016/S0095-8956(03)00042-X.
• Seymour, P. D. (1980), "Decomposition of regular matroids", Journal of Combinatorial Theory, Series B 28 (3): 305–359, DOI 10.1016/0095-8956(80)90075-1.
• Seymour, P. D. & Weaver, R. W. (1984), "A generalization of chordal graphs", Journal of Graph Theory 8 (2): 241–251, DOI 10.1002/jgt.3190080206.
• Wagner, Klaus (1937), "Über eine Eigenschaft der ebenen Komplexe", Mathematische Annalen 114: 570–590, DOI 10.1007/BF01594196.