אשמח אם תוכלו לעזטר לי בשאלה 9 בעמוד 5 כאן: (מקווה שמתאים לכאן ולאתר בכלל...)

http://www.shlomiru.com/courses8/course22/algorithms.pdf

נבצע את אלגוריתם קרוסקל למציאת עץ פורש מינימלי כאשר נמיין את הצלעות כך:

קדום נשים את הצלעות השכנות ל-u ואח"כ את שאר הצלעות ונמיין את כל זה בעזרת מיון יציב.

נריץ קרוסקל ומה שנקבל זה מה שצריך..

יש פתרון אך אשמח לדעת אם גם שלי נכון(אני טועה בדר"כ בזה..)

נשמע שזה עובד.

בשביל להוכיח שזה נכון, אתה צריך להניח שמצד אחד האלגוריתם שלך בנה עץ T, ומצד שני יש עץ 'T טוב יותר (כלומר שהוא ממשקל קטן יותר או שדרגת u ב-'T גדולה יותר), ולהוכיח שזה לא יתכן. במקרה הזה, מובטח לך של-'T ול-T יהיה בדיוק אותו משקל כי אתה משתמש באלגוריתם קרוסקל בכל מקרה, אז רק צריך להראות שלא יתכן שדרגת u ב-'T גדולה יותר.

תודה רבה!!

אפשר אולי להסביר לי את הקטע בפתרון שלהם שהוסיפו בו d/2v . למה?

נראה לי שהתכוונו להוריד d/2v במקום להוסיף...

הרעיון הוא שרוצים לתת עדיפות לקשתות שנוגעות ב-u (כדי לתת להן עדיפות על פני קשתות אחרות), בלי להוריד מהמשקל של העץ. כמובן אי אפשר לעשות את זה באמת, אז מה שעושים הוא להוסיף משקל מאוד מאוד קטן לקשתות האלו, כך שאמנם הוא ישפיע על המשקל הכולל של העץ, אבל לא ישפיע ברמה שתשנה את סדר המשקלים היחסי (כלומר - השינוי הוא כך שלכל שני עצים T1 ו-T2 כך ש-T1 קל מ-T2 לפני השינוי, אז T1 יהיה עדיין קל מ-T2 גם אחרי השינוי).

בשביל למצוא משקל מאוד מאוד מאוד קטן, לוקחים את ההפרש המינימלי של משקלים בין שתי קשתות ומחלקים אותו במספר מאוד גדול (מספר יותר גדול ממספר הקשתות הכולל). כיוון שעץ מכיל בדיוק 1-|v| קשתות, המשקל שהורדת מהעץ הוא לכל היותר d/2, ככה שזה עונה על הדרישה הנ"ל.