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.