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

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

קפיצה אל: ניווט, חיפוש

נתון גרף לא-מכוון \displaystyle G = (V, E). להלן שלוש תכונות:

  1. \displaystyle G קשיר.
  2. \displaystyle G חסר מעגלים.
  3. \displaystyle |E| = |V| - 1.

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


רמז לגרירה \displaystyle 1 \wedge 3 \rightarrow 2

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

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



מקור: http://he.wikibooks.org/wiki/%D7%9E%D7%91%D7%A0%D7%99_%D7%A0%D7%AA%D7%95%D7%A0%D7%99%D7%9D_%D7%95%D7%90%D7%9C%D7%92%D7%95%D7%A8%D7%99%D7%AA%D7%9E%D7%99%D7%9D_-_%D7%9E%D7%97%D7%91%D7%A8%D7%AA_%D7%A7%D7%95%D7%A8%D7%A1/%D7%92%D7%A8%D7%A4%D7%99%D7%9D/%D7%A2%D7%A6%D7%99%D7%9D/%D7%AA%D7%A8%D7%92%D7%99%D7%9C%D7%99%D7%9D/%D7%94%D7%92%D7%93%D7%A8%D7%95%D7%AA_%D7%A9%D7%A7%D7%95%D7%9C%D7%95%D7%AA_%D7%9C%D7%A2%D7%A5/%D7%A9%D7%90%D7%9C%D7%94