|
|
עמוד:360
א . כתבו אלגוריתם יעיל , המוצא קבוצת קשתות שמכילה לפחות קשת אחת מכל מעגל בגרף ושמשקלה הכולל מינימלי . ב . מהי סיבוביות זמן הריצה של האלגוריתם שהצעתם ? שאלה 6 . 15 א . נתון גרף לא מכוון G = ( V , E ) ונתונה פונקציית משקל , W : £ - >/? + כאשר כל קשת צבועה באחד מן הצבעים - אדום , כחול או לבן . כתבו אלגוריתם אשר מוצא מבין כל העצים הפורשים המינימליים עבור G את העץ הפורש המינימלי , שבו מספר הקשתות האדומות פחות מספר הקשתות הכחולות הוא מקסימלי . ב . מהי סיבוביות זמן הריצה של האלגוריתם שהצעתם ? שאלה 6 . 16 א . הציעו אלגוריתם יעיל , המקבל גרף לא מכוון G- ( V , E ) ושתי פונקציות משקל ממשיות , W . E R w - . E- > R הבודק אם קיים בגרף G עץ פורש , שהוא מינימלי 2 ^ x על-פי כל אחת משתי פונקציות המשקל , ואם קיים עץ כזה - מצאו אותו . הוכיחו את נכונות האלגוריתם . ב . מהי סיבוביות זמן הריצה של האלגוריתם שהצעתם ? שאלה 6 . 17 נתון גרף לא מכוון , ממושקל , שמיוצג על-ידי רשימות שכנות , כאשר המשקל של כל קשת מצוין לידה , ונתונה הקשת e בגרף הזה . א . כתבו אלגוריתם יעיל , הקובע אם ישנו בגרף עץ פורש מינימלי המכיל את הקשת . e ב . מהי סיבוביות זמן הריצה של האלגוריתם שהצעתם ? שאלה 6 . 18 נתון גרף G = ( V , E ) לא מכוון וקשיר אשר כל אחת מקשתותיו צבועה בצבע שחור או לבן .
|
|