מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/עצים/תרגילים

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

הוספת קשת ויצירת מעגל[עריכה]

שאלה[עריכה]

אנא הוכח שהוספת קשת לעץ בהכרח תיצור מעגל.

תשובה[עריכה]

נניח שנוסיף לגרף את הקשת . להלן העץ לפני הוספת הקשת.

העץ לפני הקשת

נזכור שעץ הוא קשיר עפ"י ההגדרה, ולכן לפני הוספת הקשת, היה מסלול מ ל.

העץ לפני הקשת - מסלול מודגש

לכן, לאחר הוספת הקשת יש מסלול מ לעצמו: המסלול שאליו משורשרת הקשת .

העץ לפני הקשת - המעגל

הגדרות שקולות לעץ[עריכה]

שאלה[עריכה]

נתון גרף לא-מכוון . להלן שלוש תכונות:

  1. קשיר.
  2. חסר מעגלים.
  3. .

אנא הוכח שכל שתיים משלוש התכונות בהכרח גוררת את התכונה הנותרת.


רמז לגרירה

נניח בשלילה ש1 ו3 מתקיימים, אך יש מעגל.

  1. הסבר מדוע בפשטות לא ייתכן שהמעגל כולל את כל הצמתים.
  2. נניח שהמעגל אינו כולל את כל הצמתים. חשוב מה יקרה כשנוסיף לגרף, מעבר למעגל, עוד צמתים וקשתות.

תשובה[עריכה]

משפט:

אם קשיר וחסר מעגלים, אז .


הוכחה: הוכחנו זאת כבר בהרצאה.

מש"ל.PNG



משפט:

אם חסר מעגלים, ו, אז קשיר.



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

מש"ל.PNG




משפט:

אם קשיר, ו, אז חסר מעגלים.



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

  1. מספירה פשוטה, קל לראות שקיים צומת כלשהו ב שאינו חלק מ. היות ש קשיר, יש קשת המחברת בין לצומת הנ"ל. נגדיר כ את הגרף המתקבל מהוספת הצומת והקשת. נשים לב שב יש צמתים, ו קשתות.
  2. מספירה פשוטה, קל לראות שקיים צומת כלשהו ב שאינו חלק מ. היות ש קשיר, יש קשת המחברת בין לצומת הנ"ל. נגדיר כ את הגרף המתקבל מהוספת הצומת והקשת. נשים לב שב יש צמתים, ו קשתות.
  3. ...
  4. מספירה פשוטה, קל לראות שקיים צומת כלשהו ב שאינו חלק מ. היות ש קשיר, יש קשת המחברת בין לצומת הנ"ל. נגדיר כ את הגרף המתקבל מהוספת הצומת והקשת. נשים לב שב יש צמתים, ו קשתות.קל לראות שהסעיף האחרון סותר את הקביעה .


מש"ל.PNG