Klikk (gráfelmélet) – Wikipédia

Egy gráf, melynek van
  • 23 db 1 csúcsú klikkje (a csúcsok),
  • 42 db 2 csúcsú klikkje (az élek),
  • 19 db 3 csúcsú klikkje (a világosabb és sötétebb kék háromszögek) és
  • 2 db 4 csúcsú klikkje (sötétkék területek).
A 11 világoskék háromszög maximális klikkeket alkot. A két sötétkék 4-klikk maximális, egyben maximális elemszámú is, továbbá a gráf klikkszáma is 4.
Egy biklikk: a K3,3 teljes páros gráf.

A matematika, azon belül a gráfelmélet területén a klikk (clique) egy irányítatlan gráf csúcsainak olyan halmaza, melyek feszített részgráfja teljes; tehát a klikk bármely két csúcsa között van él, bármely két csúcsa szomszédos. A klikk a gráfelmélet alapvető fogalmai közé tartozik, számos matematikai problémában és gráfkonstrukcióban előkerülnek. A klikkeket a számítástudomány is behatóan tanulmányozta: annak eldöntése, hogy létezik-e egy gráfban adott méretű klikk (a klikkprobléma) NP-teljes; a probléma nehézsége ellenére számos, klikkek keresésére szolgáló algoritmus létezik.

Bár a teljes részgráfok vizsgálata visszanyúlik legalább a Ramsey-elmélet (Erdős & Szekeres 1935) által elvégzett gráfelméleti átfogalmazásáig,[1] magát a klikk kifejezést elsőként (Luce & Perry 1949) használta, aki az ismeretségi hálózatok teljes részgráfjaival modellezte az emberekből álló klikkeket; tehát olyan embercsoportokat, akik közül mindenki ismer mindenkit. A klikkek számos más tudományterületen ismertek, különösen a bioinformatikában.

Definíciók

[szerkesztés]

Egy G = (V, E) irányítatlan gráf C klikkje csúcsainak olyan CV részhalmaza, melyben bármely két csúcs szomszédos. Ezzel ekvivalens megfogalmazás, hogy a G gráf C által feszített részgráfja teljes gráf. Egyes esetekben a klikk kifejezés alatt magát a feszített részgráfot értjük.

A klikk csúcsainak számát a klikk méretének vagy rendjének is mondják. A k csúcsú klikket röviden k-klikknek is nevezik.

A maximális klikk (maximal clique) a gráf olyan klikkje, ami nem terjeszthető ki szomszédos csúcsok hozzáadásával, tehát csúcsai nem képezik egy másik klikk valódi részhalmazát. Egyes szerzők klikk-meghatározása eleve magában foglalja a maximalitás kritériumát, ők a nem maximális teljes részgráfokra más terminológiát alkalmaznak.

A maximális elemszámú klikk (maximum clique) a G gráfnak olyan klikkje, aminél nincsen több csúcsból álló klikk a gráfban.

A G gráf klikkszáma a maximális elemszámú klikkjének a mérete; a jele ω(G).

A G gráf metszetszáma (intersection number) a G éleit lefedő klikkek lehetséges minimális száma.

A G gráf klikkfedési száma (clique cover number) a G csúcsait lefedő (nem feltétlenül diszjunkt) klikkek lehetséges minimális száma.

A klikk „ellentéte” a független csúcshalmaz, abban az értelemben, hogy minden klikk a komplementer gráf egy független csúcshalmazának felel meg. A klikkfedési probléma a gráf csúcsait lefedő minimális számú klikk megkeresése.

Kapcsolódó fogalom a bi-klikk, páros klikk avagy teljes páros részgráf. Egy gráf biklikkfedési száma (bipartite dimension), d(G) a gráf éleit lefedő páros klikkek lehetséges minimális száma.

Egy gráf klikkgráfja az a gráf, aminek minden pontja megfelel az eredeti gráf egy-egy maximális klikkjének, és két pont akkor van összekötve, ha a megfelelő klikkek metszete nem üres.

Eredmények

[szerkesztés]

