תקציר השאלה - נדרשנו למצוא אוסף של קשתות , כך שלכל קשת e קיים מעגל C שהיא חלק ממנו וכל קשת אחרת באותו מעגל C משקלהקשתות האחרות קטן או שווה למשקל של e. כל משקלי הקשתות מ1 ועד 10.
חשבתי על כמה פתרונות אפשריים אבל אני לא בטוחה באף אחד מהם ואשמח להכוונה:
פתרון א' - נריץ DFS ונמצא את כל המעגלים בגרף (כל פעם שנגיע בקשת אחורית לצומת כלשהו v נחזור אחורה במסלול שעברנו ונסמן את כל הצמתים עד שנגיע חזרה לv וככה נסמן את כל המעגלים). בכל מעגל שמצאנו נקח את הקשת/ות הכבדות ביותר.
אני חושבת שהאלגוריתם עצמו עובד אבל הפתרון הזה הוא אקפוננציאלי (החלק של מציאת המעגלים)
פתרון ב'- אפשר להוכיח בקלות שקשת e באוסף המבוקש אמ"מ אם קיים עפ"מ כלשהו T שלא מכיל את e, כלומר e לא נמצאת בכל העפ"מים. הוכחנו בשיעורי הבית שe נמצאת בכל העפ"מים אמ"מ אין מסלול הסוגר איתה מעגל שמורכב רק מקשתות במשקל קטן או שווה למשקל e, שהשלילה שלה היא בדיוק הטענה שאנחנו מחפשים.
אז האלגוריתם שנרצה יהיה:
1. למיין את הקשתות לפי משקל במיון מניה (המשקלים חסומים)
2. נריץ קרוסקל בשינוי הבא: כשנעבור ל"קטגורית משקל חדשה" i (כלומר שנעבור לקשתות במשקל גדול ממה שעברנו עד כה) לכל קשת e במשקל i נבצע את הפעולה הבאה: נוסיף זמנית את כל הקשתות באותה קטגורית משקל חוץ מe למבנה UNION FIND שלנו ונבדוק האם שני הקצוות של e באותם רכיבי קשירות. אם כן אז יש מסלול שכולו קל או שווה למשקל e ולכן נוסיף את e לאוסף. נוריד את כל הקשתות שהוספנו ונמשיך לקשת הבאה ונעשה אותו דבר. אחרי שנסיים עם כל הקשתות בקטגוריית המשקל הנוכחית, נריץ קרוסקל רגיל על קטוגרית המשקל הזו.
די בטוחה שגם זה נכון אבל הסיבוכיות פה עולה (לא בטוחה בכמה- חושבת שזה מכפיל את הסיבוכיות של קרוסקל בO(E) )
פתרון ג'
לכל משקל מ1 ועד 10:
1. נוריד את כל הקשתות במשקל כבד ממש מi.
2. לכל קשת במשקל i, נוריד אותה מהגרף, נריץ BFS ומשני הקצוות שלה ונמצא מסלול שכולו קל או שווה למשקלה. אם מצאנו - נוסיף אותה לאוסף, אחרת לא. בסיום נחזיר אותה חזרה.
הסיבוכיות:
- כל BFS הוא O(E+V) (בפועל פחות כי לא כל הקשתות משתתפות)
- מספר הBFSים שאנחנו מריצים הוא כמספר הקשתות בגרף.
סהכ E*(E+V).
אשמח להכוונה לפתרון הנכון ולעזרה עם חישוב הסיבוכיות.