clique problem

clique problem (tsz. clique problems)

1. (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.

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.

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}$

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?

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

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

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

• 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)

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

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

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

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

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]])
                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;
}

• 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

• 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)