תבנית:מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/חיפוש רוחבי/תרגילים/זמן הריצה ברכיב קשירות קטן/תשובה v2

תבנית:לאחד לתוך ולמחוק את הדף הנוכחי (שהינו דף תבנית!)

נגדיר את $\displaystyle V'$ כקבוצת הצמתים שאליהם אפשר להגיע מ$\displaystyle s$, ו$\displaystyle E'$ כקבוצת הקשתות בין איברי צמתים אלה.

• 1-2 ו5-7 הן $\displaystyle O(1)$
• 3-4 הן $\displaystyle \Theta (|V|)$.
• הלולאה 8-14 מתבצעת בדיוק פעם אחת עבור כל צומת ב$\displaystyle V'$. בפרט, הבדיקה ב8 והפעולה ב9 עולות $\displaystyle \Theta (|V'|)$.
• באופן דומה, הלולאה 10-14 מתבצעת בדיוק פעם אחת עבור כל זוג $\displaystyle u,v$ כך ש$\displaystyle (u,v)\in E'$. הלולאה תורמת לכן $\displaystyle \Theta (|E'|)$.

הסיבוכיות, לכן, היא $\displaystyle O(1)+\Theta (|V|)+\Theta (|V'|)+\Theta (|E'|)=\Theta (|V|+|E'|)$.

כפי שנראה מיד, התשובה לסעיפים תלויה בפיזור הקשתות בין הצמתים ב$\displaystyle V$.

הכרח

הנה משפט עזר בו נשתמש:

משפט: לכל $\displaystyle \alpha <1$,‏ $\displaystyle (n-n^{\alpha })^{2}=\Theta (n^{2})$

הוכחה: נשתמש בכללי גבולות וסדרי גדילה:

$\displaystyle \lim _{n\rightarrow \infty }{\frac {(n-n^{\alpha })^{2}}{n^{2}}}=$
$\displaystyle \lim _{n\rightarrow \infty }{\frac {n^{2}-2n^{1+\alpha }+n^{2\alpha }}{n^{2}}}=$
$\displaystyle \lim _{n\rightarrow \infty }1-2n^{\alpha -1}+n^{2\alpha -2}=1$

נניח ש$\displaystyle V'$ הוא עץ (המסומן באליפסה בתרשים הבא), אך כל שני צמתים ב$\displaystyle V\setminus V'$ מחוברים בקשת.

רכיב קשירות קטן.

מספר הקשתות בגרף הוא

$\displaystyle E=\Theta (|V'|)+\Theta ((|V\setminus V'|^{2})=$
$\displaystyle \Theta (|V|^{\alpha })+\Theta ((|V|-|V|^{\alpha })^{2})=$
$\displaystyle \Theta (|V|^{2}).$

הסיבוכיות היא רק $\displaystyle O(|V|+|E'|)=O(|V|)$, וקל לראות שביטוי זה אינו $\displaystyle \Theta (|V|+|E|)=\Theta (|V|^{2})$.

התכנות

שוב נניח ש$\displaystyle V'$ הוא עץ (המסומן באליפסה בתרשים הבא), אך כעת נניח שאין קשתות בגרף המקורי מעבר לקשתות אלו. במקרה זה הסיבוכיות תהיה מן הסתם $\displaystyle \Theta (|V|+|E'|)=\Theta (|V|+|E|)$.

רכיב קשירות קטן.