Błądzenie losowe

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
bofort
Witam na forum
Witam na forum
Posty: 1
Rejestracja: 29 maja 2019, 07:39
Płeć:

Błądzenie losowe

Post autor: bofort » 29 maja 2019, 07:45

Cześć,

mam problem z następującym zadaniem:
"Mysz i kot błądzą klasycznie (i niezależnie) na tym samym spójnym grafie 8-regularnym o 20 wierzchołkach.
Na początku znajdują się w niesąsiednich wierzchołkach. Gdy znajdą się w tym samym wierzchołku, kot zjada mysz.
Uzasadnij, że oczekiwana liczba kroków, po których mysz zostanie zjedzona, jest mniejsza niż 625 · 2^15."

Wiem, że można użyć twierdzenia o średnim czasie pokrycia dla błądzenia po grafie, a wynosi ono 2*e(G)*v(G).
Dodatkowo wiem, że ten czas powinien być mniejszy od 8*(e(G)^2)*(v(G)^2).

Czy ktoś ma jakiś pomysł jak to ugryźć?