„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés
| 8. sor: | 8. sor: | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
''' | '''a)'''<br> | ||
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. | 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)'''<br> | ||
msz - mélységi szám<br> | msz - mélységi szám<br> | ||
bsz - befejezési szám<br> | bsz - befejezési szám<br> | ||
Ha <math> (msz[y] < msz[x]) </math> és <math>(bsz[y] > 0) </math>, akkor az x → y egy keresztél.<br> | Ha <math> (msz[y] < msz[x]) </math> és <math>(bsz[y] > 0) </math>, akkor az x → y egy keresztél.<br> | ||
[[Fájl:keresztel_1.png]]<br> | [[Fájl:keresztel_1.png]]<br> | ||
''' | '''c)'''<br> | ||
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] < msz[x]) </math> és <math>(bsz[y] > 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. | 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] < msz[x]) </math> és <math>(bsz[y] > 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.<br> | Másképpen mondva: Nem fejezhettük volna be y-t anélkül, hogy ne jártunk volna x-ben.<br> | ||
[[Fájl:keresztel_2.PNG]]<br> | [[Fájl:keresztel_2.PNG]]<br> | ||