Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

ماتریس فاصله

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

  • D یک ماتریس متقارن با عناصر صحیح و مثبت است و عناصر روی قطر اصلی آن صفر هستند.
  • برای هر i و j و k داریم: dij+djkdik
  • برای هر i و k که dik>1، یک j وجود دارد به طوری که: dik=dij+djk

ابزار صفحه