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

فیبوناچی¶

یک گراف دو راسی را در نظر بگیرید که در آن دو راس به هم یال دارند و راس اول به خودش یک طوقه دارد. می خواهیم تعداد گشت های به طول n از راس یک به خودش را محاسبه کنیم و این مقدار را \(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 را به صورت زیر تعریف می کنیم.

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