Bevezet´ es a bonyolults´ agelm´ eletbe gyakorlatok I. B.∗ Az Ackermann f¨ uggv´ eny avagy nem minden olyan egyszer˝ u, mint amilyennek l´ atszik Legyen A(x, y) a k¨ ovetkez˝ o, rekurz´ıv m´ odon defini´alt f¨ uggv´eny: A(0, y) := y + 1 A(x, 0) := A(x − 1, 1) A(x, y) := A(x − 1, A(x, y − 1))
y≥0 x≥1 x, y ≥ 1
Hat´arozzuk meg (ak´ arhogy: fejben, pap´ıron, sz´am´ıt´og´epen, komputeralgebrai programmal, stb.) A(4,2) ´es A(5,1) ´ert´ek´et. 1. Tegy¨ uk fel, hogy egy sz´ am´ıt´ og´ep a TSP probl´em´at az ¨osszes lehets´eges ( 12 (n−1)!) k¨or´ ut el˝o´all´ıt´as´aval oldja meg, mindegyik k¨ or´ ut elemz´es´ere n · 5 · 10−5 m´asodperc id˝ot ford´ıtva. K¨or¨ ulbel¨ ul mennyi ideig tart ´ıgy a feladat megold´ asa n = 10, 14, 18, 22 v´aros eset´en? Megk¨onny´ıten´e a dolgunkat, ha egy egymilli´oszor gyorsabb ,,szupersz´ am´ıt´ og´ep” ´allna rendelkez´es¨ unkre? 2. Tegy¨ uk fel, hogy van egy sz´ am´ıt´ og´epes programunk, ami egy k m´eret˝ u feladaton a jelenlegi g´ep¨ unk¨on 1 nap alatt fut le. beszerz¨ unk egy sz´ azszor gyorsabb sz´am´ıt´og´epet. Ugyanazon programmal mekkora feladatot lehet az u ´j g´epen egy nap alatt megoldani, ha a program l´ep´essz´ama n m´eret˝ u feladat eset´en (a) n-nel; (b) n3 -bel; (c) 2n -nel ar´ anyos? 3. Papadimitriou 1.4.9. Mutassuk meg, hogy minden p(n) polinomhoz ´es c konstanshoz l´etezik egy n0 eg´esz sz´am u ´gy, hogy n ≥ n0 est´en 2cn ≥ p(n). Hat´arozzuk meg n0 ´ert´ek´et, ha (a) p(n) = n2 ´es 1 . c = 1; (b) ha p(n) = 100n100 ´es c = 100 4. (Papadimitriou 1.4.10. alapj´ an) Legyen f (n) ´es g(n) valamelyik kett˝ o az al´abbi f¨ uggv´enyek k¨oz¨ ul. D¨onts¨ uk el, hogy teljes¨ ul-e (i) f (n) = O(g(n)); (ii) f (n) = Ω(g(n)); (iii) f (n) = Θ(g(n)). a) n2 b) n3 c) 3n2 + 2n d) n2 log n e) 2n
f) 3n g) 2n+1 h) nn i) nlog n n j) 22
n+1
k) 22 2 n l) 2n
ha n p´aratlan, ha n p´aros
Rajzoljuk meg azt az ir´ any´ıtott gr´ afot, melynek cs´ ucsai a felsorolt f¨ uggv´enyek, ´es f -b˝ol g-be pontosan akkor vezet ´el, ha f (n) = O(g(n)). Az ´attekinthet˝os´eg kedv´e´ert hagyjuk el azokat az ´eleket, amelyek a megmarad´ o ´elekb˝ ol az O rel´ aci´ o tranzitivit´asa miatt k¨ovetkeznek. 5.∗ Papadimitriou 1.4.4. (a) Egy ir´ any´ıtott gr´afot k¨ ormentesnek nevez¨ unk, ha nem tartalmaz ir´any´ıtott k¨ort. Mutassuk meg, hogy minden k¨ormentes gr´afban van forr´as (olyan cs´ ucs, melybe nem vezet ´el). (b) Igazoljuk, hogy egy n cs´ ucs´ u gr´ af akkor ´es csak akkor k¨ormentes, ha cs´ ucsai sorsz´amozhat´ok 1-t˝ol n-ig u ´gy, hogy minden ´el kisebb sorsz´am´ u cs´ ucsb´ol nagyobb sorsz´am´ uba mutat (alkalmazzuk ism´etelten az (a) pontban bizony´ıtott tulajdons´agot). (c) Adjunk meg polinom idej˝ u algoritmust, mely eld¨onti, hogy egy adott gr´af k¨ormentes-e. (Val´os´ıtsuk meg a (b) pont alatti ¨ otletet u ´gy, hogy az algoritmus a gr´af minden ´el´enek feldolgoz´as´ara konstans id˝ot ford´ıtson.) 6. P´aros gr´afon egy B = (U, V, E) rendezett h´armast ´ert¨ unk, ahol U = {u1 , . . . un } ´es V = {v1 , . . . vn } egy-egy cs´ ucshalmaz, a fi´ uk illetve l´ anyok halmaza, ´es E ⊆ U × V az ´elek halmaza. A p´aros gr´af egy n elem˝ u M ⊆ E ´elhalmaz´ at teljes p´ aros´ıt´asnak nevezz¨ uk, ha minden (u, v), (u0 , v 0 ) ∈ M ´elp´arra 0 0 0 0 (u, v) 6= (u , v ) eset´en u 6= u ´es v 6= v , azaz M -ben nincs k´et k¨ ul¨onb¨oz˝o ´el, mely ugyanarra a ´ ´ITAS ´ a k¨ovetkez˝o probl´ema: Adott egy p´aros gr´af, fi´ ura vagy l´anyra illeszkedik. Legyen PAROS ´ ´ITAS ´ polinom id˝oben visszavezethet˝o a van-e teljes p´ aros´ıt´ asa? Mutassuk meg, hogy PAROS ´ MAXIMALIS FOLYAM probl´em´ ara.
Bevezet´ es a bonyolults´ agelm´ eletbe gyakorlatok II. 7.∗ Sivatagi-show Elt´evedt¨ unk a sivatagban, mit¨obb az iv´oviz¨ unk is elfogyott, de nagy nehezen kiverg˝odt¨ unk egy kelet-nyugati ir´ any´ u egyenes u ´tra. Biztos, hogy az u ´ton valamelyik ir´anyban x km t´avols´agra tal´ alunk kutat (tegy¨ uk fel, hogy x pozit´ıv eg´esz sz´am). Csak az a probl´ema, hogy sem x-et, sem a megfelel˝ o ir´ anyt nem ismerj¨ uk. Szorult helyzet¨ unkben tervezz¨ unk olyan algoritmust, mely seg´ıts´eg´evel legfeljebb C · x km gyalogl´assal biztosan megtal´aljuk a kutat, ahol C egy pozit´ıv konstans. Mekkora lehet az algoritmusokra C minim´alis ´ert´eke? (Term´eszetesen a legrosszabb esetet figyelembe v´eve.) 8. Papadimitriou 1.4.5. (a) Igazoljuk, hogy egy gr´af akkor ´es csak is akkor p´aros (azaz olyan, hogy cs´ ucsait k´et diszjunkt, de nem felt´etlen¨ ul azonos elemsz´am´ u halmazba sorolhatjuk u ´gy, hogy ¨osszes ´ele az egyik halmazb´ ol a m´ asikba mutat), ha nem tartalmaz p´aratlan hossz´ us´ag´ u ,,ir´any´ıtatlan” k¨ort. (b)Adjunk polinom idej˝ u algoritmust a gr´afok p´aross´ag´anak eld¨ont´es´ere. 9. Adjunk meg olyan Turing-g´epet1 , mely csupa A ´es B bet˝ ut tartalmaz´o szavakon dolgozik, m´egpedig u ´gy, hogy az A bet˝ uket B bet˝ ukre a B-ket pedig A-kra cser´eli. 10. Adjunk meg olyan Turing-g´epet1 , mely az M (x) = tx f¨ uggv´enyt sz´am´ıtja ki, de (ellent´etben az ´orai p´eld´aval) csak egyszer halad v´egig a sz´on. 11. Adjunk meg olyan Turing-g´epet1 , mely a k¨ovetkez˝o f¨ uggv´enyeket val´os´ıtja meg: a) un´aris n¨ ovel´est, azaz M (Ik ) = Ik+1 . b) un´aris ¨ osszead´ ast, azaz M (Ik t Il ) = Ik+l . c) 2-vel val´ o szorz´ ast, azaz M (Ik ) = I2k . d) 2-vel val´ o marad´ekos oszt´ ast, azaz M (Ik ) = Ik
mod 2
.
12. Mutassuk meg, hogy minden M Turing-g´ephez l´etezik olyan, vele ekvivalens (azaz ugyanazt a f¨ uggv´enyt megval´ os´ıt´ o), M 0 Turing-g´ep, mely m˝ uk¨od´es´et mindig a sz´o elej´en, a . karakteren fejezi be. Konstru´aljuk meg M 0 -t a 10. p´elda M Turing-g´epj´ehez. 13. Konstru´aljunk, olyan Turing-g´epet1 , mely a k¨ovetkez˝o nyelveket ismeri fel: a) {ai bj | i < j} b) {w ∈ {a, b}∗ | w-ben ugyanannyi a bet˝ u van mint b} 14.∗ Konstru´aljunk olyan egyszalagos Turing g´epet, mely a szalagj´ara ´ırt {0, 1} feletti szavakat megford´ıtja. P´eld´ aul M (0010111) = 1110100. Beadand´o a Turing-g´ep programja a Binghamtoni Egyetem szimul´ ator programj´ aval 2 futtathat´o f´ajlban lemezen ´es ´ırott form´aban is, valamint a Turing-g´ep m˝ uk¨ od´es´enek r¨ ovid magyar´ azata (Pl. mi az egyes ´allapotok szerepe). 15. Polinom idej˝ u-e az az algoritmus, ami a bemenetk´ent bin´aris ´abr´azol´assal kapott n ´es m term´eszetes sz´amok szorzat´ at u ´gy sz´ am´ıtja ki, hogy az n sz´amhoz m − 1-szer hozz´aadja ¨onmag´at? s := n; for i:= 1 to m − 1 do s := s + n; return s; 16. Bizony´ıtsuk be, hogy az eg´eszek k¨ oz¨ ott v´egzett n´egy alapm˝ uvelet elv´egezhet˝o polinomid˝oben, m´ıg a hatv´anyoz´as nem. 17. Mutassuk meg, hogy a modulo m tekintett hatv´anyoz´as elv´egezhet˝o polinomid˝oben. 18. Konstru´aljunk olyan Turing-g´epet, amely a bin´aris n¨ovel´est teljesen megval´os´ıtja (azaz, akkor is, ha a sz´amjegyek sz´ ama n˝ o), felhaszn´ alva ”szubrutink´ent” az ´or´an mutatott bin´aris n¨ovel´es ´es az el˝oz˝o p´elda ´atalak´ıtott Turing-g´ep´et. 19. Bizony´ıtsuk be (prec´ızen), hogy a Papadimitriou k¨onyv 2.7. p´eld´aj´anak RAM programja val´oban a φ(i1 , i2 ) = i1 · i2 f¨ uggv´enyt sz´ am´ıtja ki. 20. Adjunk egy term´eszetes defin´ıci´ ot mindk´et ir´anyban v´egtelen szalaggal rendelkez˝o (determinisztikus) Turing-g´epekre, azok konfigur´ aci´ oira ´es ´atmenet rel´aci´oj´ara, ´altaluk felismert nyelvekre ´es kisz´am´ıtott f¨ uggv´enyekre. Ekvivalens-e az ´ıgy defini´alt modell a hagyom´anyos Turing-g´ep modellel? Mi´ert? 21. Adjunk meg1 olyan k´etszalagos a) determinisztikus; b) nemdeterminisztikus Turing g´epet, mely a L = {ww | w ∈ {a, b}∗ } nyelvet ismeri fel. (lehet˝oleg min´el kevesebb ´allapot felhaszn´al´as´aval.) 1 Adja meg a Turing g´ ep programj´ at, ´ atmenet diagramj´ at, ´ es r¨ oviden magyar´ azza is el a m˝ uk¨ od´ es´ et, pl. mi az egyes allapotok szerepe ´ 2 A http://www.inf.u-szeged.hu/ zlnemeth/bonyelm.html weblapr´ ol let¨ olthet˝ o.
Bevezet´ es a bonyolults´ agelm´ eletbe gyakorlatok III. 22. Egy 2 × n-es sakkt´ abla mez˝ oin n piros ´es n − 1 k´ek n´egyzetet helyez¨ unk el. Ezeket oly m´odon akarjuk ´atrendezni, hogy a fels˝ o sorban piros, az als´o sorban k´ek n´egyzetek legyenek, s a bal als´o sarok maradjon u ¨res. Ehhez egy-egy l´ep´es sor´an az u ¨res mez˝ore tolhatjuk valamelyik szomsz´edj´at. Bizony´ıtsuk be, hogy ehhez O(n2 ) l´ep´es el´egs´eges ´es Ω(n2 ) l´ep´es sz¨ uks´eges. 23. Milyen konfigur´ aci´ okon megy kereszt¨ ul az al´abbi Turing-g´ep az (s, ., abaa) valamint az (s, ., abab) konfigur´aci´ob´ ol ind´ıtva? Rajzoljuk meg a g´ep ´atmenet diagramj´at ´es ´ırjuk le az ´altal felismert nyelvet. q∈Q s q0 q0 q0 q0 q0 q1 q1 q1 q1 q1 q2 q2 q3 q3 q3 q3 q4 q4 q4 q5 q5 q5 q6 q6 q6 q6 q7 q7 q7 q7 q8 q8 q8 q8 q8
σ∈Σ . a b A B t a b A B t a b a b A B A B . a b t a b B t a b A t a b A B t
δ(q, σ) (q0 , ., →) (q1 , A, →) (q1 , B, →) (q4 , A, ←) (q4 , B, ←) (q0 , t, igen) (q1 , a, →) (q1 , b, →) (q2 , A, ←) (q2 , B, ←) (q2 , t, ←) (q3 , A, ←) (q3 , B, ←) (q3 , a, ←) (q3 , b, ←) (q0 , A, →) (q0 , B, →) (q4 , a, ←) (q4 , b, ←) (q5 , ., →) (q7 , A, →) (q6 , B, →) (q5 , t, igen) (q6 , a, →) (q6 , b, →) (q8 , t, ←) (q6 , t, →) (q7 , a, →) (q7 , b, →) (q8 , t, ←) (q7 , t, →) (q8 , a, ←) (q8 , b, ←) (q5 , A, →) (q5 , B, →) (q8 , t, ←)
24. Adjunk meg esetleg t¨ obb szalagos ´es nemdeterminisztikus Turing g´epeket az al´abbi nyelvek eld¨ont´es´ere a) {xyx | x, y ∈ {a, b}∗ ´es |x| ≥ 1} b) {xy | x, y ∈ {a, b}∗ ´es x-ben ugyanannyi a bet˝ u van mint y-ban} c) {xy | x, y ∈ {a, b}∗ ´es x-ben nem ugyanannyi a bet˝ u van mint y-ban} d) {ai bi cj dj | i 6= j} e) {aba2 b2 a3 b3 . . . an bn | n ≥ 0} 25.* Adjunk egy term´eszetes defin´ıci´ ot k´etdimenzi´os (pl. a k´etdimenzi´os der´eksz¨og˝ u koordin´atarendszer egyik negyed´en dolgoz´ o) determinisztikus Turing-g´epekre, azok konfigur´aci´oira ´es ´atmenet rel´aci´oj´ara, ´altaluk felismert nyelvekre ´es kisz´ am´ıtott f¨ uggv´enyekre. Ekvivalens-e az ´ıgy defini´alt modell a ha´ ıt´asunkat bizony´ıtsuk! gyom´anyos Turing-g´ep modellel? Mi´ert? All´
Bevezet´ es a bonyolults´ agelm´ eletbe gyakorlatok IV. 26. Papadimitriou 3.4.1. alapj´ an ´ Allap´ ıtsuk meg, hogy eld¨ onthet˝ oek-e a k¨ ovetkez˝o probl´em´ak. (Rice t´etel haszn´alata n´elk¨ ul!) Melyek nem rekurz´ıvan felsorolhat´ oak? (a) Adott egy M Turing-g´ep, igaz-e, hogy M meg´all az u ¨res sz´on. (b) Adott egy M Turing-g´ep, van-e olyan bemenet, amelyen M meg´all. (c) Adott egy M Turing-g´ep, l´etezik-e olyan bemenet, hogy, amelyen M valamely l´ep´esben a σ szimb´olumot ´ırja ki. (d) Adott egy M Turing-g´ep, d¨ onts¨ uk el, hogy van-e olyan bemenet, amelyben M valamely l´ep´esben az ´eppen olvasott´ ol k¨ ul¨ onb¨ oz˝ o szimb´ olumot ´ır ki. (e) Adott egy M Turing-g´ep, igaz-e, hogy L(M ) = ∅ (Itt L(M ) az M ´altal felismert ´es nem az ´altala eld¨ont¨ott nyelvet jel¨ oli.) (f) Adott egy M Turing-g´ep, igaz-e, hogy L(M ) v´eges. (g) Adottak az M ´es M 0 Turing-g´epek, d¨ onts¨ uk el, hogy L(M ) = L(M 0 ) teljes¨ ul-e. (h) Adott egy M Turing-g´ep. Igaz-e, hogy van olyan x bemenet, hogy M az x-en ¨ot l´ep´esen bel¨ ul meg´all. (i) Adott egy M Turing-g´ep. Igaz-e, hogy nincs olyan x bemenet, hogy M az x-en ¨ot l´ep´esen bel¨ ul meg´all. 27. A 26. feladat mely pontjainak eld¨ onthetetlens´eg´et tudjuk k¨ozvetlen¨ ul megv´alaszolni a Rice-t´etel seg´ıts´eg´evel? 28. Van-e Post megfelelkez´esi probl´em´ aj´ anak megold´asa a) u1 = 10, u2 = 011, u3 = 101, v1 = 101, v2 = 11, v3 = 011 ´es b) u1 = 1, u2 = 10111, u3 = 10, v1 = 111, v2 = 10, v3 = 0 eset´en? 29. Mutassuk meg, hogy ha a meg´ all´ asi probl´ema eld¨onthet˝o lenne, akkor minden rekurz´ıvan felsorolhat´o nyelv rekurz´ıv lenne. 30. Mutassuk meg, hogy a DOMINO probl´ema komplementere rekurz´ıvan felsorolhat´o, ez´ert (mivel tudjuk hogy a DOMINO probl´ema nem rekurz´ıv), a DOMINO probl´ema m´eg csak nem is re¨ kurz´ıvan felsorolhat´ o. (Otlet: Tegy¨ uk fel, hogy ki van t¨ untetve egy ,,kezd˝odomin´o”, amelynek a ´ mutassuk meg, hogy egy k´eszlettel akkor ´es csak akkor kirak´asban mindenk´eppen szerepelni kell. Es rakhat´o ki a s´ık, ha minden n-re a (2n + 1) × (2n + 1)-es n´egyzet kirakhat´o u ´gy, hogy k¨oz´epen a kezd˝odomin´o van.) 31.* Papadimitriou 3.4.6. Adjunk meg olyan algoritmust, melynek seg´ıts´eg´evel tetsz˝oleges x sz´ohoz ´es tetsz˝oleges, az {x; y : (x, y) ∈ R} nyelvet felismer˝o M Turing-g´ephez (ahol R egy rel´aci´o) megkonstru´alhatunk egy olyan Mx Turing-g´epet, mely az {y : (x, y) ∈ R} nyelvet ismeri fel. 32. Tegy¨ uk fel, hogy L ∈ SP ACE(3 log n). Igaz-e ekkor, hogy L ∈ P ? 33. Bizony´ıtsuk be, hogy a k¨ ovetkez˝ o eld¨ ont´esi probl´ema P -ben van: Adottak az a1 , a2 , . . . , an ´es K eg´eszek. Igaz-e, hogy az a1 , . . . , an elemek medi´anja kisebb mint K? 34. Bizony´ıtsuk be, hogy a k¨ ovetkez˝ o eld¨ ont´esi probl´ema N P -ben van: Adottak egy A n × n-es m´atrix. Igaz-e, hogy det A = 0? 35. Mely al´abbi probl´em´ akr´ ol tudjuk egyszer˝ uen bel´atni, hogy P -ben, illetve N P -ben vannak? (a) Adott egy G gr´ af. P´ aros-e G? (b) Adott eg´esz sz´ amok egy halmaza, ´es egy m´asik K eg´esz sz´am. Van-e a kapott eg´esz sz´amoknak olyan r´eszhalmaza, amelyben a sz´amok ¨osszege ´eppen K? (c) Adott n darab eg´esz sz´ am. Van-e olyan r´eszhalmaz, melyben a sz´amok ¨osszege p´aros? (d) Adott n darab eg´esz sz´ am. Van-e olyan r´eszhalmaz, melyben a sz´amok ¨osszege h´arommal oszthat´o? (e) Adott egy G gr´ af. Van-e G-ben Euler-k¨or? (f) Adott egy G gr´ af ´es egy K eg´esz. Van-e G-ben legal´abb K hossz´ us´ag´ uu ´t? (g) Adott eg´esz sz´ amok egy halmaza. Igaz-e, hogy van k¨oz¨ott¨ uk pr´ımsz´am? (h) Adott eg´esz sz´ amok egy halmaza. Igaz-e, hogy mindegyik¨ uk pr´ım? 36. Mutassuk meg, hogy P ´es N P z´ artak az uni´o- ´es metszetk´epz´esre. 37.* Mutassuk meg, hogy P ´es N P z´ artak a csillag m˝ uveletre, azaz az iter´aci´ora.
Bevezet´ es a bonyolults´ agelm´ eletbe gyakorlatok V.
38. Igaz-e, hogy ha egy C probl´em´ ara a meg´ all´asi probl´ema visszavezethet˝o, akkor co-C nem rekurz´ıvan felsorolhat´o? ¨ a k¨ 39. Legyen 3SATKUL ovetkez˝ o probl´ema: Adott egy ϕ konjunkt´ıv norm´al form´aj´ u, tagonk´ent pontosan h´arom k¨ ul¨ onb¨ oz˝ o v´ altoz´ ot tartalmaz´o formula, d¨onts¨ uk el, hogy kiel´eg´ıthet˝o-e. Mutassuk ¨ N P -teljes. meg, hogy 3SATKUL ´ 40. Legyen SAT LEGFELJEBB HAROMSZOR a k¨ovetkez˝o probl´ema: Adott egy ϕ konjunkt´ıv norm´al form´aj´ u formula, melyben minden v´altoz´o legfeljebb h´aromszor fordul el˝o, d¨onts¨ uk el, hogy ´ kiel´eg´ıthet˝o-e. Mutassuk meg, hogy SAT LEGFELJEBB HAROMSZOR N P -teljes. 41.∗ Papadimitriou 9.5.6. N P -teljes-e SAT azon speci´alis esete, melyben minden tag vagy Horn-tag, vagy csak k´et liter´ alt tartalmaz. 42. Igazoljuk, hogy a 2 sz´ınnel sz´ınezhet˝ o gr´ afok nyelve P -beli. ´ ´ 43. Legyen 3SZINEZES a k¨ ovetkez˝ o probl´ema: Adott egy ir´any´ıtatlan gr´af, kisz´ınezhet˝ok-e a cs´ ucsai legfeljebb h´arom sz´ınnel u ´gy, hogy szomsz´edos cs´ ucsok nem legyenek azonos sz´ın˝ uek. Mutassuk ´ ˝ SAT meg, hogy 3SZ´INEZES N P -teljes. (Felhaszn´alhatjuk, hogy NEM MIND EGYENLO N P -teljes. Papadimitriou 216. o.) 44. Tegy¨ uk fel, hogy van egy T elj´ ar´ asunk, mely b´armely input gr´afra (egyetlen l´ep´esben) megmondja a gr´afban lev˝ o maxim´ alis klikk(ek) m´eret´et. Tervezz¨ unk olyan, a T elj´ar´ast haszn´al´o algoritmust, mely polinom id˝ oben tal´ al egy maxim´ alis klikket az input gr´afban! 45.∗ Tegy¨ uk fel, hogy van egy olyan K nev˝ u elj´ar´as, mely (egyetlen l´ep´esben) megmondja, hogy az inputjak´ent megadott ir´ any´ıtatlan gr´ af sz´ınezhet˝o-e h´arom sz´ınnel. Csin´aljunk egy, a K elj´ar´ast haszn´al´o algoritmust, mely polinom id˝ oben megadja az input G gr´af egy 3-sz´ınez´es´et, ha G ∈ ´ . 3SZ´INEZES ´ a k¨ 46. Legyen LEGHOSSZABB UT ovetkez˝o probl´ema: Adott egy G ir´any´ıtatlan gr´af, ´es egy K eg´esz sz´am. Igaz-e, hogy van G-ben legal´abb K ´elet tartalmaz´o u ´t. Mutassuk meg, hogy LEG´ N P -teljes. HOSSZABB UT ´ ´ IZOMORFIZMUS a k¨ovetkez˝o probl´ema: Adott k´et ir´any´ıtatlan gr´af, G1 47. Legyen RESZGR AF ´ ´ IZO´es G2 . Igaz-e, hogy van G1 -ben G2 -vel izomorf r´eszgr´af. Mutassuk meg, hogy RESZGR AF MORFIZMUS N P -teljes.
