الگوریتم پیدا کردن رابطه در یک ماتریس

[hadiloui]

با سلام

میخواستم ببینم در یک ماتریس مربعی با عناصر صفر و یک چگونه میتوان فهمید که رابطه بازتابی

یا غیر بازتابی یا تقارن یا پاد تقارن یا تعدی دارد.

در مورد بازتابی میتوان گفت که اگر قطر اصلی یک باشد ماتریس دارای این رابطه خواهد بود

ولی الگوریتم بقیه رابطه ها را نمی دانم اگر مرا در این زمینه یاری کنید مخصوصا در مورد تعدی

تشکر فراوان را از شما دارم.

[raha_hakhamanesh]

با سلام

دوست عزیز تمام آنچه را که شما به آن نیاز دارید در تمام کتابهای ساختمان گسسته است ولی توضیح مختصری خدمت شما عرض می کنم.

همانطور که خودتان فرمودید برای بررسی بازتابی کافیست عناصر قطر اصلی را بررسی کنیم اگر تمام عناصر 1 بود ماتریس دارای خاصیت بازتابی است در غیر اینصورت خیر مثلا در یک حلقه
A[i,i] ok
را تست نمایید .
برای خاصیت تقارنی بایستی عناصری که در بالای قطر اصلی قرار دارد و دارای مقدار غیر صفر است بررسی کنید و با اندیس معکوس مقایسه نمایید مثلا
if (a[i,j]==1 & a[j,i]==1) then ok
به ازای تمام مقادیر حال ممکن است یک ماتریس نه متقارن باشد و نه نامتقارن دقت کنید

برای بررسی تعدی کافیست به ازای تمام مقادیر اگر در مختصاتی از ماتریس مقدار 1 داریم آن نقطه به عنوان عنصر دوم است و اگر در ردیف عنصر دوم با عنصر سوم مقدار 1 داریم آنگاه به سراغ مختصات عنصر اول و سوم بروید اگر در محل تلاقی مقدار یک بود تعدی برقرار است در غیر اینصورت خیر .
مثال
A[i,j]=1
A[j,k]=1
if A[i,k]==1 then ok