„Algoritmuselmélet - ZH, 2013.04.03.” változatai közötti eltérés
| 113. sor: | 113. sor: | ||
}} | }} | ||
===8. Feladat=== | ===8. Feladat (Van megoldás)=== | ||
'''(a)''' Igaz-e, hogy egy piros-fekete fa tetszőleges belső fekete csúcshoz tartozó részfa (az a részfa, aminek ez a fekete csúcs a gyökere) is egy piros-fekete fa? | |||
'''(b)''' Igaz-e ugyanez egy tetszőleges belső piros csúcshoz tartozó részfára? | |||
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
{{Rejtett | |||
|mutatott=<big>''Megjegyzések a feladathoz''</big> | |||
|szöveg= | |||
*Avagy mitől is piros-fekete egy piros-fekete fa? | |||
#Minden nem levél csúcsnak 2 fia van. | |||
#Elemeket belső csúcsban tárolunk. | |||
#teljesül a keresőfa tulajdonság. | |||
#A fa minden csúcsa piros, vagy fekete. | |||
#A gyökér fekete. | |||
#A levelek feketék. | |||
#Minden piros csúcs mindkét gyereke fekete. | |||
#Minden ''v'' csúcsra igaz, hogy az összes ''v''-ből levélbe vezető úton ugyanannyi fekete csúcs van (~fekete magasság). | |||
}} | |||
'''a)''' Igaz-e, hogy egy piros-fekete fa tetszőleges belső fekete csúcshoz tartozó részfa (az a részfa, aminek ez a fekete csúcs a gyökere) is egy piros-fekete fa? | |||
*Igaz. ''(Nem tudom, mennyi magyarázatot, vagy milyen indoklást várnak ide, de a piros-fekete tulajdonságai közül talán csak a fekete magasság szorul magyarázatra (...), a többi elég triviális.)'' | |||
**Ha a részgráfra nem állna fenn a fekete magasság kritériuma, akkor pláne nem fog a teljes gráfra teljesülni, hiszen hiába jó a fekete magasság a pontig, ha a pont tönkre teszi azt :/. | |||
'''b)''' Igaz-e ugyanez egy tetszőleges belső piros csúcshoz tartozó részfára? | |||
*Nem. A gyökérnek feketének kell lennie. | |||
}} | }} | ||