שאלה באלגוריתמים

[גיל14]

שאלה באלגוריתמים

יש לי שאלה מממ"ן. עקרונית אני נגד פתרונות של שאלות מממ"נים בפורום, אבל כאן אני אבוד לחלוטין והייתי שמח לקבל כיוון לאן לחשוב... נתון גרף לא מכוון G = (V,E) z קשיר, עבורו לכל קשת e מותאמת פונקציה f_e(x) = a_e x + b_x כאשר a_e, b_e מספרים ממשיים. לכל t בקטע [0,1] משקלה של כל קשת e הוא f_e(t) = a_e t + b_e. תנו אלגוריתם יעיל ככל שתוכלו המוצא t בקטע [0,1] עבורו המשקל של עץ פורש מינימלי T, של G הוא הקטן ביותר. במילים אחרות: אם W הוא משקלו של עפ"מ כלשהו עבור y \neq t אזי משקלו של T גדול או שווה למשקלו של W.

 

[גיל14]

סליחה טעות - f_e(x) = a_e x + b_e

 

[Fingertip]

הפתרון

לאחר סיעור מוחין אינטנסיבי של גיל, amamak ושלי, מצאנו את הפתרון הבא: הערך המינימלי יתקבל כאשר t = 0 או t = 1, ולכן כל מה שצריך לעשות זה לבדוק את העץ הפורש המינימלי המתקבל על ידי t = 0 ואת העץ הפורש המינימלי עבור t = 1 ולבחור את הנמוך מביניהם. על מנת להראות שאכן t = 0,1 מספיקים, נשים לב להבחנה הבאה: תהי A קבוצת כל העצים הפורשים של G. לכל עץ T מ-A נתאים פונקציה (f_T(t שמחשבת את המשקל של העץ הזה לכל t בקטע [0,1]. נשים לב ש-f_T היא פשוט סכום כל הפונקציות שעל הקשתות. מכיוון שכל הפונקציות האלה לינאריות, הרי ש-f_T לינארית. הפונקציה המתאימה לכל t בקטע את המשקל של העץ הפורש המינימלי עבור ה-t הזה היא פשוט min_A f_T. קל לראות שזו פונקציה רציפה לינארית למקוטעין, אבל מה שלא כל כך ברור הוא שמדובר בפונקציה שרק עולה, ולאחר מכן רק יורדת (הוכיחו!), ולכן הערך המינימלי שלה מתקבל ב-t = 0 ו-t = 1, וזהו. אהד.

 

[yaeerk]

שאלה

מהי ההגדרה של עץ פורש מינימלי?

 

[גיל14]

עץ פורש שסכום המשקלות על הקשתות שלו מינימלי.

 

[yaeerk]

אז משהו יותר בסיסי

מהו עץ פורש של גרף קשיר לא מכוון.

 

[1ca1]

קבוצת קשתות קשירה כך שהיא מכסה את כל הגרף

והיא מינימלית (מבחינת משקל)

 

[yuvalmadar]

בלי המינימליות

(היא שאלה על עץ פורש, לאו דווקא מינימלי) ראי גם את הערך המתאים בוויקיפדיה.