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