Határidő: 2022-04-05 24:00

• 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. Ha találtunk \(k\) elemű klikket, akkor írjuk ki az elemeit a standard kimenetre. Ellenkező esetben írjuk ki, hogy „a gráfban nincs \(k\)-elemű klikk”.
  1. A klikk.py fá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.
  2. 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 az elemeit a standard kimenetre, és állítsuk le a keresést. Ha egyetlen kombináció sem klikk, akkor jelezzük, hogy a „gráfban nincs \(k\)-elemű klikk”.
  3. 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.

  Fájl	Klikk
  clique1.text	0 1 4 6
  clique2.text	a gráfban nincs 4-elemű klikk
  clique3.text	1 2 4 13 14
  clique4.text	a gráfban nincs 8-elemű klikk
  clique5.text	0 3 4 6 7
  clique6.text	0 3 4 6 16 24 27 37