10. feladatsor megoldása (vázlat)

1. Ha G-ben van H-út, akkor G éleit sorba rendezve minden él elhagyása esetén
teszteljük, hogy megmarad-e a H-út, de persze ha az elhagyott él nélkül nincs
H-út, akkor visszatesszük, egyébként végleg elhagyjuk. Ezt minden élre
elvégezve nyilván H-utat tartalmazó részgráfot kapunk. Azon kívül más él nem
is lehet a maradékban, hiszen annak tesztelése után a szóban forgó élt végleg
el kellett volna hagyni.

2. Éppen azt kell ellenőrizni, hogy G komplementere páros gráf-e, ami
szélességi kereséssel P ellenőrizhető.

3. G-hez 99 db olyan komponenst veszünk hozzá, amik lefedéséhez egy-egy kör
szükséges (pl. 99 db diszjunkt kört). Erre futtatva az algoritmust eldönthető,
hogy G lefedhető-e körrel, vagyis van-e H-köre.

4. NP trivi. Mivel bármely F fának legfeljebb n-2 páros fokú pontja van (két
elsőfokú), ezért ha az algoritmusnak G-t és n-2-t adva megkapjuk, hogy van-e
G-nek olyan feszítőfája, amiben pont két elsőfokú pont van, ez viszont H-út.
A probléma tehát NP-teljes.

5. (a) 77 (b) 7 az eukl. algoritmussal.

6. Kibőv. eukl. alg. x=17+5k, y=-34-3k.

7. Lehetséges párok: (12, 240), (48, 60), (60, 48), (240, 12)

8. Esetvizsgálattal: 3 osztójúak: 4, 9, 25, 49; 9 osztójúak: 36, 100.

9. A szám osztóinak egyes prímkitevői lehetnek: 2-re 1,..,5; 3-ra 0,..,9;
5-re 1,..5; 7-re 0,..,3. Összesen 5*10*5*4=1000.

10. Ha létezne ilyen k, akkor a rekurzió miatt F(k+1) is osztható lenne 3-mal.
Ugyancsak a rekurziót használva F(k-1), majd ezt folytatva F(k-2),... stb.
mind osztható 3-mal, ebből viszont F(1) osztható 3-mal következne, ami
ellentmondás, tehát nincs ilyen k.