מתמטיקה בדידה: תורת הקבוצות, קומבינטוריקה ותורת הגרפים

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

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

הגדרת גרף

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

גרף (Graph): זוג סדור $G = (V, E)$, כאשר $V$ היא קבוצה לא ריקה וסופית של קודקודים (Vertices), ו-$E$ היא קבוצה של צלעות (Edges) המחברות בין זוגות קודקודים.

קודקוד (Vertex / Node): יחידה בסיסית בגרף, המייצגת אובייקט או ישות.

צלע (Edge / Link): קשר או יחס בין שני קודקודים.

סוגי גרפים

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

גרף לא מכוון (Undirected Graph)

בגרף לא מכוון, צלע מייצגת קשר סימטרי בין שני קודקודים. אם קודקוד $u$ מחובר ל-$v$, אז גם $v$ מחובר ל-$u$. הצלעות הן קבוצות של שני קודקודים {u,v}.

גרף מכוון (Directed Graph / Digraph)

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

גרף פשוט (Simple Graph)

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

גרף מרובה (Multi-graph)

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

לולאה (Loop): צלע המחברת קודקוד לעצמו.

קשתות מקבילות (Parallel Edges): שתי צלעות או יותר המחברות את אותם שני קודקודים.

דרגה וקשרים

דרגה (Degree): מספר הצלעות הצמודות לקודקוד. בגרף מכוון מבחינים בין דרגת כניסה (in-degree) לדרגת יציאה (out-degree).

שכנים (Neighbors): קודקודים המחוברים לקודקוד נתון באמצעות צלע.

קשת צמודה (Incident Edge): צלע המחברת קודקוד מסוים.

משפט לחיצות הידיים (Handshaking Lemma): משפט יסוד בתורת הגרפים, הקובע שבכל גרף לא מכוון, סכום דרגות כל הקודקודים שווה לפעמיים מספר הצלעות. כלומר, $\sum_{v \in V} \deg(v) = 2|E|$. משפט זה קריטי להבנה ולפתרון שאלות רבות בבחינה, במיוחד אלו העוסקות בקשר בין מספר הקודקודים, הצלעות והדרגות. הוא גם מרמז שתמיד קיים מספר זוגי של קודקודים בעלי דרגה אי-זוגית.

מסלולים, מעגלים וקשירות

מסלולים ומעגלים

מושגים אלו מתארים את אופן התנועה או הקשרים בתוך הגרף.

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

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

אורך (Length): מספר הצלעות במסלול או במעגל.

מהלך (Walk)

סדרה של קודקודים וצלעות, שבה קודקודים וצלעות יכולים לחזור על עצמם.

שביל (Trail)

מהלך שבו כל הצלעות שונות (אך קודקודים יכולים לחזור על עצמם).

מסלול (Path)

שביל שבו כל הקודקודים שונים (ולכן גם כל הצלעות שונות).

מעגל (Cycle)

מסלול שבו הקודקוד ההתחלתי והסופי זהים, וכל שאר הקודקודים שונים.

מסלול סגור (Circuit)

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

קשירות

קשירות מתארת את מידת החיבוריות בגרף.

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

רכיב קשירות (Connected Component): תת-גרף מקסימלי קשיר בגרף לא מכוון. כל גרף לא מכוון ניתן לחלוקה לרכיבי קשירות זרים.

גרפים מיוחדים

דוגמאות נפוצות

היכרות עם גרפים מיוחדים אלו חיונית להבנת תכונות גרפים כלליות ולפתרון בעיות.

גרף שלם (Complete Graph, $K_n$): גרף פשוט לא מכוון שבו כל זוג קודקודים שונים מחובר בצלע אחת ויחידה. לגרף $K_n$ יש $n$ קודקודים ו-$n(n-1)/2$ צלעות.

גרף מסלול (Path Graph, $P_n$): גרף המורכב מ-$n$ קודקודים המחוברים ברצף ליצירת מסלול יחיד באורך $n-1$.

גרף מעגל (Cycle Graph, $C_n$): גרף המורכב מ-$n$ קודקודים המחוברים במעגל יחיד באורך $n$. (לרוב, $n \ge 3$).

גרף דו-צדדי (Bipartite Graph): גרף שבו ניתן לחלק את קבוצת הקודקודים לשתי קבוצות זרות $V_1$ ו-$V_2$, כך שכל צלע בגרף מחברת קודקוד מ-$V_1$ לקודקוד מ-$V_2$ (ואין צלעות בתוך $V_1$ או בתוך $V_2$).

שאלות לדיון

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

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

הבדל בין גרפים מכוונים ללא מכוונים: כיווניות הצלעות. בגרף מכוון הקשר אסימטרי (לדוגמה: עקוב אחרי בטוויטר), בלא מכוון הקשר סימטרי (לדוגמה: חברות בפייסבוק).
הבדל בין מסלול למעגל: מסלול הוא סדרה של קודקודים שונים (למעט אולי קצוות), מעגל הוא מסלול שבו הקודקוד ההתחלתי והסופי זהים. לא כל מעגל הוא מסלול (במובן שקודקודי הקצה זהים, אך בדרך כלל "מסלול" מתייחס לקודקודים שונים). כל מעגל מכיל מסלול.
דרגות זוגיות: לפי משפט לחיצות הידיים, סכום הדרגות הוא $2|E| = 2 \times 10 = 20$. אם כל הדרגות זוגיות, סכומן יהיה זוגי, מה שמתקיים. לכן, כן, ייתכן שכל הקודקודים יהיו בעלי דרגה זוגית.
זיהוי גרף דו-צדדי: גרף הוא דו-צדדי אם ורק אם אין בו מעגלים באורך אי-זוגי. ניתן לזהות זאת באמצעות אלגוריתם כמו BFS או DFS, תוך צביעת הקודקודים לסירוגין בשני צבעים. אם נתקלים בצלע המחברת שני קודקודים מאותו צבע, הגרף אינו דו-צדדי.

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