Algoritmuselmélet - Vizsga, 2013.06.06.

A VIK Wikiből
A lap korábbi változatát látod, amilyen Arklur (vitalap | szerkesztései) 2013. június 7., 15:57-kor történt szerkesztése után volt. (Új oldal, tartalma: „==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 …”)
(eltér) ← Régebbi változat | Aktuális változat (eltér) | Újabb változat→ (eltér)
Ugrás a navigációhoz Ugrás a kereséshez

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 [math] (msz[y] \lt msz[x]) [/math] és [math](bsz[y] \gt 0) [/math], 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 [math] (msz[y] \lt msz[x]) [/math] és [math](bsz[y] \gt 0) [/math], 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