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

تعریف: هرگاه 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.