Algoritmuselmélet pótgyakorlat az ötödik gyakorlathoz 1. Adott egy G egyszerű irányított gráf éllistával, nemnegatív élsúlyokkal. Legyen v1 egy tetszőleges csúcsa G-nek. Adjunk minél hatékonyabb módszert a v1-hez legközelebbi 100 csúcs megtalálására! 2. Adjunk algoritmust, mely egy éllistával megadott irányítatlan gráfban vagy talál egy kört, vagy igazolja a gráf körmentességét O(|V|) időben (függetlenül attól, hogy |E| akár sokkal nagyobb is lehet, mint |V|)! 3. Legyen adva egy (egyszerű, irányítatlan, öszefüggő) n pontú G gráf éllistával, az élek súlyozásával együtt. Tegyük fel, hogy a G-ből a v1 csúcs, valamint a v1-re illeszkedő élek elhagyásával keletkező $G^\prime$ gráf még mindig összefüggő, és adott $G^\prime$ egy minimális költségű feszítőfája. Adjunk minél hatékonyabb algoritmust a G gráf egy minimális költségű feszítőfájának az elkészítésére! (Teljes értékű megoldás: $O(n\log n)$ idejű algoritmus.) 4. Adott egy egyszerű irányítatlan G=(V,E) gráf. Szeretnénk a csúcsokat két osztályba sorolni úgy, hogy a gráf éleinek legalább a fele különböző osztályú pontokat kössön össze. (Tehát olyan $V_1, V_2\subseteq V$ csúcshalmazokat szeretnénk kijelölni, melyekre $V_1\cap V_2=\emptyset$, $V_1\cup V_2=V$, és $\vert\{(u,v)\in E\vert u\in V_1, v\in V_2\}\vert\geq \vert E\vert/2$.) Adjunk e feladat megoldására O(|V|2) futási idejű algoritmust! Megoldások