تعداد گشت ها به طول n¶

معنی ضرب ماتریس در گراف ها¶

دو گراف n راسی را در نظر بگیرید. برای مثال این دو گراف را گراف آبی با ماتریس مجاورت A و قرمز با ماتریس مجاورت B می نامیم. می خواهیم تعداد گشت های بین دو راس i و j را به دست بیاوریم. به طوری که دو یال داشته باشند و یال اول آن ها آبی و یال دوم آن ها قرمز باشد. این تعداد را \(C_{i,j}\) می نامیم. واضح است که برای محاسبه این مقدار می توان روی راس میانی این گشت حالت بندی کرد (راسی مانند k) و سپس یال های آبی از i به k را در یال های قرمز از k به j ضرب کرد و مقادیر به دست آمده را به ازای تمام k های ممکن جمع زد. به زبان ریاضی:

که با کمی دقت می توان دریافت که ماتریس C برابر ضرب ماتریس A در B است.

توان ماتریس¶

توان ماتریس را مانند توان اعداد، به این صورت تعریف می کنیم که \(A^n\) یعنی n بار ضرب A در خودش. طبق قضیه ای که در بالا نشان دادیم می توان دریافت که تعداد گشت های به طول n از i به j برابر درایه (i,j) در \(A^n\) است. برای اثبات به ازای هر گشت به طول n-1 یک یال قرمز بگذارید و به ازای هر یال گراف یک یال آبی. به وضوح هر گشت به طول n معادل یک گشت با یک یال قرمز و یک یال آبی است. و چون \(A^n = A^{n-1}A\) حکم را با استقرا می توان ثابت کرد.

الگوریتم و پیچیدگی¶

پس برای حل مساله کافیست تا بتوانیم توان ماتریس را در زمان خوبی محاسبه کنیم. چون ضرب ماتریس ها خاصیت شرکت پذیری دارد ( یعنی \((AB)C = A(BC)\) ) پس مهم نیست که به چه ترتیبی توان را حساب می کنیم. اگر توان زوج باشد داریم:

و اگر فرد باشد، داریم:

اگر ضرب ماتریس را با الگوریتم بدیهی اش، یعنی \(O(n^3)\) محاسبه کنیم، می توان به صورت بازگشتی برای محاسبه \(A^k\) ابتدا توان \(A^{\lfloor\frac{k}{2}\rfloor}\) را محاسبه کنیم و سپس به وسیله روابط بالا جواب مساله را حساب کنیم. زمان اجرای این الگوریتم بازگشتی برابر است با:

نام این الگوریتم الگوریتم توان رسانی سریع است که در جایی که می خواهیم یک عملیات شرکت پذیر را روی یک عضو چندین بار تکرار کنیم می توانیم از آن استفاده کنیم. مثلا برای توان اعداد نیز می توانید از همین الگوریتم استفاده کنید.

تعمیم¶

الگوریتمی که در این جا بررسی کردیم تنها برای محاسبه تعداد گشت های به طول ثابت کاربرد ندارد، بلکه می توان با آن خواص دیگری از گشت های به طول ثابت را نیز (مانند بزرگ ترین گشت یا گشت با کم وزن ترین یال) به دست آورد. برای مثال می خواهیم بین دو راس گشتی به طول k پیدا کنیم که جمع وزن یال های آن بیشینه باشد. اگر بخواهیم این مساله را برای گرافی حل کنیم که یال های آن قرمز و آبی باشد و گشت های با یک یال قرمز و یک یال آبی مد نظر مان باشد پاسخ به این صورت به دست می آید:

می توانیم ماتریس C را به عنوان ترکیب ماتریس A و B تعریف کنیم. با کمی دقت می توان دریافت که عمل ترکیب مانند عمل ضرب ماتریس شرکت پذیر است. برای اثبات می توانید یک گراف با یال های قرمز و آبی و سبز در نظر بگیرید و گشتی که قرمز - آبی - سبز باشد و جمع وزن یال هایش بیشینه باشد را از دو روش به دست آورید. پس می توان مشابه قبل توان ماتریس را تعریف کرد و با استقرا ثابت کرد که \(A^k_{i,j}\) برابر بزرگترین گشت به طول k بین دو راس i و j است و الگوریتم \(O(n^3lg(k))\) برای محاسبه این ماتریس وجود دارد.