„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés
| 17. sor: | 17. sor: | ||
[[Fájl:keresztel_1.png]]<br> | [[Fájl:keresztel_1.png]]<br> | ||
'''c)'''<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.<br> | ||
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> | ||
}} | }} | ||