לפניכם גרף לא מכוון G=(V, E).

(1) האם הגרף קשיר? נמקו.

(2) האם הגרף מכיל מעגל? אם כן, ציינו מעגל אחד בגרף. אם לא, נמקו.

(3) אם הגרף דו־צדדי – הציגו חלוקה אפשרית (וציינו את הצמתים בכל צד).

אם הגרף אינו דו־צדדי, הסירו מספר מינימלי של קשתות כך שהגרף שיתקבל יהיה דו־צדדי והציגו חלוקה אפשרית לשתי קבוצות.

נתון גרף לא מכוון G=(V,E) המיוצג ע"י מטריצת הסמיכויות הבאה:

מקרא: 1 – קיימת קשת, 0 – לא קיימת קשת.

שרטטו את הגרף G המיוצג על ידי המטריצה הנתונה.

כמה רכיבי קשירות יש בגרף G? נמקו.

הציגו את המסלול הקצר ביותר מהקודקוד a לקודקוד f.

האם קיימת קשת שהסרתה מהגרף G תגדיל את מספר רכיבי הקשירות ב־1? אם כן, ציינו את הקשת.

האם קיימת קשת שהסרתה מהגרף G לא תשנה את מספר רכיבי הקשירות בגרף? אם כן, ציינו את הקשת.