رابطه‌ها و گراف‌ها

تعریف: هرگاه A و B دو مجموعه باشند آنگاه یک رابطه از A به B عبارت است از زیر مجموعه ای از A×B. زیر مجموعه‌های A×A را رابطه‌های روی A گویند.
مثال: مجموعهٔ A={۱٬۲,۳٬۴,۶٬۱۲} مفروض است.

به ازای هر دو عضو a,b که عضو مجموعه A باشند تعریف می‌کنیم:

aRb هرگاه a|b.

حال فرض کنید A یک مجموعه متناهی و R یک رابطه روی A باشد. به R گراف جهت دار G را به صورت زیر نسبت می‌دهیم.

رأس‌های G اعضای A هستند و راس a به رأس b متصل است هرگاه aRb.
مثلاً گراف مربوط به رابطه ای که در مثال بالا است در شکل زیر نشان داده شده‌است:

مثلاً از گراف شکل زیر نتیجه می‌شود که رابطه ای مانند R روی مجموعهٔ A={a,b,c} تعریف شده‌است و داریم:

aRb , aRc , bRb , cRa , cRc.

منابع 

ریاضیات