ثابت کنید که تعداد مسیرهای با درازای ۲ بین دو گرهٔ $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$ شدن یک جمعوند می شود لذا حکم ثابت شد.