ماتریس فاصله

ثابت کنید ماتریس $D$، ماتریس فاصله‌ی یک گراف همبند است اگر و فقط اگر شایط زیر برقرار باشند:

• $D$ یک ماتریس متقارن با عناصر صحیح و مثبت است و عناصر روی قطر اصلی آن صفر هستند.
• برای هر $i$ و $j$ و $k$ داریم: $d_{ij}+d_{jk} \geq d_{ik} \quad\quad\quad\quad\quad$
• برای هر $i$ و $k$ که $d_{ik}>1$، یک $j$ وجود دارد به طوری که: $d_{ik}=d_{ij}+d_{jk} \quad\quad\quad\quad\quad$

• سوال بعد
• سوال قبل