A klikkekkel kapcsolatos matematikai eredmények közül néhány:

  • Tetszőleges gráfra teljesül, hogy (az i-edik csúcs fokszámát di-vel jelölve)
  • A legkisebb olyan R szám, amire egy R csúcsú gráfban biztosan van egy m csúcsú klikk vagy egy n elemű független ponthalmaz, az Ramsey-szám. A Ramsey-tétel kimondja, hogy minden m-re és n-re létezik ilyen szám, de a pontos értékük meghatározása nehéz feladat.
  • A klikkszám mindig kisebb vagy egyenlő, mint a kromatikus szám; azt a gráfot, aminek minden feszített részgráfjára teljesül, hogy a klikkszáma megegyezik a kromatikus számával, perfekt gráfnak nevezzük. A legnagyobb olyan n csúcsú gráf, amiben nincs k csúcsú klikk, a Turán-gráf.
  • A Turán-tétel (Turán 1941) alsó korlátot ad a sűrű gráfok klikkjeinek méretére. Ha egy gráf elegendően sok éllel rendelkezik, tartalmaznia kell egy nagy klikket. Például minden, csúccsal és több mint éllel rendelkező gráfban kell lennie 3-klikknek.
  • A Ramsey-tétel értelmében (Graham, Rothschild & Spencer 1990) bármely gráf vagy a komplementere legalább a csúcsok számának logaritmusa szerinti klikket tartalmaz.
  • (Moon & Moser 1965) eredménye szerint egy 3n csúcsból álló gráf legfeljebb 3n maximális klikket tartalmazhat. A korlátot ténylegesen elérő gráfok a K3,3,... Moon–Moser-gráfok , a Turán-tétel extremális eseteként fellépő Turán-gráfok speciális esetei.
  • A Hadwiger-sejtés a gráf legnagyobb klikk minorját (a gráf Hadwiger-számát) a kromatikus számával hozza kapcsolatba.
  • Az Erdős–Faber–Lovász-sejtés szintén a gráfok színezését hozza kapcsolatba a klikkekkel.

Számos fontos gráfosztály határozható meg vagy karakterizálható klikkjei alapján:

  • Egy klasztergráf vagy P3-mentes gráf olyan gráf, melynek összefüggő komponensei klikkek.
  • Egy blokkgráf vagy klikkfa olyan gráf, melyben minden kétszeresen összefüggő komponens klikk.
  • Egy húrgráf olyan gráf, melynek csúcsaira létezik olyan rendezés, hogy bármely v csúcs környezetében lévő csúcsok közül a rendezésben utána következő csúcsok klikket alkotnak (bármely feszített részgráf tartalmaz szimpliciális csúcsot).
  • Egy kográf olyan gráf, melynek feszített részgráfjaiban bármely maximális klikk bármely maximális független csúcshalmazt egyetlen csúcsban metsz.
  • Egy intervallumgráf olyan gráf, melynek maximális klikkjeire létezik olyan rendezés, hogy bármely v csúcsra a v-t tartalmazó klikkek egymás után következnek a rendezésben.
  • Egy élgráf olyan gráf, melyben lehetséges klikkek olyan éldiszjunkt gyűjteményét azonosítani (megengedve, hogy egyes klikkek egyetlen csúcsból álljanak), melyek a gráf éleit úgy particionálják, hogy a gráf minden csúcsa pontosan két klikkbe tartozzon.
  • Egy perfekt gráf olyan gráf, melynek minden feszített részgráfjában a kromatikus szám a klikkszámmal megegyezik.
  • Egy split gráf olyan gráf, melynek csúcsai egy klikkbe és egy független csúcshalmazba oszthatók szét.
  • Egy háromszögmentes gráfban a csúcsokon és éleken kívül nincsen több klikk.

A fentieken túl számos más matematikai konstrukciónak van köze a klikkekhez. Néhány közülük:

  • A G gráf klikk-komplexuma egy X(G) absztrakt szimpliciális komplexum, mely G minden klikkjéhez egy szimplexet tartalmaz.
  • A G gráfhoz tartozó irányítatlan κ(G) szimplexgráf egy csúcsot tartalmaz G minden klikkjéhez és minden olyan klikk között húzódik él, melyek egyetlen csúcsban különböznek. A mediángráfok közé tartozik, és kapcsolódik a gráf klikkjeinek medián algebrájához: az A, B, és C klikken értelmezett m(A,B,C) medián egy olyan klikk, melynek csúcsai az A, B és C klikkek közül legalább kettőbe beletartoznak.[2]
  • A klikk-összeg művelet segítségével két gráf egy közös klikk mentén összefűzhető.
  • A klikkszélesség egy gráf bonyolultságát fejezi ki annak fényében, hogy legalább hány különbözően címkézett csúcsra van szükség ahhoz, hogy a gráfot felépítsük a diszjunkt unió, átcímkézés és az adott címkéjű csúcspárok összekötésének művelete segítségével. Az 1 klikkszélességű gráfok éppen a diszjunkt klikkekből felépített gráfok (klasztergráfok).
  • Egy gráf metszetszáma éleit lefedő klikkek lehetséges minimális száma.
  • Egy gráf klikkgráfja a maximális klikkjei metszetgráfjának felel meg.

