עמוד:359

שאלה 6 . 11 נתון גרף לא מכוון וקשיר G = ( V , E ) ונתונה פונקציית משקל ממשית של קשתותיו . כל קשת בגרף צבועה באחד משלושת הצבעים ! כחול , לבן או אדום . תארו אלגוריתם יעיל , המוצא מבין כל העצים הפורשים שעבורם 2 k + 11- ! , מקסימלי , עץ שמשקלו מינימלי , כאשר r הוא מספר הקשתות הכחולות בעץ , n הוא מספר הקשתות הלבנות בעץ " 7-ו הוא מספר הקשתות האדומות בעץ . מהי סיבוביות זמן הריצה של האלגוריתם ? הוכיחו את האלגוריתם . שאלה 6 . 12 נתון גרף לא מכוון oy G = ( V , E ) משקל שלם 1 < w ( e ) < 100 לכל קשת ך לכל קשת e צבע לבן או שחור . הגרף מיוצג על-ידי רשימות שכנות , והמשקל של כל קשת וצבעה מצוינים ברשימות השכנות . א . כתבו אלגוריתם יעיל , המוצא , מבין כל העצים הפורשים של הגרף G שמכילים את המספר הגדול ביותר האפשרי של קשתות לבנות , את העץ שמשקלו מינימלי . ב . מהי סיבוביות זמן הריצה של האלגוריתם ? שאלה 6 . 13 נתונים שני גרפים קשירים ולא מכוונים על אותה קבוצת קדקודים , כלומר , G = ( V , E ) G \ = ( V , E ) ונתונה פונקציית משקל אי-שלילית ( על הקשתות ) משותפת . כלומר , אם , eeE nE , אז לקשת e משקל זהה בשני הגרפים . בנו אלגוריתם יעיל , הקובע אם לשני גרפים קיים עץ פורש מינימלי משותף : כלומר , אם קיים עבור הגרף G עץ פורש מינימלי שהוא גם העץ הפורש המינימלי של הגרף . G הפתרון 2 x צריך להיות בעל סיבוביות זמן ריצה של . 0 (| 1 ' ' | ) שאלה 6 . 14 נתון גרף G = ( V , E ) לא מכוון , קשיר , עם פונקציית המשקל : W : £ - ? { 1 , 3 , 10 ) עבור כל קשת , ee E הגרף מיוצג על-ידי רשימות שכנות .

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


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