Algoritmuselmélet - Vizsga, 2013.06.06.

2013.06.06. vizsga megoldásai

1. Feladat

Ebben a feladatban a mélységi bejárással kapcsolatos kérdésekre kell válaszolni.

• (a) Adja meg a keresztél definícióját!
• (b) A mélységi bejárás során hogyan lehet a mélységi és a befejezési számok alapján felismerni a keresztéleket?
• (c) Bizonyítsa be, hogy irányítatlan gráf mélységi bejárásánál nincsenek keresztélek!

Megoldás

(a)
Tekintsük a G irányított gráf egy mélységi bejárását és a kapott T mélységi feszítő erdőt. Ezen bejárás szerint G egy x → y éle keresztél, ha x és y nem leszármazottjai egymásnak.

(b)
msz - mélységi szám
bsz - befejezési szám
Ha $(msz[y]<msz[x])$ és $(bsz[y]>0)$, akkor az x → y egy keresztél.
Fájl:Keresztel 1.png
(c)
A b) rész alapján könnyen belátható. Ha lenne keresztél, az azt jelentené, hogy van olyan x → y él, amire fennáll, hogy $(msz[y]<msz[x])$ és $(bsz[y]>0)$, vagyis y-ban előbb jártunk, mint x-ben, és y-nak van befejezési száma. Ennél fogva nem lehet keresztél, hiszen ha lenne, akkor y-ból eljuthattunk volna még x-be, mielőtt befejeztük volna. Másképpen mondva: Nem fejezhettük volna be y-t anélkül, hogy ne jártunk volna x-ben.

Fájl:Keresztel 2.PNG

2. Feladat

TODO

3. Feladat

TODO

4. Feladat

TODO

5. Feladat

TODO

6. Feladat

TODO

7. Feladat

TODO

8. Feladat

TODO