المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۸:گراف:سوال ۷

ماتریس فاصله

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

ابزار صفحه