به دست آوردن توابع بازگشتی به کمک گراف و ماتریس

مساله به دست آوردن تعداد گشت های به طول k در یک گراف مساله ای است که بسیاری از مسائل شمارشی را می توان حالت خاصی از آن حساب کرد و چون زمان محاسبه این تعداد متناسب با لگاریتم k است، در بسیاری از موارد از الگوریتم های دیگر سریع تر عمل می کند و می توان به جای راه های دیگر از توان رساندن ماتریس این گراف استفاده کرد.

در این بخش خانواده هایی از توابع بازگشتی که در مسائل تئوری و همچنین برنامه نویسی پویا دیده می شوند را در نظر می گیریم و برای آن ها گراف هایی می سازیم که جمله n ام رابطه بازگشتی مورد نظر برابر تعداد گشت های به طول n در گرافی باشد که تعداد ثابتی راس دارد. به این ترتیب الگوریتمی به دست می آید که پیچیدگی آن \(O(lg(n))\) است و دنباله بازگشتی مورد نظر را حساب می کند.

فیبوناچی

یک گراف دو راسی را در نظر بگیرید که در آن دو راس به هم یال دارند و راس اول به خودش یک طوقه دارد. می خواهیم تعداد گشت های به طول n از راس یک به خودش را محاسبه کنیم و این مقدار را \(f_n\) می نامیم. روی اولین یال گشت حالت بندی می کنیم. اگر اولین یال گشت آن طوقه باشد، در ادامه طبق تعریف به \(f_{n-1}\) طریق می توانیم کار را ادامه دهیم. اما اگر در اولین قدم به راس دیگر رفته باشیم، دومین یال گشت به صورت یکتا معلوم است و مجبوریم که به راس اول برگردیم. در ادامه به \(f_{n-2}\) طریق می توانیم کار را ادامه دهیم. پس داریم:

\[f_n = f_{n-1} + f_{n-2}\]

و تعداد گشت های ۰ یالی و ۱ یالی از راس یک به خودش برابر ۱ است و بنابراین دنباله f همان دنباله فیبوناچی معروف است. پس اگر بخواهیم عدد n ام در دنباله فیبوناچی را حساب کنیم می توانیم ماتریس مجاورت این گراف را به توان برسانیم. یعنی درایه ۱ و ۱ ماتریس \(\begin{bmatrix}1 & 1\\1 & 0\end{bmatrix} ^ n\) همان فیبوناچی n ام است.

تبدیل ها

نیازی نیست که برای هر رابطه بازگشتی بیاییم و از ابتدا یک گراف بسازیم، بلکه می توانیم تبدیل های کلی ای پیدا کنیم و گراف را طوری تغییر دهیم که الگوی خاصی از توابع را شامل شود. برای مثال در ادامه تبدیل جمع جزیی آمده است.

فرض کنید گرافی داریم که در آن تعداد گشت های به طول n آن از راس i به j برابر \(f_n\) است. دنباله g را به صورت زیر تعریف می کنیم.

\[g_0 = 0\]
\[g_n = g_{n-1} + f_{n-1}\]

می خواهیم گراف را به طوری تغییر دهیم که بتوان با آن دنباله بالا را محاسبه کرد. به گراف یک راس جدید مانند k اضافه می کنیم و یک یال از راس j به k اضافه می کنیم و یک طوقه نیز روی راس جدید می گذاریم. تعداد گشت های از راس i به j تغییری نمی کند و همان حالت قبل می ماند. ادعا می کنیم که تعداد گشت های به طول n از i به k همان مقدار خواسته شده است. ابتدا واضح است که پایه برقرار است و هیچ گشت ۰ یالی از i به k وجود ندارد. برای اثبات قسمت دوم روی یال آخر گشت حالت بندی می کنیم. یا یال آخر گشت همان یال طوقه است که ابتدای گشت \(g_{n-1}\) حالت دارد و یا یالی است که از راس j به k وارد شده است که در این حالت طبق فرض ابتدای گشت می تواند \(f_{n-1}\) حالت داشته باشد.