Czy g musi mieć cykl Eulera Kasia_95: Hej wszystkim! 1. G−pewien graf nieskierowany. Wiemy, że jego graf krawędziowy L(g) ma cykl Hamiltona. Czy G musi mieć cykl Eulera? Uzasadnij. 2. G−pewien graf skierowany. Wiemy, że G ma drogę Eulera. Czy jego graf pochodny musi mieć drogę Hamiltona? Podaj pełne uzasadnienie. Dziękuję

po prostu Michał: Nie wiem co to graf krawedziowy ani pochodny, jednakze zeby miec w grafie skierowanym Eulera to wystarczy 1) spojnosc 2) ilosc krawedzi wchodzacych do wierzcholka = ilosci krawedzi wychodzacych natomiast w nieskierowanym 1) spojnosc 2) wierzcholek parzystego stopnia co do Hamiltona to nie wiadomo za bardzo, w sensie 1) spojny (musi byc) 2) jesli dodatkowo jest, ze dla kazdego v, deg(v) > 1/2n (to wtedy na 100% jest hamilton) a tak to wlasciwie mozna szukac i szukac i nie znalezc. Problem NP zupelny