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 által elvégzett gráfelméleti átfogalmazásáig, 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. magát a klikk kifejezést elsőként 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 Egy irányítatlan gráf C klikkje csúcsainak olyan 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 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 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 bármely gráf vagy a komplementere legalább a csúcsok számának logaritmusa szerinti klikket tartalmaz. 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., page 200. 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
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 Maga a „klikk” kifejezés és gráfelméleti használata 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. , és .
A bioinformatika számos különböző problémáját modellezték klikkek segítségével. Például 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; egy hasonló biklaszterezési problémát tárgyal, mely megköveteli, hogy minden klaszter egyben klikk legyen. a klikkek segítségével modellezi a táplálékláncok niche-eit. 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ő. 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 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 a klikkek segítségével analizált távközlési hálózatokat, 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.. 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 egy kémiai adatbázisban klikkekkel jellemez olyan vegyi anyagokat, melyek a célul kitűzött térszerkezettel nagyfokú hasonlóságot mutatnak. klikkekkel modellezi két vegyi anyag egymással való kötőhelyeit.
Fordítás
Jegyzetek
. . . . . . . . . . . . . . . . . . . . . .
További információk
Kategória:Gráfelméleti objektumok