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

לפניכם גרף לא מכוון 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 לא תשנה את מספר רכיבי הקשירות בגרף? אם כן, ציינו את הקשת.