Błądzenie losowe

11.07.2009 - Marek Szykuła
Trudność

Czasy pokrycia grafów

Jednym z najważniejszych zagadnień dotyczących łańcuchów Markowa jest mierzenie czasu pokrycia grafu. Kiedy znamy czas pokrycia, możemy nim oszacować również czas przejścia z dowolnego miejsca w grafie do dowolnego innego.

Przyjrzyjmy się czasom pokrycia w różnych typach grafów i porównajmy je. Wierzchołki zielone to te jeszcze nie odwiedzone.

Przeglądarka ma wyłączoną obsługę Javy lub Java nie została zainstalowana. Pobierz Javę

Klika - 50 wierzchołków. Wszystkie są ze sobą połączone, co daje maksymalną swobodę podróżowania. Średni czas pokrycia wynosi ok. 220.

Przeglądarka ma wyłączoną obsługę Javy lub Java nie została zainstalowana. Pobierz Javę

Linia - 50 wierzchołków. Piłeczka często zmienia kierunek, co utrudnia przejście od końca do końca. Średni czas pokrycia wynosi ok. 2900.

Przeglądarka ma wyłączoną obsługę Javy lub Java nie została zainstalowana. Pobierz Javę

Lizak - klika i linia połączone razem - 50 wierzchołków. Zauważmy, że wydostanie się z kliki jest bardzo trudne (ucieczka prowadzi tylko przez jeden wierzchołek). Tutaj ma duże znaczenie również miejsce gdzie zaczynamy: jeśli w linii to średni czas pokrycia wynosi ok. 420, jeśli w klice to ponad 17500 !

Możesz sprawdzić swoje zdolności jasnowidzenia, zgadując jakie czasy pokrycia mają inne grafy:

Gra w przewidywanie


Artykuł i aplety - Marek Szykuła

Obrazek tytułowy - Marcin Południak

4.875
Twoja ocena: Brak Ocena: 4.9 (8 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com