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