Klikk (gráfelmélet)

A klikk a gráfelméletben olyan részgráf, aminek bármely két pontja között van él; más szóval, egy olyan részgráf, ami teljes gráf. 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.

Általában a gráf legnagyobb klikkje (a maximális klikk) az érdekes. Egyes szerzők klikk alatt automatikusan maximális klikket értenek.

A G gráf klikkszáma a legnagyobb klikkjének a mérete; a jele ω(G). A klikkszám megállapítása (a klikk probléma) NP-teljes. Tetszőleges gráfra teljesül, hogy (az i-ik csúcs fokszámát d_i-vel jelölve)

$\omega(G) \geq \sum_{i=1}^n \frac{1}{n-d_i}$

A klikkszám mindig kisebb, 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 elemű klikk, a $T_{n,k}$ Turán-gráf.

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.

A klikk ellentéte a független ponthalmaz: a klikknek a komplementer gráfban meg fog felelni egy ugynakkora független ponthalmaz. A legkisebb olyan R szám, amire egy R csúcsú gráfban biztosan van vagy egy m elemű klikk, vagy egy n elemű független ponthalmaz, az $R_{m,n}$ Ramsey-szám. A Ramsey-tétel kimondja, hogy minden m-re és n-re létezik ilyen szám, és felülről becsülhető, de a pontos megállapításuk (a színezési probléma) nehéz feladat.

Források

• Mathworld: klikk, klikkszám