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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

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

נגדיר את כקבוצת הצמתים שאליהם אפשר להגיע מ, ו כקבוצת הקשתות בין איברי צמתים אלה.

  • 1-2 ו5-7 הן
  • 3-4 הן .
  • הלולאה 8-14 מתבצעת בדיוק פעם אחת עבור כל צומת ב. בפרט, הבדיקה ב8 והפעולה ב9 עולות .
  • באופן דומה, הלולאה 10-14 מתבצעת בדיוק פעם אחת עבור כל זוג כך ש. הלולאה תורמת לכן .

הסיבוכיות, לכן, היא .

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


הכרח[עריכה]

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


משפט:

לכל ,‏


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






מש"ל.PNG

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

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

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



הסיבוכיות היא רק , וקל לראות שביטוי זה אינו .

התכנות[עריכה]

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

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