Klikk (gráfelmélet)

A Wikipédiából, a szabad enciklopédiából

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-edik csúcs fokszámát di-vel jelölve)

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

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 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 egy ugyanakkora független ponthalmaz felel meg. 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 R(m,n) 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.

Források[szerkesztés | forrásszöveg szerkesztése]