הגרף הלא מכוון G=(V,E) לסעיף א
קודקודים: a, b, c, d, e
קשתות: a-b, b-c, a-c, a-d, c-e, d-e
מטריצת סמיכויות לגרף G=(V,E) לסעיף ב
a b c d e f
a 0 1 1 0 0 0
b 1 0 0 1 0 0
c 1 0 0 1 1 0
d 0 1 1 0 0 0
e 0 0 1 0 0 1
f 0 0 0 0 1 0
(מקרא: 1 – קיימת קשת, 0 – לא קיימת קשת.)
לפניכם גרף לא מכוון G=(V,E) (חמישה קודקודים a,b,c,d,e; שש קשתות a-b,b-c,a-c,a-d,c-e,d-e -- משולש a-b-c עם קודקודים נוספים d,e המחוברים במסלול a-d-e-c). (1) האם הגרף קשיר? נמקו. (2) האם הגרף מכיל מעגל? אם כן, ציינו מעגל אחד. אם לא, נמקו. (3) אם הגרף דו-צדדי, הציגו חלוקה אפשרית (ציינו את הצמתים בכל צד). אם הגרף אינו דו-צדדי, הסירו מספר מינימלי של קשתות כך שהגרף שיתקבל יהיה דו-צדדי, והציגו חלוקה אפשרית לשתי קבוצות.
נתון גרף לא מכוון G=(V,E) המיוצג ע"י מטריצת סמיכויות (קודקודים a..f; שורה a: b,c; שורה b: a,d; שורה c: a,d,e; שורה d: b,c; שורה e: c,f; שורה f: e -- סימטרית). (1) שרטטו את הגרף G המיוצג על ידי המטריצה הנתונה. (2) כמה רכיבי קשירות יש בגרף G? נמקו. (3) הציגו את המסלול הקצר ביותר מהקודקוד a לקודקוד f. (4) האם קיימת קשת שהסרתה מהגרף G תגדיל את מספר רכיבי הקשירות ב-1? אם כן, ציינו את הקשת. (5) האם קיימת קשת שהסרתה מהגרף G לא תשנה את מספר רכיבי הקשירות בגרף? אם כן, ציינו את הקשת.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.