|
|
עמוד:321
שאלה 5 . 38 נתון הגרף . G = ( V , E ) פונקציית המשקל •/? + W = E - » קובעת משקל ( מספר ) לכל קשת בגרף . G א . כתבו אלגוריתם יעיל , הקובע אם קשת מסוימת e נמצאת על כל המסלולים הקצרים ביותר מקדקוד המקור s לקדקוד היעד . t ב . נתחו את סיבוביות זמן הריצה של האלגוריתם שהצעתם בסעיף . 'א שאלה 5 . 39 נתון הגרף . G = ( V , E ) פונקציית המשקל W = E- > R + קובעת משקל ( מספר ) לכל קשת בגרף . G כל קשת בגרף צבועה באדום או בלבן . בגרף ס נתונים שני צמתים : s . ? -ו א . כתבו אלגוריתם יעיל , אשר מוצא מבין המסלולים הקצרים ביותר בין s / -ל ( ביחס למשקלות שעל הקשתות ) את המסלול שבו מספר הקשתות האדומות מינימלי . ב . נתחו את סיבוביות זמן הריצה של האלגוריתם שהצעתם בסעיף אי . שאלה 5 . 40 ( רשות ) נתון גרף לא מכוון עם משקלות חיוביים על הקשתות . חלק מהקשתות אדומות וחלק כחולות . נתון הקדקוד .. r א . תארו אלגוריתם המוצא את המסלול המינימלי בעל מספר זוגי של קשתות אדומות , $ -מ אל כל קדקוד . v e v ב . נתחו את סיבוביות זמן הריצה של האלגוריתם שהצעתם בסעיף א' . ג . תארו אלגוריתם המוצא את המסלול המינימלי בעל מספר זוגי של קשתות אדומות ומספר אי-זוגי של קשתות כחולות . 5-מ אל כל קדקודי & י . \ שאלה 5 . 41 ( רשות ) נתון גרף מכוון G שצמתיו ממוספרים כך : v = ( 1 , 2 ,..., n ) ( כלומר לכל צומת מתאים מספר סידורי שוגה בין 1 . \ v \ = /! -ל נסמן R ( v ) -1 את קבוצת הצמתים , שניתן להגיע אליהם ^ -מ על-ידי מסלול מכוון . £ -ב tiy ) יהיה הצומת W e R ( v ) שמספרו הסידורי מינימלי . תארו אלגוריתם יעיל ככל האפשר , המוצא את rty ) לכל . ve V
|
|