Klikkösszeg

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.

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.^[1]

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.

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^[2] (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.^[3] 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.^[4] (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).^[5] 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.^[6]

A klikkösszegek elmélete általánosítható gráfokról matroidokra.^[1] 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.^[1][7]

• 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.