A teljes részgráfokkal közeli kapcsolatban álló fogalmak a teljes gráfok topologikusan izomorf felosztásai és a teljes gráfminorok. A Kuratowski-tétel és a Wagner-tétel a síkgráfokat tiltott teljes, illetve teljes páros felosztásaik és minoraik alapján karakterizálja.

Számítástudomány

[szerkesztés]

A számítástudományban a klikkprobléma adott gráf maximális elemszámú klikkjének, illetve összes klikkjének megkeresése. NP-teljes, szerepel Karp 21 NP-teljes problémája között. Egyben rögzített paraméter mellett kezelhető és nehezen approximálható probléma. A klikkek keresésére kifejlesztett legjobb algoritmusok vagy exponenciális időben futnak (mint a Bron–Kerbosch-algoritmus) vagy valamely gráfosztályra vannak specializálva (pl. síkgráfok vagy perfekt gráfok), melyekre a probléma polinom időben megoldható.

Alkalmazásai

[szerkesztés]

Maga a „klikk” kifejezés és gráfelméleti használata (Luce & Perry 1949) munkásságából ered, aki az ismeretségi hálózatok teljes részgráfjaival modellezte az emberekből álló klikkeket; tehát olyan embercsoportokat, akik közül mindenki ismer mindenkit. Az ismeretségi hálózatok gráfelméleti vizsgálatának további fejleményeihez lásd pl. (Alba 1973), (Peay 1974) és (Doreian & Woodard 1994).

A bioinformatika számos különböző problémáját modellezték klikkek segítségével. Például (Ben-Dor, Shamir & Yakhini 1999) a génkifejeződési adatok klaszterezésének problémáját úgy modellezi, mint egy gráf diszjunkt klikkek uniójává való átalakításához szükséges lépések minimális számát; (Tanay, Sharan & Shamir 2002) egy hasonló biklaszterezési problémát tárgyal, mely megköveteli, hogy minden klaszter egyben klikk legyen. (Sugihara 1984) a klikkek segítségével modellezi a táplálékláncok niche-eit. (Day & Sankoff 1986) filogenetikai fák (evolúciós leszármazási vonalak) kikövetkeztetésének problémáját úgy írja le, mint egy olyan gráf maximális elemszámú klikkjeinek megkeresését, melyben a csúcsok a fajok tulajdonságait jelentik, és két csúcs akkor szomszédos, ha a két tulajdonság tökéletesen (homoplázia nélküli törzsfejlődési vonallal) összeköthető. (Samudrala & Moult 1998) a fehérjeszerkezet-előrejelzést úgy modellezik, mint klikkek keresését egy olyan gráfban, melynek csúcsai a fehérjék alegységeinek elhelyezkedéseinek felelnek meg. És a fehérjék közötti kölcsönhatások hálózatában klikkek keresésével (Spirin & Mirny 2003) fehérjék olyan klaszterét találta meg, melyek egymással szorosan kölcsönhatnak, de a klaszteren kívül kevés fehérjével lépnek kölcsönhatásba. A power graph analysis nevű módszer egyszerűsíti a komplex biológiai hálózatokat azzal, hogy a klikkeket és hasonló struktúrákat tekinti a hálózat alapvető építőelemeinek.

A villamosmérnöki szakmában (Prihar 1956) a klikkek segítségével analizált távközlési hálózatokat, (Paull & Unger 1959) pedig részlegesen specifikált Boole-függvények számításával hatékony áramkörök tervezésére használta őket. Klikkeket alkalmaztak automatikus tesztmintázat-előállításra is: a lehetséges hibák ún. inkompatibilitási gráfjában lévő nagy klikk alsó korlátot ad a teszthalmaz méretére.[3] (Cong & Smith 1993) leírja a klikkek egy alkalmazási területét egy elektronikus áramkör kisebb alegységekre való hierarchikus particionálásában.

A kémiában (Rhodes et al. 2003) egy kémiai adatbázisban klikkekkel jellemez olyan vegyi anyagokat, melyek a célul kitűzött térszerkezettel nagyfokú hasonlóságot mutatnak. (Kuhl, Crippen & Friesen 1983) klikkekkel modellezi két vegyi anyag egymással való kötőhelyeit.

Fordítás

[szerkesztés]
  • Ez a szócikk részben vagy egészben a Clique (graph_theory) 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

[szerkesztés]
  1. (Kuratowski 1930) korábbi, a síkgráfokat tiltott teljes, illetve teljes páros részgráfok alapján karakterizáló munkája eredetileg nem gráfelméleti, hanem topológiai megközelítésben íródott.
  2. (Barthélemy, Leclerc & Monjardet 1986), page 200.
  3. (Hamzaoglu & Patel 1998).

További információk

[szerkesztés]