Klikk (gráfelmélet)
gráfelméleti fogalom / From Wikipedia, the free encyclopedia
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.