בשאלה זו שני סעיפים, א-ב, שאין ביניהם קשר. יש לענות על שני הסעיפים.

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

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

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

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

(4) האם הגרף הוא עץ? נמקו.

חברת תעופה מפעילה בשגרה קווי תעופה בין המדינות A, B, C, D, E, F, G, H, I על פי הסרטוט שלהלן:

סרטטו את רשימת הסמיכות המייצגת את קווי התעופה בין המדינות.

בעקבות שינויים בחברת התעופה הוחלט לבטל כמה מקווי התעופה במדינות שלהלן:

מדינה G — ביטול הטיסות הנכנסות והטיסות היוצאות

מדינה H — ביטול הטיסות היוצאות למדינה F

מדינה D — ביטול הטיסות היוצאות למדינה C

מדינה A — ביטול הטיסות היוצאות למדינה E

סרטטו את רשימת הסמיכות המתקבלת לאחר הביטולים המצוינים לעיל.

אביטל צריכה להגיע ממדינה מסוימת למדינה אחרת.

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

מהו האלגוריתם שעליה להשתמש בו למטרות אלה? הסבירו.

הערה

אם יש כמה אלגוריתמים מתאימים, בחרו באחד מהם.

הפעילו את האלגוריתם שכתבתם עליו בסעיף ב(3)I כדי למצוא את מסלול הטיסה ממדינה A למדינה E. כתבו את מסלול הטיסה שמצאתם.

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