---
# System prepended metadata

title: Domácí úkol 5.3 - nejdelsi

---

# Domácí úkol 5.3 - nejdelsi
(Délkou cesty rozumím počet vrcholů, nikoli počet hran)
Předpokládáme, že v grafu existují dvě nejdelší cesty ($P_x$ $\geq$ $P_y$) bez společného vrcholu. Pak rozdíl jejich délek může být nanejvýš 1 (jinak by druhou nejdelší cestou byla podcesta oné delší cesty bez jednoho krajního vrcholu). 
Aby graf byl spojitý, pak musí existovat cesta z některého vrcholu cesty $P_x$ do vrcholu cesty $P_y$. Těmito vrcholy rozdělíme cesty na čtyři části, které mají délky $[n; (x-n+1)], [m; (y-m+1)]$ (ono "$+1$" znamená, že rozdělovací/spojovací vrchol je součástí obou podcest). 
V krajním případě$*$ nyní předpokládejme, že mezi oněmi spojovacími vrcholy není žádný jiný vrchol.
Tím mohu vytvořit novou nejdelší cestu $P_z$ tak, že vyberu delší cestu z první i druhé dvojice a propojím je přes hranu $v_nv_m$$*$ . Je-li cesta $P_x$ rozdělena na dvě části, pak delší má velikost alespoň $x//2 + 1$, takže dohromady obě "větší poloviny" mají velikost alespoň $x+1$ ($y$ může být rovno pouze $x$ nebo $x-1$, viz první odstavec).
Tím jsme nalezli novou nejdelší cestu, a druhou nejdelší cestou se tak "stává" $P_x$. A jak jsme zmínili, na cestě $P_x$ se musí nacházet spojovací vrchol, který bude oběma cestám společný.
$*$ Je vidět, že další vrcholy na cestě mezi $v_n$ a $v_m$ zvýší pouze délku cesty $P_z$, což pouze posiluje tvrzení, že $z > x$.