למישהו יש רעיון?

[student47]

למישהו יש רעיון?

השאלה היא באלגוריתמים..בנושא של עצים פורשים מינימליים.

(G=(V,E גרף לא מכוון, קשיר עם פונקציית משקל: w:E-->R.
U תת-קבוצה של קדקדים ב-G (זאת אומרת: U מוכלת ב-V).
צריך לכתוב אלגוריתם למציאת עץ פורש מינימלי של G שבו כל קדקדי U הם עלים (יתכנו עלים אחרים בעץ שאינם בקבוצה U), ומשקלו מינימלי מבין כלל העצים הפורשים את G שכל קדקדי U עלים בהם.
(במידה ולא קיים עץ כזה, יש להחזיר תשובה מתאימה).
איך אני בונה עץ פורש מינימלי שכל קדקדי U הם עלים בו?
איך אני יכול להבטיח שקדקדי U יהיו בו עלים?

 

[אורי769]

רמז

דרך למנוע מצלע מלהשתתף בעץ פורש מינימלי זה לתת לה משקל גבוהה במיוחד.

 

[student47]

האם מה שאתה מציע זה:

לתת לצלעות ש-u חל בהן את המשקל הכי גבוהה, ואז בעצם העץ הפורש המינימלי שיבנה, בשלב הראשון לא יכיל את קדקדי U? או שאני לא מבין אותך נכון?

דרך חלופית יכולה להיות: השמטת קדקדי U מהגרף, בניית עץ פורש מינימלי לגרף שמתקבל לאחר ההשמטה של קדקדי U, ובמידה והגרף שמתקבל קשיר, לטפל בהוספת קדקדי U לעץ הפורש המינימלי שנבנה עד עתה?

 

[אורי769]

תשובה

מה שכתבת בפסקה הראשונה הוא בערך מה שהתכוונתי...
נניח שבגרף מסוים G ומשקלות על הצלעות יש צלע e שהמשקל שלה לבד הוא גדול מהסכום של כל שאר המשקלות. עכשיו אתה מפעיל אלגוריתם כלשהו לחיפוש עץ פורש מינימלי. נניח שיצא ש-e היא בעץ הזה. מה זה אומר?