עמוד:249

שאלה 5 . 18 נתון גרף לא מכוון עם משקלות חיוביים על הקשתות . בקשתות חלק הן אדומות וחלק הן כחולות . נתון הקדקוד . s א . תארו אלגוריתם , המוצא את המסלול המינימלי בעל מספר זוגי של קשתות אדומות . 5-מ אל כל קדקוד . ve V ב . נתחו את סיבוביות זמן הריצה של האלגוריתם שהצעתם בסעיף א' . ג . תארו אלגוריתם , המוצא את המסלול המינימלי בעל מספר זוגי של קשתות אדומות ומספר אי-זוגי של קשתות כחולות , מהקדקוד s אל כל קדקוד . v eV שאלה 5 . 19 נתון הגרף המכוון , G ומספור קדקודיו הוא : \/ = { 1 , 2 «) ( כלומר לכל קדקוד מתאים מספר סידורי שונה בין 1 . (|^| = 7 ? -ל נסמן R ( v ) -1 את קבוצת הקדקודים שניתן להגיע אליהם v-n על-ידי מסלול מכוון ב-ס . r ( v ) יהיה קדקוד w e R ( v ) שמספרו הסידורי מינימלי . תארו אלגוריתם יעיל ככל האפשר , המוצא את r ( v ) לכל . ve V שאלה 5 . 20 נתון גרף שמתאר אתרי תיירות בעיר מסוימת ( מוזיאון , כנסייה , בית כנסת , כיכר מרכזית , שוק , אזור פיקניק , גן בוטני . ( לכל אתר מוגדר זמן שהייה מומלץ . הניחו שהאתרים פתוחים 24 שעות ביממה . נתונים גם משכי הנסיעה בין כל שני אתרים ובינם לבין בית המלון . לרשותו של תייר עומדים X ימים לבקר בעיר . הוא יכול לטייל בעיר עד 12 שעות ביממה , ובכל לילה עליו לחזור למלון ולשהות בו לפחות 12 שעות רצופות . כתבו תכנית , שתציע לתייר מסלול סיורים כך שיוכל לבקר במקסימום אתרים במסגרת האילוצים והזמן המוקצב . שאלה 5 . 21 תארו לעצמכם שטח ריבועי שיש בו מכשולים אקראיים . מכשול יוצג על-ידי פוליגון קמור . הפוליגון נתון על-ידי סדרת קדקודים עם קשתות ביניהם והקדקוד האחרון מחובר גם לראשון .

מטח : המרכז לטכנולוגיה חינוכית


לצפייה מיטבית ורציפה בכותר