|
|
صفحة: 170
דוגמה לשימוש בפעולות שבממשק גנה-גרף («) הפעולה מחזירה גרף המתאים לקשתות הנקראות מהקלט . G הוא משתנה מטיפוס גרף . x , y הס משתנים מטיפוס שלם , הנחה ; הקלט תקין . ( 1 ) אתחל-גרף . G < - W ( 2 ) כל עוד לא הגעת לסוף הקלט , בצע ( 2 . 1 ) קרא ץ ;* , . ( G , x , y ) tyvp- <\ V ) t ) ( 2 . 2 ) ( 3 ) החזר ס . כזכור , המטרה שלנו היא לממש את המודל המתמטי עבור גרפים ורשתות , ולבצע את הפעולות הנדרשות שתוארו לעיל . בהינתן המודל המתמטי והפעולות שיש לבצע בו , אפשר לבנות עבורו מימושים שונים . זאת משום שבדרישות הבעיה לא נקבעו פרטי הפתרון של בעיה מסוימת או מימוש המודל המתמטי עבורה . בבואנו לממש ייצוג גרפים ורשתות , נבחין בין שני מקרים ו מקרה : 1 מספר הצמתים בגרף ידוע מראש . מקרה : 2 מספר הצמתים בגרף אינו ידוע מראש . בשלושת הסעיפים שלהלן נכיר שיטה לייצוג גרפים עבור מקרה , 1 שבו מספר הצמתים בגרף ידוע מראש . 4 . 3 . 2 ייצוג גרף באמצעות מטריצת סמיכות השיטה הראשונה לייצוג גרף שנכיר משתמשת ב"מטריצת סמיכות '' ( שכנות / קישוריות . ( מאחר שמספר הצמתים בגרף ידוע מראש ( נניח , (« - אזי כל צומת בגרף מיוצג על-ידי מספר שלם בין 0 ל- . (« -1 ) בשיטה זו ניתן לייצג גרף כלבד ולא לשת , כלומר , אין כל מידע המיוחס לצמתים , אלא רק מידע על קיום קשתות בגרף .
|
|