Энгийн чиглэлгүй граф өгөгдөв. Орой бүр дээр тоо бичигдсэн ба нэг раундад орой бүр дээрх тоо түүнтэй холбогдсон оройнууд дээрх тоонуудын нийлбэр болж өөрчлөгднө. K раундын дараах оройнууд дээрх тоог ол.
Граф-н холболтыг илэрхийлэх матриц-г A, орой дээр бичигдсэн тоонуудыг 1*N матриц гэж үзээд B гэе. Нэг раундын дараа B=B*A болно гэдгийг харахад амархан. Тэгвэл К раундын дараа B=B*(A^K) болно. Эндээс гол асуудал нь A^K -г олох юм. A^K зэргийг O(N^3logK) -д олж болох ба энэ хэсгийг уншигч таньд үлдээе.
No comments:
Post a Comment