תרגיל 12 – מתמטיקה בדידה

1.	כמה רכיבי קשירות יש לגרף חסר מעגלים בן 17 קודקודים ו – 10 קשתות?

2.	הוכיחו כי אם בגרף פשוט מתקיים לכל זוג קודקודים לא סמוכים  x, y: , אז הגרף קשיר.

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

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

5.	הוכח כי אם צובעים את קשתות  ב – 8 צבעים אז יש בגרף מעגל פשוט שכל קשתותיו באותו צבע.

6.	מהו העץ המתאים למחרוזת 1821531 עפ"י קוד Pr�fer?

7.	בכמה עצים על קבוצת הקודקודים {V={1,2,...,10
א.	הקודקודים 1,2,3 הם עלים.
ב.	הקודקודים 7,8 אינם עלים.
ג.	הקודקודים 1,2,3 הם עלים, הקודקודים 7,8 אינם עלים.

8.	בכמה עצים ממוספרים על n קודקודים מספר העלים הוא בדיוק
א. 2	ב. 3	ג. 4	ד. n-1	     ה. n-2	ו. n-3

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

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

			בהצלחה