Úloha č.4, Řešitelský seminář
k odevzdání 23.3.2010
Příklad . Nechť G = (V, H) je acyklický orientovaný graf. Dokažte, že rekurzivní
předpis
* g(v) = 0, je-li v list
* g(u) = mex{g(v)|(u, v)  H}
splňuje jediná funkce g : V  N.
List je vrchol v acyklickém grafu, jehož výstupní stupeň je 0 (nevede z
něj žádná hrana). Funkce mex udává pro každou vlastní podmnožinu V  N
nejmenší přirozené číslo, které není ve V obsaženo. Přirozená čísla uvažujeme
včetně nuly.
1