מתמטיקה דיסקרטית ח (2023 — מרחב למידה אישי

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

מושגי יסוד בקישוריות גרפים

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

גרף קשיר: גרף לא מכוון שבו קיים מסלול בין כל שני קודקודים.

רכיב קשיר: תת-גרף קשיר מקסימלי בגרף נתון.

סוגי קישוריות

קשירות קודקודית (Vertex Connectivity)

מספר הקודקודים המינימלי שצריך להסיר כדי לנתק את הגרף (או להפוך אותו לטריוויאלי). מסומן כ-κ(G).

קשירות קשתית (Edge Connectivity)

מספר הקשתות המינימלי שצריך להסיר כדי לנתק את הגרף. מסומן כ-λ(G).

קשירות k

גרף G נקרא k-קשיר קודקודית (או קשתית) אם κ(G) ≥ k (או λ(G) ≥ k). מבטא את "חוזק" הקישוריות של הגרף.

חתך קודקודי (Vertex Cut): קבוצת קודקודים S שבהסרתה הגרף הופך ללא קשיר.

חתך קשתי (Edge Cut): קבוצת קשתות E' שבהסרתן הגרף הופך ללא קשיר.

רשתות זרימה ומשפט זרימה מקסימלית-חתך מינימלי

רשתות זרימה הן מודל גרפי מכוון שבו לכל קשת יש קיבולת, והמטרה היא למצוא את הזרימה המקסימלית ממקור (source) לבור (sink).

רשת זרימה (Flow Network): גרף מכוון G=(V,E) עם קודקוד מקור s, קודקוד בור t, ופונקציית קיבולת c(u,v) ≥ 0 לכל קשת (u,v) ∈ E.

זרימה (Flow): פונקציה f: E → ℝ המקיימת:

קיבולת: 0 ≤ f(u,v) ≤ c(u,v) לכל (u,v) ∈ E.
שימור זרימה: לכל קודקוד v ≠ s, t, מתקיים Σ_u f(u,v) = Σ_w f(v,w) (סך הזרימה הנכנסת שווה לסך הזרימה היוצאת).

ערך הזרימה הוא Σ_v f(s,v) - סך הזרימה היוצאת מהמקור.

חתך S-T (S-T Cut): חלוקה של קודקודי הגרף לשתי קבוצות (S, T) כך ש-s ∈ S ו-t ∈ T. קיבולת החתך היא סכום קיבולות הקשתות מ-S ל-T.

משפט זרימה מקסימלית-חתך מינימלי (Max-Flow Min-Cut Theorem): משפט זה הוא אבן יסוד בתורת הרשתות ומופיע כמעט בכל בחינה. הוא קובע כי ערך הזרימה המקסימלית ברשת זרימה שווה לקיבולת המינימלית של כל חתך S-T. הבנת המשפט, הוכחתו האינטואיטיבית (באמצעות גרף שאריתי ומסלולי שיפור) ויישומיו היא קריטית.

אלגוריתמים ויישומים

פתרון בעיות זרימה מקסימלית מתבצע באמצעות אלגוריתמים יעילים.

גרף שאריתי (Residual Graph): גרף המייצג את הקיבולת הנותרת בקשתות לאחר זרימה מסוימת, ומאפשר למצוא מסלולי שיפור (augmenting paths).

מסלול שיפור (Augmenting Path): מסלול מהמקור לבור בגרף השאריתי, שדרכו ניתן להגדיל את הזרימה הכוללת.

אלגוריתמים לזרימה מקסימלית

אלגוריתם פורד-פלקרסון (Ford-Fulkerson)

אלגוריתם איטרטיבי המוצא מסלולי שיפור בגרף השאריתי ומעדכן את הזרימה עד שלא ניתן למצוא מסלולים נוספים. יעילותו תלויה בבחירת מסלולי השיפור.

אלגוריתם אדמונדס-קארפ (Edmonds-Karp)

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

יישומים נפוצים כוללים הקצאת משימות, תכנון רשתות תקשורת, בעיות שידוך (matching) ובעיות כיסוי.

משפט מנגר והקשר לקישוריות

משפט מנגר מקשר בין קישוריות לבין מספר המסלולים הזרים בגרף, ומהווה הכללה של משפט זרימה מקסימלית-חתך מינימלי לגרפים לא מכוונים.

מסלולים זרים קודקודית (Vertex-Disjoint Paths): מסלולים בין שני קודקודים s ו-t שאין להם קודקודים משותפים למעט s ו-t עצמם.

מסלולים זרים קשתית (Edge-Disjoint Paths): מסלולים בין שני קודקודים s ו-t שאין להם קשתות משותפות.

משפט מנגר (Menger's Theorem):

גרסא קודקודית: מספר המסלולים הזרים קודקודית המקסימלי בין שני קודקודים s ו-t שווה למספר הקודקודים המינימלי שצריך להסיר כדי לנתק את s מ-t.
גרסא קשתית: מספר המסלולים הזרים קשתית המקסימלי בין שני קודקודים s ו-t שווה למספר הקשתות המינימלי שצריך להסיר כדי לנתק את s מ-t.

משפט זה מדגיש את הקשר העמוק בין קישוריות הגרף לבין יכולתו להעביר "זרימה" או "מידע" במסלולים מקבילים.

שאלות לדיון

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

נקודות לתשובת מודל

לשאלה 1: הגדרת גרף מכוון עם קודקודים המייצגים ערים/צמתים וקשתות המייצגות כבלים. קיבולת הקשתות תהיה 1 (או מספר הכבלים בין הערים). המקור והבור יהיו הערים הרצויות. חתך מינימלי ייתן את מספר הכבלים המינימלי לניתוק.
לשאלה 2: משפט מנגר קובע שמספר המסלולים הזרים (קודקודית או קשתית) שווה לקישוריות. רשת עמידה תהיה בעלת קישוריות גבוהה, כלומר, מספר רב של מסלולים זרים בין נקודות קריטיות, מה שמבטיח שגם אם מספר רכיבים ייכשלו, עדיין תישמר קישוריות. דוגמה: רשת אינטרנט עם נתיבים חלופיים רבים.
לשאלה 3: פורד-פלקרסון: כללי יותר, לא מבטיח סיום בזמן פולינומי אם הקיבולות אינן שלמות או אם בחירת המסלולים אינה אופטימלית. אדמונדס-קארפ: מקרה פרטי של פורד-פלקרסון, בוחר תמיד מסלול שיפור קצר ביותר (BFS), מבטיח סיום בזמן פולינומי (O(VE^2)). נעדיף אדמונדס-קארפ לרוב בשל יעילותו המובטחת.
לשאלה 4: ההוכחה האינטואיטיבית מתבססת על כך שכל זרימה היא לכל היותר קיבולת של כל חתך (כי היא חייבת לעבור דרכו). מצד שני, כאשר לא ניתן למצוא יותר מסלולי שיפור בגרף השאריתי, הדבר יוצר חתך S-T שבו כל הקשתות מ-S ל-T רוויות (או שקיבולתן אפס בגרף השאריתי). קיבולת חתך זה שווה לזרימה הכוללת שהושגה, ובכך הוא מהווה חתך מינימלי.

מצאתם טעות או שחסר משהו?