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