פתרונות נבחרים לשיעורי הבית
תרגיל מס' 12

1.	כמה רכיבי קשירות יש לגרף חסר מעגלים בן 17 קודקודים ו – 10 קשתות?
פתרון: נסמן ב – k את מספר רכיבי הקשירות. נסמן ב – ci את מספר הצמתים ברכיב הקשירות ה - i. כל רכיב קשירות הוא עץ, לכן מספר הקשתות בו הוא כמספר הצמתים פחות 1. לפיכך: , כלומר . לכן .
הערה: באופן דומה, קל להכליל את התוצאה ולהראות כי בכל יער, מספר הקשתות שווה למספר הקודקודים פחות מספר רכיבי הקשירות.
פתרון אחר: לפני ציור הקשתות יש 17 רכיבי קשירות. כל קשת שנצייר תחבר שני רכיבי קשירות (שכן אילו הייתה מחברת שני צמתים באותו רכיב קשירות היה נסגר מעגל). לכן כל קשת שנוסיף יקטין את מספר רכיבי הקשירות ב – 1. לפיכך לאחר ציור 10 הקשתות אנו נותרים עם 7 רכיבי קשירות.

2.	הוכיחו כי אם בגרף פשוט מתקיים לכל זוג קודקודים לא סמוכים  x,y: , אז הגרף קשיר.
פתרון: נראה כי קיים מסלול בין כל זוג קודקודים x,y בגרף. אם יש קשת בין x ל –y, אז זהו המסלול ביניהם. אחרת, הם אינם סמוכים. נראה כי קיים קודקוד הסמוך לשניהם. תהי A קבוצת הקודקודים הסמוכים ל – x ו – B קבוצת הקודקודים הסמוכים ל – y. אילו לא קיים צומת הסמוך לשניהם אז הקבוצות A ו – B הן זרות. לכן . אולם  ולכן . סתירה.

4.	נתונים שני עצים  ו -, בעלי אותה קבוצות קודקודים . איחוד שני העצים הוא הגרף , שקבוצות הקשתות שלו היא האיחוד . הוכח כי יש ב-  קודקוד שדרגתו אינה עולה על שלוש. רמז: שים לב למספר הקשתות.
פתרון: נסמן ב – n את מספר הקודקודים ב- V. בעץ יש  קשתות. לכן באיחוד העצים יש לכל היותר קשתות. לפיכך סכום הדרגות בגרף הוא  לכל היותר . אילו הייתה דרגת כל קודקוד לפחות 4, סכום הדרגות היה לפחות 4n.

5.	הוכח כי אם צובעים את קשתות  ב – 8 צבעים אז יש בגרף מעגל פשוט שכל קשתותיו באותו צבע.
פתרון: נניח בשלילה שיש צביעה של קשתות K17 ב – 8 צבעים כך שאין מעגל מונוכרומטי. תהי Ei קבוצת כל הקשתות הצבועות בצבע i. בגרף  אין מעגלים שאם לא כן היה קיים מעגל מונוכרומטי. לכן מספר הקשתות בגרף הוא לכל היותר 16. דבר זה נכון לכל i, ולכן יש לכל היותר 16·8=128  קשתות בגרף. זו סתירה לכך שב – K17 יש 136 קשתות.

7.	בכמה עצים ממוספרים על קבוצת הקודקודים 1,2,...,10
א.	הקודקודים 1,2,3 הם עלים.
פתרון: כמספר המחרוזות באורך 8 בהם התווים 1,2,3 לא מופיעים, כלומר 78 .

ב.	הקודקודים 7,8 אינם עלים.
פתרון: מספר המחרוזות הכולל הוא 108. מספר המחרוזות בהם 7 לא מופיע הוא 98 (זהו מספר העצים בהם קודקוד 7 הוא עלה). גם מספר המחרוזות בהם 8 לא מופיע הוא 98 (זהו מספר העצים בהם קודקוד 8 הוא עלה). מספר המחרוזות בהם 7 ו – 8 הם לא מופיעים הוא 88 (זהו מספר העצים בהם קודקודים 7 ו – 8 הם עלים). מהכלה והדחה מתקבל הפתרון: 108-2·98+88.

ג.	הקודקודים 1,2,3 הם עלים, הקודקודים 7,8 אינם עלים.
פתרון: בדומה לפתרון הסעיף הקודם: 78-2·68+58

8.	בכמה עצים ממוספרים על n קודקודים מספר העלים הוא בדיוק
א.	2
פתרון: יש  אפשרויות לבחור שני עלים. יתר הקודקודים צריכים להופיע בדיוק פעם אחת. יש  אפשרויות לסדר אותם במחרוזת לכן הפתרון הוא: .

ב.	3
פתרון: כמספר המחרוזות בהם יש 3 קודקודים שלא מופיעים, אחד שמופיע פעמיים וכל השאר פעם אחת. יש  אפשרויות לבחור 3 עלים, יש (n-3) אפשרויות לבחור קודקוד שיופיע פעמיים ויש -  מחרוזות בהם הקודקוד הנבחר מופיע פעמיים. לכן הפתרון הוא .

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

ד.	n-1
פתרון: עבור n > 2, התשובה היא: כמספר המחרוזות באורך n-2 המורכבות מתו בודד, כלומר n. תשובה זו נכונה גם כאשר n = 1 (כלומר, יש עץ אחד על קבוצה של קודקוד בודד שיש בו אפס עלים). אולם, עבור n = 2 התשובה היא אפס (אין עצים על קבוצה של שני קודקודים שיש בהם עלה אחד).

ה.	n-2
פתרון: עבור n > 2, התשובה היא: כמספר המחרוזות שבהם מופיעים שני תוים, כלומר . תשובה זו נכונה גם עבור n = 1 (שכן ). עבור n = 2, התשובה היא אפס.

ו.	n-3
פתרון: עבור n > 2, התשובה היא: כמספר המחרוזות שבהם מופיעים שלושה תוים. מהכלה והפרדה התשובה היא . תשובה זאת נכונה גם כאשר n מקבל את הערכים 1 או 2 (שכן ).