Az NP-teljes problémák megoldásának egy lehetséges módszere a
„nyers erő” alkalmazása. Ebben a megközelítésben generáljuk a
bemenethez tartozó összes lehetséges tanút, és egyesével
ellenőrizzük őket. Ha találunk egy jó tanút, akkor a bemenet benne
van a vizsgált nyelvben, míg ha egyetlen generált tanú sem volt
jó, akkor a bemenet biztosan nem eleme a nyelvnek. Természetesen
ettől az eljárástól sem remélhetjük, hogy a feladatot polinom
időben oldja meg.
A \(\textrm{CLIQUE}\) nyelv az olyan \((G, k)\) párokból
áll, ahol a \(G\) egyszerű irányítatlan gráfban van pontosan \(k\)
elemű klikk, azaz teljes részgráf. Arra, hogy \((G, k) \in
\textrm{CLIQUE}\), jó tanú egy \(k\) elemű \(F \subseteq
V(G)\) klikk. Ha \(|V(G)| = n\), akkor az \(F\)
halmazról \(O(n^2)\) időben eldönthető, hogy egyetlen \(u, v \in
F\) pontpár között sem húzódik él a gráfban.
Készítsünk olyan programot, ami a parancssori argumentumként
kapott fájlban leírt \((G, k)\) párról eldönti, hogy a
\(\textrm{CLIQUE}\) nyelvben van-e.
A clique.pyfájlban
megadtuk
a grafot_olvas
függvényt, ami beolvassa a parancssori argumentumként megadott
fájlból \(G\) gráf éllistáját és a \(k\) számot. A beolvasott
fájl formátumát és a függvény visszatérési értékét a
függvény forráskódjának docstring megjegyzésében
dokumentáltuk. Ezt a fájl módosítsuk a következőképp.
Generáljuk a gráf \(\{0, 1, \ldots, n - 1\}\) csúcsainak
\(k\) elemű kombinációit, és vizsgáljuk meg, hogy teljes részgráfot
alkotnak-e.
Ha az \(F\) kombináció klikk,
akkor írjuk ki a standard kimenetre hogy klikk: majd \(F\) elemeit, és
állítsuk le a keresést. Kimeneti formátum példa:
klikk: 0 1 4 6
vagy
klikk: [0, 1, 4, 6]
Ha egyetlen kombináció sem klikk,
akkor jelezzük, hogy a gráfban nincs \(k\)-elemű klikk így:
nincs
A \(k\)-elemű részhalmazok generálásához használjuk
az itertools
csomag combinations
függvénye.
Próbáljuk ki a programot az alábbi fájlokkal! Azokhoz a
bemenetekhez, melyek a \(\textrm{CLIQUE}\) nyelvben vannak,
megadtunk egy klikket is példaként a
kimenetre. Természetesen más klikk is elfogadható jó
tanúnak.