المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:الگوریتم‌های تکمیلی:شمارش تعداد مسیرها با طول ثابت بین هر دو راس

شمارش تعداد گشت‌ها با طول ثابت بین هر دو راس

تعریف مساله

یک گراف جهت‌دار داریم که می‌تواند یال چندگانه یا طوقه نیز داشته باشد (گراف های بدون جهت هم با گذاشتن دو یال جهت دار به ازای هر یال بی جهت، جهت دار میکنیم). میخواهیم تعداد گشت‌ها به طول $m$ را بین هر دو راس در این گراف پیدا کنیم.

الگوریتم

برای این کار ماتریس مجاورت گراف را ماتریس $A$ در نظر میگیریم. آن را به توان $m$ می‌رسانیم. در ماتریس $A$ درایه $(i,j)$ نشان دهنده تعداد گشت های به طول دقیقا $m$ بین دو راس $i$ و $j$ است.

اثبات درستی

درستی این الگوریتم را به استقرا ثابت می‌کنیم:

پایه استقرا: در ماتریس $ A_1=A $ درایه$(i,j)$ نشان دهنده تعداد گشت‌های بین دو راس $i$ و $j$ به طول 1 است. چون گشت به طول 1 فقط میتواند یک یال باشد، پس تعداد گشت‌های به طول 1 بین دو راس، برابر تعداد یال های بین این دو است که در ماتریس مجاورت درایه مربوطه همین را نشان میدهد.

فرض استقرا: حکم به ازای $m - 1$ درست است.

گام استقرا : یک گشت به طول $m$ از $i$ به $j$ را در نظر بگیرید، $m - 1$ یال اول آن یک گشت به طول $m - 1$ با شروع از $i$ است و با یک یال آخر به راس $j$ میرسد. پس راس پایانی گشت $m - 1$ تایی همسایه راس $j$ است، به عبارتی بین راس پایانی گشت $m - 1$ تایی و راس $j$ گشت به طول یک وجود دارد. حال به ازای هر راس در گراف تعداد گشت های بین راس $i$ و آن راس را در $A_{m-1}$ داریم، با ضرب این تعداد در گشت های به طول 1 بین این راس و $j$ و جمع همه مقادیر راس ها، تعداد گشت‌های به طول $m$ بین دو راس $i$ و $j$ بدست می‌آید. این مقدار برابر درایه $(i,j)$ ماتریس $A_m$ است که از ضرب $Aـ{m - 1}$ در $A_1$ بدست آمده است.

پیچیدگی زمانی

برای بدست آوردن تعداد گشت های به طول $m$ بین هر دو راس، باید ماتریس $A_m$ را محاسبه کنیم. میدانیم که ضرب دو ماتریس $n$ در $n$ در هم از $O(n^3)$ است. برای به توان $m$ رساندن کافی است $log(m)$ بار ضرب انجام دهیم. پس کل عملیات از $O(n^3log(m))$ است.

شبه کد

Function MatrixMultiply(A, B):
	For i Form 1 To n
		For j From 1 To n
			C[i][j] = 0
			For x From 1 To n
				C[i][j] += A[i][x] * B[x][j]
Function Power(D, k):
	if k = 1
		return D
	tmp = Power(D, k/2)
	if (k % 2 = 0) :
		return MatrixMultiply(tmp, tmp)
	else
		tmp = MatrixMulyiply(tmp, tmp)
		return MatrixMultiply(tmp, D)

ابزار صفحه