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

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

منابع

Kenneth H, Rosen (1998). Discrete Mathematics and its Applications. SIGS Reference Library (به انگلیسی). William C Brown Pub; 4th edition. Retrieved 2007. {{cite book}}: Check date values in: |بازبینی= (help)