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źć?
Błądzenie losowe
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij