====== ماتریس فاصله ======


ثابت کنید ماتریس $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$

  * [[سوال ۸|سوال بعد]]
  * [[سوال ۶|سوال قبل]]