Pługi (omówienie)

15.01.2011

Każdą ulicę trzeba przejechać co najmniej raz. Kiedy więc zużyjemy najmniej paliwa? Wtedy, gdy każdą ulicę przejedziemy DOKŁADNIE jeden raz. Stąd wynika, że zadanie można sformułować następująco: należy rozbić dany graf na najmniejszą możliwą liczbę dróg. Oczywiście każdą spójną składową grafu należy rozpatrywać osobno, w dalszej części zajmiemy się więc grafem z jedną tylko spójną składową.

Czytelnikom niezaznajomionym z pojęciem drogi Eulera polecam ten artykuł http://www.informatyka.wroc.pl/node/142. Znanym faktem jest, że jeśli w grafie spójnym tylko 0 lub 2 wierzchołki mają stopień nieparzysty, to istnieje w nim droga Eulera.

Niech D oznacza szukaną najmniejszą liczbę dróg, jakimi jesteśmy w stanie pokryć dany graf o jednej spójnej składowej. Niech ponadto N oznacza liczbę wierzchołków stopnia nieparzystego w grafie. Jeśli N = 0, to oczywiście D = 1, bo istnieje cykl Eulera. Załóżmy więc, że N > 0.
Rozważmy dowolną ścieżkę. Po jej usunięciu, co najwyżej dwóm wierzchołkom w grafie ( początkowemu i końcowemu ) zmieni się parzystość stopnia. Udowodniliśmy więc, że: D >= N/2.
Z drugiej strony, połączmy N-2 wierzchołki nieparzystego stopnia w pary ( jest to możliwe, bo N jest na pewno parzyste ) i w obrębie każdej pary połączmy wierzchołki sztuczną krawędzią. Każdy z tych N-2 wierzchołków ma teraz parzysty stopień ( bo doszło im po jednej krawędzi ), czyli wierzchołki stopnia nieparzystego są już tylko 2. W tym grafie istnieje już więc droga Eulera. Znajdźmy ją i usuńmy z niej wszystkie N/2 - 1 sztucznych krawędzi. Powstało nam N/2 dróg, które łącznie pokrywają cały graf. Udowodniliśmy więc, że D <= N/2. W połączeniu z poprzednim oszacowaniem daje to równość: D = N/2.

Pozostaje więc umiejętność znajdowania dróg Eulera. Algorytm nie jest trudny i bazuje na przeszukiwaniu w głąb:

drogaEulera(u)
    dla każdej nieodwiedzonej krawędzi (u,v)
        usuń krawędź (u,v)
        drogaEulera(v)
    dołóż u do drogi wynikowej
   
Całe rozwiązanie działa więc w czasie liniowym ze względu na rozmiar wejściowego grafu.

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com