Cykl Eulera cz II.

Cyklem Eulera w grafie nazywamy następujące obejście grafu:

- zaczynamy w wybranym przez nas wierzchołku
- obchodzimy graf w ten sposób, że każdą krawędź przechodzimy dokładnie raz
- kończymy na wierzchołku w którym zaczęliśmy.

Jakie warunki musi spełniać graf aby istniał w nim cykl Eulera? Graf przede wszystkim musi być spójny. Jeśli by nie był mogłaby istnieć krawędź do której nie możemy dojść. Ponadto za każdym razem gdy wchodzimy do jakiegoś wierzchołka musimy umieć z niego wyjść. Zatem stopień każdego wierzchołka musi być wielokrotnością dwójki.

Okazuje się, że jeśli graf spełnia te dwa warunki to istnieje w nim cykl Eulera (dowód przez podanie algorytmu Fleury'ego będzie przedstawiony w którejś z kolejnych notek).

Zadanie z winniczkiem wydaje się teraz banalne. Spójność grafu mamy dane w treści zadania. Ponadto każdą krawędź w tym grafie musimy przejść dwukrotnie (ścieżki są dwa razy szersze od kosiarki) - zatem spełniony jest również drugi warunek. Zatem w grafie istnieje cykl Eulera. Ponieważ w zadaniu nie proszą nas o znalezienie tego cyklu, a jedynie o podanie w jakim czasie Winicjusz jest w stanie przejść ten graf, więc odpowiadamy: suma wag na krawędziach przemnożona przez dwa.

Cykl Eulera cz I.

Oto zadanie, które musiał rozwiązać w miniony weekend. Zadanie wygląda na bardzo trudne, ale z odrobiną teorii okazuje się banalne.

Jak wszyscy dobrze wiemy, w soboty nie chodzi się do szkoły. Każde dziecko bardzo się z tego powodu cieszy i winniczek Winicjusz nie stanowi pod tym względem wyjątku. Niestety rodzice zaplanowali już, że w sobotę odbędzie się wielkie koszenie trawy w parku przed domem. Ponieważ dawno nikt tego nie robił, park strasznie zarósł i cała rodzina uznała, że nie starczy weekendu, aby doprowadzić go do ładu. Postanowili zatem, że skoszą jedynie trawę rosnącą na ścieżkach.

Przydomowy park jest bardzo typowy. Poprzecinany jest siecią alejek, które spotykają się ze sobą na ponumerowanych skrzyżowaniach. Ponieważ parki zazwyczaj służą do spacerowania, z dowolnego skrzyżowania można dojść na dowolne inne.

Ponieważ przyjaciele Winicjusza chcą wyciągnąć go wieczorem na pizzę, winniczek chciałby wiedzieć, ile czasu zajmie mu koszenie trawy. Kosiarka podczas koszenia porusza się z prędkością 1m/s oraz 2m/s, gdy jedzie po skoszonej trawie, a szerokość alejki jest dwa razy większa niż szerokość kosiarki.