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

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 szerint, aki számos egyéb klikkösszeg-alapú karakterizációt sorol fel. egy tétele volt, aki bizonyította, hogy a K5 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.. 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

Jegyzetek

. . . . . . . . . . .

Kategória:Gráfműveletek Kategória:Gráfminorok