Anonymní profil Wolda – Programujte.com

Jen par poznamek k tomu, co se tu pise:

1) jakpak se da Dijkstrovym algoritmem hledat NEJDELSI cesta? Tvrdim, ze jakakoli modifikace Dijkstry bud nebude hledat nejdelsi cestu nebo bude spatne :-).
PS: kdyby se umela nejdelsi cesta (nikoli sled) v grafu hledat jakymkoli rozumnym zpusobem, asi by pak nebyl problem odpovedet, zda graf obsahuje Hamiltonovskou cestu (tj. cestu prochazejici vsemi vrcholy) a to je notoricky znamy NP-uplny problem (lze s vcelku velkou pravdepodobnosti prelozit jako algoritmicky slozity problem).

2) prumerem grafu byva oznacovana nejdelsi z nejkratsich cest mezi libovolnymi dvema vrcholy; polomerem se oznacuje:
pro kazdy vrchol si vezmeme nejdelsi z nejkratsich cest do ostatnich vrcholu a z nich vezmeme tu nejkratsi :-), neboli min_v {max_u {d(u,v}} kde min_v znaci minimum pres vsechny vrcholy v grafu, max_u maximum pres vsechny vrcholy u a d(u,v) je delka nejkratsi cesty mezi u a v.

3) jestli ty grafy maji byt navzajem neizomorfni, tak ten napad s permutovanim je dle meho nazoru dost mimo (nejak jsem nemel silu premyslet nad tim, jak presne mel fungovat, ale obecne si myslim, ze zkouset libovolne umistovat hrany izomorfismu nezabranuje).

4) myslim si, ze at uz je graf rovinny nebo neni, rozhodne to neni snadne ... A pokud nerovinnost grafu ulohu nejak usnadnuje, pak by me vazne zajimalo jak :-).