|
|
עמוד:221
מצאו עבור כל אחד מהם את הרכיבים הקשירים ואת מספרם . שאלה 5 . 6 להלן הגדרה חדשה ו הקדקוד ' 1 בגרף קשיר G נקרא "נקודת חיתוך" articulation ) ( point אם כאשר מסירים את ' 1 ואת כל הקשתות הנוגעות בו , נקבל גרף חדש G שאינו קשיר . א . תנו דוגמה לגרף עם שישה קדקודים שיש לו שתי נקודות חיתוך . ב . תנו דוגמה לגרף עם שישה קדקודים שאין לו נקודות חיתוך כלל . ג . הראו כי הקדקוד v בגרף קשיר G ייקרא נקודת חיתוך אם ורק אם קיימים שני קדקודים כלשהם x * ' -ו בגרף G המקיימים את התכונה ו כל מסלול w-n . * -ל עובר דרך הקדקוד ע . 5 . 3 . 2 הגדרה פורמלית של בעיית המסלול הקצר נתון גרף משוקלל G = ( V , E ) לכל קשת מיוחס מספר אשר יכול לייצג מחיר , מרחק בין שני יישובים , עלות בניית כביש שיקשר בין שני היישובים , ממוצע מספר הלקוחות העוברים מטרמינל אחד לטרמינל אחר , זמן בכדי להגיע מיישוב אחד ליישוב אחר , ועוד . בלי הגבלת הכלליות נניח שהמספר שמיוחס לקשת יציין את המרחק בין שני יישובים . כל קדקוד ברשת מייצג יישוב , וכל קשת ברשת מייצגת כביש בין שני יישובים , והמספר שעל הקשת
|
|