Górskie szlaki

04.06.2009
Trudność

Zadanie to okazało się najprostszym w rundzie drugiej. Jednak choć większość zawodników dostrzegła poprawne rozwiązanie, nie wszyscy zadali sobie dodatkowy trud udowodnienia jego poprawności.

Na wejściu dane było drzewo. Należało wyznaczyć minimalną liczbę ścieżek, która wystarzcza do pokrycia tego drzewa. Odpowiedzią okazała się być ilość liści podzielona przez dwa i zaokrąglona do góry.

Najpierw pokażmy, że taka ilość ścieżek jest niezbędna do pokrycia drzewa (tzn. że mniejszą ilością pokryć się nie da). Oczywiście liście, jako składniki drzewa, muszą zostać pokryte ścieżkami. Ponieważ z liścia wychodzi tylko jedna krawędź, aby pokryć go, ścieżka musi się w nim zaczynać, bądź kończyć. Stąd bierze się minimalna ilość ścieżek.

Teraz pokażmy, że ilość ta zawsze wystarcza do pokrycia całego drzewa. Połączmy liście w pary i poprowadźmy ścieżki. Jeżeli drzewo nie jest pokryte, to znaczy, że istnieje jakaś ścieżka (ciąg krawędzi, oznaczmy go X), która nie jest pokryta. Końce tej ścieżki (wierzchołki, oznaczmy je A, B) muszą być pokryte (w przeciwnym wypadku możemy wydłużyć ścieżkę X). Podzielmy ścieżkę przechodzącą przez A wierzchołkiem A na fragmenty A1, A2, podobnie ścieżkę pokrywającą B podzielmy na B1, B2. Teraz zamiast ścieżek A1,A2 oraz B1,B2 poprowadźmy ścieżki A1,X,B2 oraz A2,X,B1. Po tej operacji dotychczas niepokryta ścieżka X jest pokryta, a cała reszta drzewa jest pokryta tak, jak była. Zatem pokrycie drzewa zwiększyło się. Operacje tą powtarzamy do skutku (tzn. aż do pokrycia całego drzewa)

Wiktor Janas

4
Twoja ocena: Brak Ocena: 4 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com