להלן גרף G=(V,E) שאינו מכוון:

i. האם הגרף קשיר? נמקו.

ii. האם הגרף דו־צדדי? נמקו.

iii. האם הגרף מלא (שלם)? נמקו.

iv. האם הגרף הוא עץ? נמקו.

מהנדס העיר הגדיר את המעבר בין השכונות a,b,c,d,e,f על פי הגרף שלהלן:

i. שרטטו מטריצת סמיכויות.

ii. האם הגרף הוא גרף קשיר חזק? נמקו.

iii. תושב העיר צריך להגיע משכונה אחת לשכונה אחרת. לשם כך עליו לבדוק אם קיים מסלול בין שתי השכונות ואם קיים, הוא רוצה למצוא מסלול כלשהו המגיע לאותה שכונה. מהו האלגוריתם שעליו להשתמש בו למטרות אלה? הסבירו.

iv. הפעילו את האלגוריתם שכתבתם עליו בסעיף הקודם כדי למצוא את המסלול משכונה b לשכונה c. כתבו את המסלול שמצאתם.

יש לבצע מעקב מפורט בכל שלב בהתאם לאלגוריתם שהפעלתם.