עץ פורש מינימלי
נתון גרף G לא מכוון ממושקל וקשיר שבו כל קשת צבועה בשחור או לבן.
מבין העצים הפורשים המינימליים, צריך להחזיר את העץ הכי שחור. כלומר את העץ פורש המינימלי עם הכי הרבה קשתות שחורות מבין כל העצים הפורשים המינימליים.
חשבתי להשתמש בקרוסקל עם שינוי קל. בשלב שבו קרוסקל ממיין את הקשתות בסדר עולה (לא עולה ממש כי יתכן שיש קשתות בעלות אותו משקל), נדאג שבמידה וישנן 2 קשתות (אחת לבנה ואחת שחורה) בעלות משקל זהה, אז הקשת השחורה תופיעה לפני הלבנה, וכך קרוסקל יוסיף את השחורה לעץ פורש המינמלי (במידה והיא לא סוגרת מעגל) לפני שהוא מוסיף את הכחולה (כמובן שאם הכחולה לא סוגרת מעגל, אז גם היא תתווסף לעץ פורש המינימלי, אך אם בעקבות הוספת השחורה, יווצר מצב שבו הכחולה תסגור מעגל, אז הכחולה לא תיהיה בעץ פורש המינימלי, בעוד שאם לא היינו עושים את השינוי הזה, היא כן הייתה בעץ פורש המינימלי).
יש לי 2 שאלות:
1. בעצם השינוי שעשיתי, עשוי להביא תוצאה שונה מאשר האלגוריתם המקורי (מבחינת הצבע של העץ פורש...לא מבחינת המינימלית) רק עבור מצבים שבהם יש קשתות בצבעים שונים עם אותו משקל? כלומר במידה ואין 2 קשתות עם אותו משקל, אז קרוסקל המקורי וקרוסקל עם השינוי, יתנו תוצאה זהה לחלוטין?
2. מדוע מובטח לי (במידה ובכלל מה שהצעתי נכון), שלא קיים אלגוריתם אחר למציאת עץ פורש מינימלי, שבאמצעותו אקבל עץ פורש מינימלי בעל יותר צלעות שחורות מהאלגוריתם שהצעתי?
תודה מראש.
נתון גרף G לא מכוון ממושקל וקשיר שבו כל קשת צבועה בשחור או לבן.
מבין העצים הפורשים המינימליים, צריך להחזיר את העץ הכי שחור. כלומר את העץ פורש המינימלי עם הכי הרבה קשתות שחורות מבין כל העצים הפורשים המינימליים.
חשבתי להשתמש בקרוסקל עם שינוי קל. בשלב שבו קרוסקל ממיין את הקשתות בסדר עולה (לא עולה ממש כי יתכן שיש קשתות בעלות אותו משקל), נדאג שבמידה וישנן 2 קשתות (אחת לבנה ואחת שחורה) בעלות משקל זהה, אז הקשת השחורה תופיעה לפני הלבנה, וכך קרוסקל יוסיף את השחורה לעץ פורש המינמלי (במידה והיא לא סוגרת מעגל) לפני שהוא מוסיף את הכחולה (כמובן שאם הכחולה לא סוגרת מעגל, אז גם היא תתווסף לעץ פורש המינימלי, אך אם בעקבות הוספת השחורה, יווצר מצב שבו הכחולה תסגור מעגל, אז הכחולה לא תיהיה בעץ פורש המינימלי, בעוד שאם לא היינו עושים את השינוי הזה, היא כן הייתה בעץ פורש המינימלי).
יש לי 2 שאלות:
1. בעצם השינוי שעשיתי, עשוי להביא תוצאה שונה מאשר האלגוריתם המקורי (מבחינת הצבע של העץ פורש...לא מבחינת המינימלית) רק עבור מצבים שבהם יש קשתות בצבעים שונים עם אותו משקל? כלומר במידה ואין 2 קשתות עם אותו משקל, אז קרוסקל המקורי וקרוסקל עם השינוי, יתנו תוצאה זהה לחלוטין?
2. מדוע מובטח לי (במידה ובכלל מה שהצעתי נכון), שלא קיים אלגוריתם אחר למציאת עץ פורש מינימלי, שבאמצעותו אקבל עץ פורש מינימלי בעל יותר צלעות שחורות מהאלגוריתם שהצעתי?
תודה מראש.