Matematické Fórum

Mám za úkol vymyslet algoritmus pro spočítání celkového počtu cest v acyklickém orientovaném grafu. Našel jsem si i nejspíše správné řešení (je tam i zadání):http://hscc.cs.nthu.edu.tw/~sheujp/lect … l/hw16.pdf

Tady je obrázek, na kterém si to zkouším:


Ale trochu v tom tápu, tak bych si chtěl jen některé věci doplnit. Pokud to správně chápu, tak B(v) je číslo udávající počet orientovaných cest, které začínají ve v. Je to tak nebo se to česky říká jinak?

Z příkladu bych si třeba mohl vzít vrchol t, u kterého je číslo 8, a chápu to správně, že je to spočítáno jakože si vycházím z bodu t a jdu všemi možnými směry a zkouším všechny možné cesty, které z t vychází (spočítám si kolik je na cestě hran) a nakonec přičtu ještě 1? Výpočet: tz: 1 hrana + tyz: 2 hrany + txyz: 3 hrany + txz: 2 hrany (ovšem protože, když je to společná s txyz, tak se znovu nepřičítá? tedy jenom 1 hrana) = 7 a k tomu tedy přičtu ještě 1 za prázdnou cestu.   

D(v) vlastně ani nevím, jak spočítat. V tom algoritmu je to napsáno jako počet orientovaných cest po v v topologickém pořadí, ale dost dobře si nedovedu představit co to znamená.

Nakonec by mě zajímalo co vlastně dostanu za výsledek. Vím, že by to měl být ten celkový počet cest, ale bude to podle mě celkem velké číslo a co přesně znamená? Znamená to, že například v mém obrázku pro D(r) (vrchol úplně vlevo) tam budou všechny cesty a to ještě i třeba jenom cesta st nebo musí začínat v r? Tedy rs, rst apod.?