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 …”)
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 és , 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 és , 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.
