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

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

מבוא: מהו גרף?

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

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

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

קשת (Edge / Link): חיבור בין שני קודקודים בגרף, המייצג קשר או יחס ביניהם. מסומן לרוב כזוג סדור או לא סדור של קודקודים (לדוגמה, (u,v) או {u,v}).

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

סוגי גרפים עיקריים

גרף לא מכוון מול גרף מכוון

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

גרף פשוט מול מולטי-גרף

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

גרף משוקלל מול לא משוקלל

גרף לא משוקלל: לכל הקשתות יש "משקל" זהה (לרוב 1), או שאין להן משקל כלל. גרף משוקלל: לכל קשת משויך ערך מספרי (משקל), שיכול לייצג מרחק, עלות, קיבולת וכו'.

מונחי יסוד נוספים

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

מסלול (Path): סדרה של קודקודים v₀, v₁, ..., v_k כך שקיימת קשת בין כל v_i ל-v_i+1. אורך המסלול הוא מספר הקשתות בו.

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

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

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

$\sum_{v \in V} \text{deg}(v) = 2|E|$

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

ייצוג גרפים

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

מטריצת סמיכויות (Adjacency Matrix)

מטריצה בגודל |V|x|V| שבה התא (i,j) מכיל 1 אם קיימת קשת מהקודקוד i לקודקוד j, ו-0 אחרת. בגרף משוקלל, התא יכיל את משקל הקשת. יתרונות: בדיקת קיום קשת ב-O(1), קל ליישום. חסרונות: דורש זיכרון של O(|V|²) גם לגרפים דלילים (מעט קשתות).

רשימת סמיכויות (Adjacency List)

מערך של |V| רשימות, כאשר הרשימה במקום i מכילה את כל הקודקודים הסמוכים לקודקוד i. בגרף משוקלל, כל פריט ברשימה יכיל גם את משקל הקשת. יתרונות: יעיל לגרפים דלילים (דורש O(|V|+|E|) זיכרון), קל לעבור על כל השכנים של קודקוד. חסרונות: בדיקת קיום קשת דורשת O(deg(v)) זמן.

יישומים ודוגמאות

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

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

שאלות לדיון

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

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

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

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