מסלול אלגוריתמים: גרפים מדעי המחשב לכיתה י״ב

בנושא הזה 9 שיעורים. כך הם מתחילים:

1. היכרות עם גרפים

   פתיחת מסלול "אלגוריתמים" (פרק 1 - היכרות עם גרפים): גרף G=(V,E), קודקודים וקשתות, גרף מכוון ולא מכוון, דרגה (וסכום הדרגות = 2|E|), מסלול ומעגל, קשירות ורכיבי קשירות, עץ ויער, גרף דו-צדדי, גשר, וגרף ממושקל.

2. ייצוג גרפים: מטריצה ורשימות

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

3. BFS ומסלולים קצרים

   מסלולים קצרים ביותר ממקור יחיד בגרף לא ממושקל (פרק 3): אלגוריתם BFS עם תור, המרחקים d(v) וההורים π(v), עץ BFS, סדר הביקור לפי רשימות הסמיכויות, ושימושים - קשירות ובדיקת דו-צדדיות.

4. אלגוריתם דייקסטרה

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

5. משקלות שליליים: בלמן-פורד

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

6. סריקה לעומק - DFS

   סריקה לעומק - DFS (פרק 6): הרעיון ("ללכת עד הסוף ולחזור"), המימוש הרקורסיבי, זמני גילוי וסיום, עץ DFS, קשתות עץ וקשתות אחורה, זיהוי מעגלים ורכיבי קשירות, רכיבי קשירות חזקה (רק״ח) בגרף מכוון וגרף העל, והשוואה ל-BFS.

7. מיון טופולוגי ומסלולים בגמ״ל

   מיון טופולוגי ומסלולים קצרים בגמ״ל - גרף מכוון ללא מעגלים (פרק 7): מהו סדר טופולוגי ומתי הוא קיים, שני אלגוריתמים (הסרת קודקודים עם דרגת כניסה 0; סדר יורד של זמני סיום ב-DFS), ומסלולים קצרים (וארוכים) בגמ״ל בזמן ליניארי - גם עם משקלות שליליים.

8. עץ פורש מינימלי

   עץ פורש מינימלי (פרק 8): עץ פורש, משקל של עץ, אלגוריתם קרוסקל (קשתות לפי משקל, בלי ליצור מעגל) ובהרחבה אלגוריתם פרים (גידול עץ מקודקוד), תכונת החתך ותכונת המעגל, יחידות העץ, וההבדל מעץ מסלולים קצרים.

9. חזרה: טענות ודוגמאות נגדיות

   חזרה על מסלול האלגוריתמים: טענות "נכון / לא נכון" עם נימוק או דוגמה נגדית (סגנון הבגרות), ושאלות מעורבות על ייצוג, BFS, DFS, דייקסטרה, בלמן-פורד, מיון טופולוגי ועץ פורש מינימלי.

→ עצים בינארייםמבחני תרגול 899271 ←