Najdlhsia cesta v strome - algoritmus

Hloupý algoritmus - spočítáš si cestu z každého vrcholu do každého a vybereš nejdelší - poběží v O(n^2)
Chytrý algoritmus:
1) zvolíš libovolný vrchol v stupně 1
2) najdeš nejvzdálenější vrchol k tomuto, označmě w - o tom tvrdím, že leží na konci nejdelší cesty.
3) najdeš nejvzdálenější vrchol z vrcholu w - máš nejdelší cestu.

nejsem si teď 100% jistý protože nemůžu vypotit důkaz, ale myslím, že to bylo takhle. Běží to pak samozřejmě v O(n).

Jo. Už možná vím. Představ si že BÚNO v je kořen a w je uzel na nejnižší hladině. Sporem pokud by existovala cesta, která nezahrnuje uzel w na nejnižší hladině, lze jí prodloužit právě tak, že v tom podstromě, že kratší konec té cesty vyměním za w - blbě se to říká slovy, lépe by se to dokazoval o obrázkem, ale třeba ti aspoň tohle pomůže

AM:
Edit: To jsem teda napsal pitomost. Zbytek příspěvku ignorujte.

To by ale fungovalo, pokud je propojený každý vrchol s každým, tady se mluví o stromu.
Jestli jsem ten algoritmus správně pochopil, tak když bude strom:
- tak to jako nejdelší vybere A-E-G a ne správnou A-B-C-D

Navíc procházení všech větví stromu myslím nebude O(n^2), ale O(n).

Joker: Nejdelší cesta podle AM_ je IMHO G-E-A-B-C-D (nebo naopak).
1) Vybereš libovolný vrchol stupně 1 - já vyberu třeba F
2) Najdeš nejvzdálenější vrchol k tomuto - to je bez pochyb D
3) Najdeš nejvzdálenější vrchol z vrcholu D - to je G

A pak jen vypíšeš cestu mezi nimi...

Joker:
„Navíc procházení všech větví stromu myslím nebude O(n^2), ale O(n).“
pokud počítáme každý s každým, je to jistě asymptoticky O(n^2) - je to n*(n-1).

„To by ale fungovalo, pokud je propojený každý vrchol s každým, tady se mluví o stromu.“
no, ale ve stromu je propojen každý vrchol s každým :) (tedy ne hranou, ale cestou. Pokud by byl každý vrchol propojený s každým hranou, je to úplný graf, a tam by nejdelší cesta ani moc neměla smysl - ostatně ona má smysl jedině na stromě).

„tak to jako nejdelší vybere A-E-G a ne správnou A-B-C-D“
nejdelší cesta ve stromě je mezi dvěma libovolnými vrcholy, nikoli mezi kořenem a vrcholem (to by byla triviální úloha na prohledávání grafu). Obecný strom je jakýkoli 1souvislý graf s n-1 hranami, nemá definovaný kořen, a ze zadání peter4545 nevyplývá, že by šlo o zakořeněný strom. Ono každý strom zakořenit lze (to jsem také zmínil ve svém nástřelu důkazu, protože po vybrání kořene se to lépe ukazuje, ale jako kořen lze zvolit libovolný vrchol stupně <=2 a to není součástí zadání).

Marek88, AM:
Jasně, máte pravdu. Na mou obhajobu, bylo to psáno na konci poměrně vyčerpávajícího víkendu :-)

AM:
„pokud počítáme každý s každým“
Každý s každým ano, ale právě na projití všech větví stromu není potřeba počítat každého s každým.
Mám-li kořen, stačí jít „od kořenu dolů“, jinak vyjít z koncových vrcholů (= stupně 1)

Joker:
„Mám-li kořen, stačí jít ‚od kořenu dolů‘, jinak vyjít z koncových vrcholů (= stupně 1)“
a) to, jestli strom má nebo nemá kořen (neboli jestli nějaký vrchol označíme jako kořen), je pro tuto úlohu úplně jedno - s nejdelší cestou to nijak nesouvisí
b) není mi jasné, jak by ten hloupý algoritmus prošel každou větev jen jednou. Tam už je potřeba vymyslet nějaký sofistikovanější než hledání maxima hrubou silou, a u toho jsem napsal, že ten už je O(n).