ثابت کنید که تعداد مسیرهای با درازای ۲ بین دو گرهٔ $i$ و $j$ در یک گراف با ماتریسِ مجاوریِ $A$ برابر با درایهٔ سطر $i$ و ستون $j$ -ِ ماتریس $A^2$ است.

Question

ثابت کنید اگر $A$ ماتریس مجاورت گراف ساده $G$ باشد آنگاه درایه $b_{ij}$ که $i \neq j$ در $A^2$ برابر است با تعداد مسیر به طول 2 بین این دو راس.

Answer 1

اگر قرار دهیم $A=( a_{ij} )$ آنگاه $A^{2} =( b_{ij} )$ که در آن $b_{ij} = \sum_{k=1}^n a_{ik}a_{kj}$ حال از آنجایی که هر $a_{ij}$ یا $1$ است یا $0$ لذا هر جمعوند $a_{ik}a_{kj}$ یا $1$ است یا $0$ و زمانی یک است که $a_{ik}=1$ و$a_{kj} =1$ یعنی مسیر $(i,k,j)$ را در گراف داشته باشیم به طور مشابه هر مسیر باعث $1$ شدن یک جمعوند می شود لذا حکم ثابت شد.