הגרף מורכב מקודקודים וקצוות. הקודקודים מחוברים בקצוות על פי מאפיין מסוים - יחס ההיארעות, המגדיר את מערך הקצוות. במקרה זה, לולאות וקודקודים מבודדים יכולים להיווצר.
הוראות
שלב 1
תן למכלול הקצוות של הגרף וניתן היחס שלאורכו ניתן לצייר קצה מקודקוד אחד למשנהו. כדוגמה, קבוצת הקודקודים {1, 2, 3, 4, 5, 6, 7, 8}, שני הקודקודים x ו- y הם ביחס x + y <8.
שלב 2
בנה מטריצת סמיכות קודקודית. לשם כך, בנה שולחן מרובע, מספר השורות והעמודות בטבלה עולה בקנה אחד עם מספר הקודקודים. ואז שים 1 בצומת השורה ה- I והעמודה ה- J אם הקודקודים i ו- j מספקים את היחס הנתון. שים 0 בצומת השורה ה- I והעמודה ה- J אם היחס עבור האלמנטים המתאימים אינו מתקיים.
בדוגמה שלנו, השורה הראשונה ממולאת באופן הבא:
1 + 1 <8, אז יש 1 בצומת השורה הראשונה והעמודה הראשונה
1 + 2 <8, שוב 1
1 + 3 <8, שוב 1
1 + 7 <8, אי שוויון שגוי, כך שאלמנט זה בטבלה יהיה 0
1 + 8 <8, שוב 0
שלב 3
כדי לברר את מספר הקצוות, ספר את מספר הקצוות במטריצת הסמיכות מבלי לשכפל את הקצוות.
בדוגמה התקבלה מטריצה סימטרית, אז ספרנו תחילה את אלה מעל האלכסון הראשי של המטריצה (מסומנים בכחול), ואז את אלה על האלכסון הראשי (מסומנים באדום). המספר הכולל של הצלעות הוא 12.
שלב 4
בנה מטריצה של אירועים (קצוות). לשם כך, צייר טבלה, מספר השורות בה שווה למספר הקודקודים בגרף, ומספר העמודות שווה למספר הקצוות. שים יחידות על הקווים שיחוברו בקצה. הקצוות המובילים מהקודקוד אליו נקראים לולאות ומתווספים לקצה המטריצה. בעמודות המתאימות לולאות ישנה יחידה אחת בלבד, בניגוד לשאר הקצוות.
שלב 5
עכשיו צייר גרף. הנח את הקודקודים על הנייר בכל דרך שהיא וחבר אותם לקצוות באמצעות השולחנות הבנויים. קודקודים שאינם מחוברים בקצוות נקראים מבודדים.
