Berek (omówienie)

14.12.2011

Zadanie było klasycznym problemem z zakresu teorii grafów. W tym wypadku rozważanym grafem jest podwórko na którym dziewczynki grały w berka - jego wierzchołkami są zakątki, a krawędziami - przejścia.

W postawionym problemie wyróżniono dwa wierzchołki grafu - wierzchołek $ J $ to ten, w którym znajduje się Joasia, a $ K $ to wierzchołek w którym znajduje się Kornelia. Znając strukturę grafu należy odpowiedzieć jak długo Joasia może uciekać przed Kornelią zanim zostanie złapana, jeśli każda dziewczynka może przejść co najwyżej jedną krawędź na turę

Kluczową informacją zawartą w treści zadania jest liczba krawędzi grafu - na podwórku znajduje się o jeden więcej zakątków, niż przejść; a przy tym wiadomo, że z każdego zakątka można dojść do każdego innego. Takie grafy są bardzo specyficzne - okazuje się, że graf spełniający te warunki nigdy nie zawiera cyklu, tj. z każdego zakątka do dowolnego innego prowadzi jedna i tylko jedna droga. Grafy tego rodzaju nazywamy drzewami.

Wiele problemów które trudno rozwiązać dla dowolnych grafów staje się prostsze (trochę prostsze lub znacznie prostsze) kiedy ograniczymy się do drzew i tak jest w tym przypadku.

Przede wszystkim zauważmy, że niezależnie od struktury podwórka i rozmieszczenia wierzchołków, Kornelia na pewno prędzej czy później złapie Joasię - dlatego, że w każdej turze będzie zwiększać się liczba wierzchołków, do których jedyna droga z aktualnego wierzchołka Joasia prowadzi przez wierzchołek Kornelii.

Zastanówmy się jakie warunki musi spełniać optymalny z punktu widzenia Joasi wierzchołek końcowy (ten, w którym Kornelia łapie Joasię i gra się kończy), który oznaczymy $ x $. Przede wszystkim - odległość pomiędzy $ x $ a $ J $ musi być mniejsza niż pomiędzy $ x $ a $ K $, co gwarantuje, że Joasia pierwsza do niego dotrze (i nie zostanie złapana po drodze - zauważmy, że gdyby Kornelia dotarła pierwsza do dowolnego odcinka na drodze do $ x $, mogłaby też dotrzeć pierwsza do $ x $). Poza tym, powinien być to najbardziej odległy od $ K $ wierzchołek spośród wszystkich spełniających ten warunek (co zagwarantuje możliwe długą zabawę).

Tak więc dla rozwiązania tego zadania należało obliczyć odległości pomiędzy wierzchołkiem $ J $ a wszystkimi wierzchołkami i grafu oraz pomiędzy wierzchołkiem $ K $ i wszystkimi wierzchołkami grafu; a na końcu wybrać wierzchołek zgodnie z opisem z poprzedniego akapitu.

Organizatorzy:

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com