דיגרפים

כאשר A קבוצה סופית , גם A  A היא קבוצה סופית . במקרה זה כל תת-קבוצה של A  A היא סופית , כלומר כל יחס מעל A הוא קבוצה סופית של זוגות מתוך . A אחת הדרכים הנוחות לתאר יחס דו-מקומי מעל קבוצה סופית לא ריקה היא גרף מכוון ( , ( directed graph שהוא מודיפיקציה של דיאגרמת החיצים שבה נעזרנו קודם . גרף מכוון מכונה בקיצור דיגרף . בדיגרף של יחס דו-מקומי R מעל קבוצה סופית A יש קדקודים – נקודות המייצגות את איברי , A וחיצים , המבהירים מיהם הזוגות העומדים ביחס : אם , a Rb אז בדיגרף של R יש חץ שמוביל מ- a ל- . b אם , a Ra אז בדיגרף של R יש חץ לולאה , מ- a ל- . a אם a Rb וגם , b Ra אז החץ המקשר את a ו- b הוא דו-כיווני . הנה למשל דיגרף של היחס R מעל { , A = { a , b , c , d 1 אם A היא בת n איברים אז מספר איברי A  A הוא . n 2 שני הדיגרפים הבאים מתארים את היחס המלא ואת יחס השוויון מעל קבוצה { a , b , c } בת שלושה איברים . שאלה 2 . 21 הדיגרף שלפניכם ממחיש יחס . R השלימו :  אל הספר