clique problem

Angol

Főnév

clique problem (tsz. clique problems)

(informatika) A klikk probléma (angolul: clique problem) a gráfelmélet és számítástudomány egyik legismertebb és NP-teljes problémája. Kiemelten fontos az algoritmuselméletben, mesterséges intelligenciában, hálózatelemzésben és optimalizálásban.

🧠 Mi az a klikk (clique)?

Egy gráfban egy klikk egy olyan csúcshalmaz, amelyben minden csúcspár között él van — azaz teljesen összekötött részgráf.

Formálisan:

Legyen ${\textstyle G=(V,E)}$ . Egy ${\textstyle C\subseteq V}$ klikk, ha:

${\textstyle \forall u,v\in C,u\neq v\Rightarrow (u,v)\in E}$

❓ A klikk probléma megfogalmazása

🟩 Döntési változat (Clique Decision Problem):

Input: Egy gráf ${\textstyle G=(V,E)}$ , és egy szám ${\textstyle k}$ . Kérdés: Tartalmaz-e ${\textstyle G}$ legalább ${\textstyle k}$ csúcsot tartalmazó klikket?

📈 Optimalizálási változat (Maximum Clique Problem):

Feladat: Meghatározni a gráf legnagyobb elemszámú klikkjét.

📊 Példa

Gráf:

A --- B
|  \  |
C --- D

Ez a gráf tartalmaz egy 4 csúcsú klikket: {A, B, C, D} – Minden csúcs össze van kötve minden másikkal

🔁 Kapcsolódó fogalmak

Fogalom	Kapcsolat
Független halmaz	Egy gráfban a komplementer gráfban a független halmaz klikknek felel meg
Vertex Cover	Kapcsolódik klikkhez (kiegészítő halmaz)
Gráfkomplementer	Egy gráf, amelyben ott van él, ahol az eredetiben nincs

A komplementer gráfban a klikk = eredeti gráfban a független halmaz.

🧮 Bonyolultság

A k-Klikk probléma NP-teljes
A maximum klikk keresés NP-nehéz
Akkor is nehéz, ha a gráf síkbarajzolható (planáris)

⚙️ Algoritmusok

1. Brute-force (minden csúcshalmazt ellenőriz)

Időbonyolultság: ${\textstyle O(2^{n}\cdot n^{2})}$

2. Backtracking + Pruning

Kipróbálás visszalépéssel
Elveti azokat a részhalmazokat, amelyek nem lehetnek klikkek

3. Bron–Kerbosch algoritmus

Hatékony algoritmus az összes maximális klikk megtalálására

4. Heurisztikák

Nem garantálják az optimális megoldást (pl. GRASP, tabu keresés)

🔧 Egyszerű C++ példa – van-e k-klikk?

bool isClique(const vector<vector<int>>& adj, const vector<int>& nodes) {
    for (int i = 0; i < nodes.size(); ++i)
        for (int j = i + 1; j < nodes.size(); ++j)
            if (!adj[nodes[i]][nodes[j]])
                return false;
    return true;
}

bool hasKClique(const vector<vector<int>>& adj, int k) {
    int n = adj.size();
    vector<int> vertices(n);
    iota(vertices.begin(), vertices.end(), 0);

    for (int mask = 0; mask < (1 << n); ++mask) {
        vector<int> subset;
        for (int i = 0; i < n; ++i)
            if (mask & (1 << i))
                subset.push_back(i);
        if (subset.size() == k && isClique(adj, subset))
            return true;
    }
    return false;
}

🧪 Alkalmazások

Szociális hálózatok: ismerősökből álló szoros csoportok (pl. Facebook baráti körök)
Biológia: fehérjék közötti kölcsönhatások
AI és tervezés: konfliktusmentes tevékenységek tervezése
Számítási kémiában: molekulák elemzése

🔁 Kapcsolat más problémákkal

Probléma	Átalakítható Klikk problémává
SAT	Igen, speciális konstrukcióval
3-SAT	Igen, → klikk-redukcióval
Independent Set	Igen, komplementer gráfon keresztül
Vertex Cover	Kiegészítő halmazként szerepel

📘 Összefoglalás

Fogalom	Leírás
Klikk	Olyan csúcshalmaz, ahol minden csúcspár össze van kötve éllel
k-klikk	Tartalmaz-e a gráf legalább k csúcsú klikket?
Maximum klikk	Legnagyobb elemszámú klikk megtalálása
Bonyolultság	NP-teljes, NP-nehéz
Kapcsolódó problémák	Független halmaz, vertex cover, SAT

További információk

clique problem - Szótár.net (en-hu)
clique problem - Sztaki (en-hu)
clique problem - Merriam–Webster
clique problem - Cambridge
clique problem - WordNet
clique problem - Яндекс (en-ru)
clique problem - Google (en-hu)
clique problem - Wikidata
clique problem - Wikipédia (angol)