שאלה על קבוצות זרות

[SmartToyBoy]

שאלה על קבוצות זרות

שלום לכולם! ביישום של קבוצות זרות כמציאת הרכיבים הקשירים בגרף בלתי מכוון, יש את האלגוריתם היסודי שמחשבת את הרכיבים הקשירים של גרף. זה אלגוריתם ידוע, שמתבצע כך (בקצרה): 1. לכל קודקוד בגרף עושים make_set ויוצרים קבוצה זרה 2. לכל קשת בגרף בודקים אם שני הקודקודים הנמצאים עליה שייכים לאותו רכיב קשיר בגרף כלומר האם find_setU = find_setV , ואם כן, אז מבצעים פעולת Union המאחדת את שתי הקבוצות של הקודקודים הללו. שאלתי היא כמה פעמים נקראות find_set ו Union במהלך הרצת האלגוריתם , אם V הוא מס' הקודקודים , E הקשתות ו-k הוא מס' הרכיבים הקשירים. אני חושב ש- find_set מתבצעת E פעמים כי בסה"כ פעולת הבדיקה שבה משתמשים ב- find_set מתבצעת עבור כל קשת. לגבי Union אני מבין שזה קשור למס' הרכיבים הקשירים בגרף , אבל איך => אולי V/k [חסם עליון של זה] חשבתי על כמה דברים אבל אני לא בטוח בתשובה , ואשמח אם תוכלו לעזור... תודה מראש

SmartToyBoy.

 

[ron369]

נכון, אתה כנראה צודק

באלגוריתם הדי טריוויאלי שתיארת, בהכרח מתבצעות בדיוק |E| פעולות make-set, ולכל היותר O(

) ZZZ פעולות union, אם אני לא טועה. (חסם הדוק יותר הוא

-1, כי לאחר מספר זה של פעולות הגרף הוא רכיב קשירות אחד, וגם כי קיימת דוגמא (אחת לפחות

) של גרף שבו מתבצע בדיוק מספר זה של פעולות union).

 

[ron369]

*| V | נהפך בהודעה ל../images/Emo127.gif, לצערי

 

[SmartToyBoy]

תודה! אני מבין ש-...

Union תתבצע לכל היותר V או V-1 פעמים. אבל האם אפשר למצוא חסם הדוק יותר כאשר ידוע שמס' הרכיבים הקשירים בגרף הוא k?

 

[ron369]

אה, סליחה, אתה צודק.

אם יש לך k רכיבים קשירים, נובע מכך שהתבצעו לכל היותר (או בדיוק? תחשוב לבד

)

-k פעולות union, אם אני לא טועה. (או

-k-1? שוב, תחשוב לבד

)