به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+1 امتیاز
242 بازدید
در دبیرستان و دانشگاه توسط OXIDE

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

1 پاسخ

+1 امتیاز
توسط erfanm

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

حمایت مالی


کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...