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

משפט: אם $\displaystyle G=(V,E)$ קשיר וחסר מעגלים, אז $\displaystyle |E|=|V|-1$.

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

משפט: אם $\displaystyle G=(V,E)$ חסר מעגלים, ו$\displaystyle |E|=|V|-1$, אז $\displaystyle G$ קשיר.

הוכחה: כל גרף חסר מעגלים הוא יער; בפרט, נניח שמדובר ביער בעל $\displaystyle i$ עצים. אם $\displaystyle i=1$, אז ההוכחה הושלמה. אם $\displaystyle i>1$, אז, בהנחה שבעץ ה$\displaystyle j$ יש $\displaystyle |V_{j}|$ צמתים (ולכן $\displaystyle |V_{j}|-1$ קשתות), יש בגרף סך הכל $\displaystyle \sum _{j=1}^{i}|V_{j}|$ צמתים, אך רק $\displaystyle \sum _{j=1}^{i}[|V_{j}|-1]=\sum _{j=1}^{i}|V_{j}|-i<|V|-1$ קשתות.

משפט: אם $\displaystyle G=(V,E)$ קשיר, ו$\displaystyle |E|=|V|-1$, אז $\displaystyle G$ חסר מעגלים.

הוכחה: נניח שבגרף יש מעגל בעל $\displaystyle n'\leq n$ צמתים. קל לראות אז שבמעגל יש $\displaystyle n'$ קשתות. אם $\displaystyle n'=n$, אז לא ייתכן ש$\displaystyle |E|=|V|-1$. נניח לכן ש$\displaystyle n'<n$. נגדיר כ$\displaystyle G'_{1}$ את המעגל.

1. מספירה פשוטה, קל לראות שקיים צומת כלשהו ב$\displaystyle G$ שאינו חלק מ$\displaystyle G'_{1}$. היות ש$\displaystyle G$ קשיר, יש קשת המחברת בין $\displaystyle G'_{1}$ לצומת הנ"ל. נגדיר כ$\displaystyle G'_{2}$ את הגרף המתקבל מהוספת הצומת והקשת. נשים לב שב$\displaystyle G'_{2}$ יש $\displaystyle n'+1$ צמתים, ו$\displaystyle n'+1$ קשתות.
2. מספירה פשוטה, קל לראות שקיים צומת כלשהו ב$\displaystyle G$ שאינו חלק מ$\displaystyle G'_{2}$. היות ש$\displaystyle G$ קשיר, יש קשת המחברת בין $\displaystyle G'_{2}$ לצומת הנ"ל. נגדיר כ$\displaystyle G'_{3}$ את הגרף המתקבל מהוספת הצומת והקשת. נשים לב שב$\displaystyle G'_{3}$ יש $\displaystyle n'+2$ צמתים, ו$\displaystyle n'+2$ קשתות.
3. ...
4. מספירה פשוטה, קל לראות שקיים צומת כלשהו ב$\displaystyle G$ שאינו חלק מ$\displaystyle G'_{n-n'}$. היות ש$\displaystyle G$ קשיר, יש קשת המחברת בין $\displaystyle G'_{n-n'}$ לצומת הנ"ל. נגדיר כ$\displaystyle G'_{n-n'+1}$ את הגרף המתקבל מהוספת הצומת והקשת. נשים לב שב$\displaystyle G'_{n-n'+1}$ יש $\displaystyle n$ צמתים, ו$\displaystyle n$ קשתות.קל לראות שהסעיף האחרון סותר את הקביעה $\displaystyle |E|=|V|-1$.