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

פורסם בתאריך 25 בינואר 2012 על ידי gadial

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

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

האופן הטבעי להכליל את הבעיה הוא לדבר על גרף (אניח שהקוראים מכירים את המושג הזה). המשבצות הן צמתים, וקשת בין שני צמתים מייצגת משבצות שכנות. בצורה הזו אפשר לייצג לוח \(n\times n\) ריבועי כלשהו; וגם לוחות מלבניים; ועם משושים או משולשים; או תלת ממדיים, או כל דבר בעצם. אני לא אניח שום דבר על הגרף שאני תוקף.

הדבר הראשון שצריך לשים לב אליו הוא שאמנם טבעי לחשוב על המשחק בגישה "סדרתית" ("קודם אלחץ כאן ואז אלחץ שם") אבל זה מיותר לגמרי. אין שום חשיבות לסדר שבו לוחצים על משבצות, וגם אין שום צורך ללחוץ על משבצת יותר מפעם אחת (לחיצה כפולה פשוט מנטרלת את האפקט של הלחיצה הראשונה; אם לחצנו פעמיים, גם אם חלף פרק זמן גדול בין הלחיצות ועשינו דברים אחרים בלוח, זה שקול לחלוטין לכך שמעולם לא היינו לוחצים וחסל). כלומר, הדרך ה"נכונה" לנצח במשחק היא פשוט ללחוץ בו זמנית על קבוצה מסויימת של צמתים, וזהו. פורמלית, אם \(V\) היא קבוצת צמתי הגרף, אנו מחפשים תת-קבוצה \(S\subseteq V\) כך שלכל צומת \(v\notin S\) יש מספר אי זוגי של שכנים מתוך \(S\), ואילו לכל צומת \(v\in S\) יש מספר זוגי של שכנים מתוך \(S\) (זוגי, כי אנחנו נלחץ גם על \(v\) עצמו, ואנחנו רוצים שכל הלחיצות שלנו על השכנים של \(v\) יבטלו אלו את אלו בכל מה שנוגע ל-\(v\)).

כאן אני שולף מהשרוול שפן בדמות טענה לא טריוויאלית לגמרי בתורת הגרפים – לכל גרף אפשר לפרק את קבוצת הצמתים שלו לשתי קבוצות זרות \(V_{1},V_{2}\) כך שבתת-הגרפים המושרים על \(V_{1},V_{2}\) כל הצמתים הם מדרגה זוגית. תכף אוכיח את הטענה הזו אבל בואו נבין איך נעזרים בה כדי להראות שקיימת בגרף קבוצה \(S\) כמו שאנחנו רוצים. הרעיון הוא לבצע בניית עזר – לקחת את הגרף של המשחק, ולהוסיף צומת חדשה \(u\) שמחוברת לכל צומת בגרף שדרגתו זוגית. כעת אפשר לחלק את הגרף לשתי קבוצות \(V_{1},V_{2}\) כאמור לעיל. בואו נניח ש-\(u\in V_{2}\), בלי הגבלת הכלליות; אז נגדיר \(S=V_{1}\).

כעת, מה הולך כאן? מצד אחד, הדרגה של כל צומת בתת-הגרף שמושרה על \(S\) היא זוגית, מה שאומר בדיוק שלכל \(v\in S\) יש מספר זוגי של שכנים ב-\(S\); מצד שני, אם \(v\notin S\) והוא מחובר ל-\(u\), זה אומר שהוא מחובר למספר זוגי של צמתים שאינם ב-\(S\) כולל הצומת החדש \(u\). זה שאומר ש-\(v\) מחובר למספר אי זוגי של צמתים שאינם ב-\(S\) ואינם \(u\). כעת מגיע טיעון המחץ: את \(u\) חיברנו רק לצמתים שהיו מדרגה זוגית מלכתחילה, ולכן אם \(v\) מחובר למספר אי זוגי של צמתים שאינם מ-\(S\) ודרגתו לפני הוספת \(u\) לגרף הייתה זוגית, הוא חייב להיות מחובר למספר אי זוגי של צמתים מ-\(S\). אם לעומת זאת \(v\) לא מחובר ל-\(u\) זה אומר שדרגתו בגרף המקורי הייתה אי זוגית, וכעת הוא מחובר למספר זוגי של צמתים שאינם ב-\(S\) ולכן גם כאן הוא חייב להיות מחובר למספר אי זוגי של צמתים מ-\(S\). סוף המשחק.

טוב ויפה, אבל איך מוצאים פירוק ל-\(V_{1},V_{2}\) שכזה? אם בגרף שלנו כל הצמתים מדרגה זוגית אז \(V_{1}=V,V_{2}=\emptyset\) הוא פירוק טריוויאלי שכזה (ועל הדרך יש בגרף מעגל אוילרי) אבל אפשר לצפות שבאופן כללי יהיה בגרף איזה צומת \(v\) שהוא מדרגה לא זוגית. אם כן, הופס! נוציא את \(v\) מהגרף.

למרבה הצער, זה לא מספיק. נצטרך לעשות התחכמות נוספת שחשיבותה תתברר בקרוב. בואו נסמן ב-\(S\) את קבוצת השכנים של \(v\) בגרף; לכל זוג צמתים \(x,y\in S\), אם יש קשת בין \(x,y\) נוריד אותה מהגרף, ואם אין קשת – נוסיף אותה לגרף.

אם כן, על ידי הוצאת \(v\) קיבלנו גרף קטן יותר (עם פחות צמתים) ולכן אפשר לשלוף מהכיס את קסם ההוכחה באינדוקציה ולטעון שבגרף הקטן יותר יש חלוקה לשתי קבוצות \(W_{1},W_{2}\) כך שדרגת כל צומת בתת-הגרף שמושרה על ידי כל אחת מהקבוצות היא זוגית. מה שנרצה לעשות הוא להחזיר את \(v\) לאחת מהקבוצות הללו, אבל לאיזו מהן? מכיוון ש-\(S\) אי-זוגית, בהכרח \(S\cap W_{1}\) אי זוגית או \(S\cap W_{2}\) אי זוגית (אחרת היה אפשר לכתוב מספר אי זוגי כסכום שני מספרים זוגיים). בואו נניח ש-\(S\cap W_{1}\) זוגית – אני טוען שלהוסיף את \(v\) לקבוצה הזו יסיים את העסק. כלומר, נגדיר \(V_{1}=W_{1}\cup\left\{ v\right\} \) ו-\(V_{2}=W_{2}\). נותר רק להבין למה זה עובד.

ברור כי כל צמתי \(V\) שלא היו שייכים ל-\(S\) ואינם \(v\) עדיין מקיימים את תכונת הזוגיות הנדרשת – מבחינתם לא שיניתי כלום. לעומת זאת, צמתי \(S\cap W_{1}\) חוו טראומה כפולה – גם חיברו להם את \(v\) (ובכך שינו להם את הזוגיות) וגם הפכו את הקשתות בינם לבין עצמם. כל איבר של \(S\) היה מחובר למספר אי זוגי של שכנים מתוך \(S\) ב-\(W_{1}\), מה שאומר שמספר השכנים מתוך \(S\) ב-\(W_{1}\) שהוא לא היה מחובר אליהם היה בעל סימן הפוך, ולכן אחרי היפוך הקשתות הזוגיות משתנה ומבטלת את שינוי הזוגיות ש-\(v\) גרם לו.

מבלבל? בהחלט. בואו נראה דוגמת צעצוע. נניח ש-\(S\cap W_{1}\) הייתה מגודל 6. נסתכל על צומת \(x\in S\cap W_{1}\) כלשהו. יש לו בדיוק 5 שכנים פוטנציאליים שגם הם ב-\(S\cap W_{1}\). נניח שכרגע יש לו קשת ל-2 מהם, זה אומר שאין קשת ל-3, ואחרי שנהפוך את זה (נמחק את הקשתות הקיימות וניצור את כל הקשתות שלא היו קודם) הזוגיות של הדרגה של \(x\) תשתנה בשל כך (קודם היא הייתה זוגית, עכשיו היא כבר לא). אם לעומת זאת הייתה קשת מ-\(x\) רק לצומת אחד אחר ב-\(S\cap W_{1}\) אחרי השינוי תהיה קשת ל-4: שוב שינוי בזוגיות. תוסיפו לכך את השינוי בזוגיות ש-\(v\) גורם לו, וקיבלנו שגם ב-\(V_{1}\) האיבר \(x\) מחובר רק למספר זוגי של צמתים.

עכשיו כבר די ברור מה קורה ב-\(S\cap W_{2}\), אני מקווה. אנחנו לא מוסיפים את \(v\) לשם כך שהוא לא גורם לשום שינוי. מצד שני, גם היפוך הקשתות לא יגרום לשום שינוי, כי לכל צומת \(x\in S\cap W_{2}\) יש מספר שכנים פוטנציאלי זוגי מתוך \(S\cap W_{2}\). לכן: או שקודם \(x\) היה מחובר למספר זוגי, ואחרי השינוי הוא עדיין יהיה מחובר למספר זוגי, או שקודם הוא היה מחובר למספר אי זוגי, ואחרי השינוי הוא עדיין יהיה מחובר למספר אי זוגי. סיימנו.

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

כבר הזכרתי בפוסט על כפל מטריצות את הרעיון לפיו אפשר לייצג גרף באמצעות מטריצה, ובכך להכניס את האלגברה הלינארית לתורת הגרפים בדלת הקדמית. אם הגרף מכיל את הצמתים \(\left\{ v_{1},\dots,v_{n}\right\} \) אז המטריצה, שאסמן \(A\), תהיה מסדר \(n\times n\), כך שהכניסה \(A_{ij}\) שווה 1 אם יש קשת בין \(v_{i}\) ו-\(v_{j}\) ו-0 אחרת. במקרה שלנו הגרף איננו מכוון כך ש-\(A_{ij}=A_{ji}\) – המטריצה סימטרית. מכיוון שהמטריצה מכילה רק 0 ו-1 ואין משמעות לערכים אחרים, הגיוני לחשוב עליה בתור מטריצה מעל השדה הפצפון \(\mathbb{F}_{2}=\left\{ 0,1\right\} \) (אלגברה לינארית תמיד עושים מעל שדה, אחרת תוצאות בסיסיות – כמו זה שאפשר לדרג כל מטריצה – פשוט לא עובדות יותר).

כעת, מה המשמעות של כפל המטריצה \(A\) בוקטור \(x\) כלשהו מעל \(\mathbb{F}_{2}\)? התוצאה תהיה וקטור \(u\) כך ש-\(y_{i}=\sum_{j=1}^{n}A_{ij}x_{j}\), כלומר \(y_{i}\) הוא מספר האינדקסים \(j\in\left\{ 1,\dots,n\right\} \) כך שבו זמנית \(A_{ij}=1\) וגם \(x_{j}=1\). חשבו על \(x_{j}=1\) כאומר "בחרנו ללחוץ על \(x_{j}\) בפתרון שלנו", ואז \(y_{i}\) מתאר בדיוק מה יהיה המצב של הצומת \(v_{i}\) אחרי הלחיצות – אנחנו עוברים על כל צומת שמחובר ל-\(v_{i}\) בקשת ואם רואים שבחרנו ללחוץ עליו, אנחנו מוסיפים 1 ל-\(y_{i}\) ובסופו של דבר (בגלל שאנחנו מעל \(\mathbb{Z}_{2}\)) נקבל ש-\(y_{i}\) מכיל את זוגיות מספר הלחיצות. שימו לב שבשביל שזה יעבוד אנחנו חייבים לקבוע ש-\(A_{ii}=1\) לכל \(i\), כי הרי לחיצה על צומת משנה גם את מצבו שלו (אפשר – וכדאי – לחשוב על כך כאילו יש קשת מהצומת לעצמו וחסל).

אם לסכם, מה שאנחנו רוצים לעשות הוא פשוט לפתור את המשוואה \(Ax=\overline{1}\), כאשר \(\overline{1}\) הוא הוקטור שכולו אחדות (ואם הלוח התחיל ממצב אחר שבו לא כל המשבצות כבויות, פשוט יש משוואה שונה שאפשר לנסות לפתור – אבל במקרה הזה לא מובטח שהיא תהיה פתירה בהכרח; נסו למצוא לוח לא פתיר!). הנה הצלחנו לתרגם עוד בעיה קומבינטורית לגמרי לבעיה בסיסית של אלגברה לינארית. האופן שבו פותרים את הבעיה ידוע – דירוג מטריצות, שניתן לביצוע באופן כללי ביעילות סבירה – ועיקר העניין כרגע הוא בהוכחה שתמיד קיים פתרון. ההוכחה עצמה היא עניין של שורה או שתיים שמבוססות על תוצאות סטנדרטיות באלגברה לינארית – אבל תוצאות שטרם הראיתי, וזו הזדמנות טובה לראות להן דוגמה קונקרטית לפני שמציגים את התורה הכללית.

בתור התחלה, שימו לב ש-\(Ax\) הוא בעצם צירוף לינארי של עמודות \(A\) שמקדמיו נקבעים לפי הכניסות של \(x\). באופן דומה, \(xA\) הוא צירוף לינארי של שורות \(A\) (כרגיל, אני ממשיך במנהג הנלוז שלי לכתוב \(x\) גם לוקטור שורה וגם לוקטור עמודה מתוך הנחה שתבינו מההקשר: \(Ax\) הוא מכפלה של \(A\) בוקטור עמודה, ואילו \(xA\) הוא מכפלה של \(A\) בוקטור שורה). במקרה שלנו \(A\) סימטרית, ולכן אם משהו נמצא בתמונה של \(A\) (כלומר, מתקבל על ידי כפל \(Ax\)) הוא נמצא במרחב שנפרש על ידי שורות \(A\) ולהיפך. נשארנו עם להוכיח ש-\(\overline{1}\) נמצא במרחב שנפרש על ידי שורות \(A\). את המרחב הזה קל במיוחד להבין על ידי התבוננות בגרעין של \(A\), \(\ker A\) – כל הוקטורים \(c\) שמקיימים \(Ac=\overline{0}\).

שימו לב לכך שאם יש לנו \(c\in\ker A\) אז מתקיים \(\left(xA\right)c=x\left(Ac\right)=x\overline{0}=0\). במילים: אם ניקח וקטור כלשהו שנפרש על ידי שורות \(A\) ונכפול אותו עם איבר של \(\ker A\), נקבל 0. אם הרעיון של כפל שני וקטורים מבלבל אתכם, זכרו שהאחד הוא וקטור שורה והשני וקטור עמודה ואפשר לחשוב על הכפל כמכפלה של מטריצה \(1\times n\) במטריצה \(n\times1\). אפשר גם לחשוב על זה כך: אם \(x=\left(x_{1},\dots,x_{n}\right)\) ו-\(y=\left(y_{1},\dots,y_{n}\right)\), אפשר להגדיר מכפלה שלהם על ידי \(x\cdot y=\sum_{i=1}^{n}x_{i}y_{i}\). זה זהה לחלוטין למה שמתקבל מכפל המטריצות, אבל אנחנו כבר לא צריכים להטריד את עצמנו בעניינים כמו מי וקטור שורה ומי וקטור עמודה. המכפלה שהגדרתי כרגע נקראת מכפלה סקלרית של וקטורים, ועוד נפגוש בה בהמשך הפוסטים על אלגברה לינארית.

אם \(x\cdot y=0\) אומרים ש-\(x,y\) אורתוגונליים (מאונכים), מסיבות גאומטריות שיובהרו בפעם אחרת. לעת עתה, מה שראינו הוא שכל איבר במרחב השורות של \(A\) אורתוגונלי לכל איבר בגרעין של \(A\). אני רוצה לטעון שגם ההפך הוא נכון – אם \(x\) אורתוגונלי לכל איבר בגרעין של \(A\), אז \(x\) נמצא במרחב השורות של \(A\).

לב הענין הוא בטענה הבאה: אם \(V\) הוא מרחב וקטורי כלשהו, ואם \(W\) הוא תת מרחב כלשהו, ואם \(W^{\perp}=\left\{ x|\forall y\in W:xy=0\right\} \) הוא אוסף כל האיברים ב-\(V\) שאורתוגונליים לכל איברי \(W\), אז \(\dim V=\dim W+\dim W^{\perp}\). לא אוכיח כרגע את התכונה הזו אבל אני מקווה שאסגור את החשבון באחד מהפוסטים העתידיים. כדי להבין איך הטענה הזו עוזרת לנו, זכרו שמתקיים \(\dim V=\dim\ker A+\dim\mbox{Im}A\) – זו תכונה חשובה של טרנספורמציות לינאריות שכבר הוכחתי בעבר. אם \(W=\ker A\) אז חיבור שני השוויונות מראה לנו שמימד מרחב השורות של \(A\) הוא כמימד \(W^{\perp}\) ומכיוון שידוע לנו שמרחב השורות מוכל ב-\(W^{\perp}\) עולה שהם שווים, מה שמסיים את הוכחת הטענה שאם וקטור אורתוגנלי לכל הגרעין אז הוא במרחב השורות.

כל שנותר לעשות הוא להוכיח שהוקטור \(\overline{1}\) אורתוגונלי לכל איבר בגרעין של \(A\). לצורך כך אנחנו שולפים מהשרוול את התעלול האחרון שלנו, שעובד רק מעל \(\mathbb{F}_{2}\). ניקח וקטור כלשהו \(v\). מהו \(vAv\)? אם נחשב לפי ההגדרה הישירה, נקבל ש-

\(vAv=v\cdot\left(\sum_{i=1}^{n}A_{1i}v_{i},\dots,\sum_{i=1}^{n}A_{ni}v_{i}\right)=\sum_{j=1}^{n}v_{j}\left(\sum_{i=1}^{n}A_{ji}v_{i}\right)=\sum_{i,j=1}^{n}A_{ji}v_{i}v_{j}\)

בהערת אגב אציין שהרעיון הזה, של לכפול מטריצה מימין ומשמאל בוקטור כדי לקבל סקלר, הוא מה שעומד בלב המושג של תבניות בילינאריות שאני מקווה להגיע אליהן בהמשך. מה שקורה כרגע הוא מקרה פרטי שבו העסק פשוט הרבה יותר בגלל שאנחנו מעל \(\mathbb{F}_{2}\) ובגלל ש-\(A\) סימטרית. שימו לב שבגלל הסימטריה הזו, \(A_{ji}=A_{ij}\) ואם \(i\ne j\) אז בסכום מופיעים גם \(A_{ji}v_{j}v_{i}\) וגם \(A_{ij}v_{i}v_{j}\) והסכום של שניהם הוא פשוט \(2A_{ij}v_{j}v_{i}=0\) – אפס, כי אנחנו ב-\(\mathbb{F}_{2}\). לכן מכל הסכום נותר לנו רק \(\sum_{i=1}^{n}A_{ii}v_{i}^{2}\). בגלל שאנחנו מעל \(\mathbb{F}_{2}\), אז \(v_{i}^{2}=v_{i}\) (כי \(v_{i}\in\left\{ 0,1\right\} \)), ולכן קיבלנו שנותר לנו רק \(\sum_{i=1}^{n}A_{ii}v_{i}\) – וזו, במילים אחרות, המכפלה הסקלרית של האלכסון של \(A\) עם הוקטור \(v\).

כעת, אם \(v\) בגרעין של \(A\), אז \(Av=0\) ולכן בוודאי \(vAv=0\), ולכן האלכסון של \(A\) אכן אורתוגונלי לגרעין של \(A\) וההוכחה נסתיימה. אולי היא נראית קצת מסורבלת ומוזרה כעת, אבל למי שבקיא במושגים היא לא דורשת יותר משורה-שתיים.

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

כפל מטריצות – מה, לעזאזל?

פורסם בתאריך 6 באוקטובר 2011 על ידי gadial

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

כשאני אומר "מזכיר", אני מתכוון שמתקיים למשל \(A+B=B+A\) (כלל החילוף), ושמתקיים \(A\left(B+C\right)=AB+AC\) (כלל הפילוג) ומתקיים \(\left(AB\right)C=A\left(BC\right)\) (כלל הקיבוץ, שמתקיים גם לחיבור). בנוסף, עוד לפני שהפוסט הזה יסתיים נראה איך פעולת הכפל של מטריצות מתקשרת הן לפתרון משוואות והן לבעיה שונה לחלוטין – ספירת מסלולים בגרפים.

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

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

בואו ניזכר טיפה מהן מטריצות. מטריצה \(A\) שהיא מסדר \(n\times m\) כוללת \(nm\) "כניסות", כך שכל כניסה היא בעלת שני אינדקסים – הראשון בין 1 ו-\(n\) ("שורה") והשני בין 1 ו-\(m\) ("עמודה"). כל כניסה כוללת מספר כלשהו (לצורך הדיון בינתיים אני מניח שזה מספר ממשי). את הכניסה בשורה \(i\) ועמודה \(j\) מסמנים ב-\(A_{ij}\).

כעת, אם יש לנו שתי מטריצות \(A,B\), כיצד נגדיר מטריצה \(C=A+B\)? בתור התחלה, אף אחד לא אומר שאנחנו בכלל יודעים איך להגדיר כזה דבר; אם \(A,B\) לא שתיהן בדיוק מאותם מימדים – כלומר, עם \(n\) שורות ועם \(m\) עמודות, החיבור כלל לא מוגדר פשוט כי לא ברור איך נכון להגדיר אותו. אבל, אם \(A,B\) שתיהן מאותן מימדים יש הגדרה מאוד טבעית שצצה לראש – נחבר אותן "כניסה כניסה". בדוגמה:

\(\left[\begin{array}{cc}a_{11} & a_{12}\\a_{21} & a_{22}\end{array}\right]+\left[\begin{array}{cc}b_{11} & b_{12}\\b_{21} & b_{22}\end{array}\right]=\left[\begin{array}{cc}a_{11}+b_{11} & a_{12}+b_{12}\\a_{21}+b_{21} & a_{22}+b_{22}\end{array}\right]\)

ובהגדרה פורמלית: אם \(C=A+B\) אז \(C_{ij}=A_{ij}+B_{ij}\).

זה מוביל אותנו גם להגדרה מאוד טבעית ופשוטה של כפל: אם \(C=AB\) אז \(C_{ij}=A_{ij}B_{ij}\). כלומר, כופלים את המטריצות "כניסה כניסה". זו לא ההגדרה שאני רוצה להציג. לא שזו לא הגדרה קיימת; למכפלה "כניסה כניסה" קוראים "מכפלת הדמר", מסמנים אותה ב-\(A\circ B\) ומתעסקים איתה קצת. אלא שהשם "כפל מטריצות" שמור לפעולה שונה, שהיא פי עשרות מונים יותר נפוצה ושימושית.

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

נעבור להגדרה. ראשית כל, בואו נדבר על מטריצות פשוט במיוחד – כאלו שיש להן רק שורה אחת, או רק עמודה אחת. מטריצה כזו נקראת וקטור. יותר במדויק – מטריצה בת שורה אחת היא וקטור שורה ומטריצה בעלת עמודה אחת היא וקטור עמודה. אפשר לחשוב על וקטורים כאלו פשוט בתור סדרות של מספרים: \(\left(a_{1},a_{2},\dots,a_{n}\right)\) ו-\(\left(b_{1},b_{2},\dots,b_{n}\right)\) הם וקטורים בעלי \(n\) איברים כל אחד. למי שמכיר וקטורים במשמעות גאומטרית – זה אותו הדבר, וארחיב על כך בעתיד.

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

פורמלית, \(\left(a_{1},a_{2},\dots,a_{n}\right)\cdot\left(b_{1},b_{2},\dots,b_{n}\right)=a_{1}b_{1}+a_{2}b_{2}+\dots+a_{n}b_{n}\), וזו ההזדמנות שלי להציג סימן מקוצר לחיבור שהוא קריטי כשמדברים על כפל מטריצות: \(\Sigma\). בסימון המקוצר הזה המכפלה הסקלרית של הוקטורים שלמעלה מתוארת כך: \(\sum_{i=1}^{n}a_{i}b_{i}\). מה שקורה כאן הוא שבתחתית של ה-\(\Sigma\) מגדירים "משתנה אינדקס" בשם \(i\) ו"מאתחלים" אותו ל-1; ה-\(n\) למעלה פירושו "לכל ערך טבעי של \(i\) החל מערך האתחול שלו ועד ל-\(n\)", וה-\(a_{i}b_{i}\) אומר שלכל \(i\) שרצים עליו, מוסיפים לסכום של \(a_{i}b_{i}\). אין כאן שום דבר יותר מאשר כתיב מקוצר של \(a_{1}b_{1}+a_{2}b_{2}+\dots+a_{n}b_{n}\) שדורש הרבה, הרבה פחות מקום; ולשם שינוי אני לא אתחיל להגדיר פעולות כפל מוזרות גם על ה-\(\Sigma\) הזה עצמו.

עכשיו אפשר לתת הגדרה בנפנוף ידיים מהיר של כפל מטריצות: \(C=AB\) היא מטריצה שהכניסה ה-\(ij\) שלה היא התוצאה של המכפלה הסקלרית של השורה ה-\(i\) של \(A\) עם העמודה ה-\(j\) של \(B\). הרי על שורה של מטריצה אפשר לחשוב גם כוקטור שורה העומד בפני עצמו; ועל עמודה של \(j\) אפשר לחשוב גם כוקטור עמודה העומד בפני עצמו; ואפשר להכפיל אותם; והתוצאה תהיה מספר, אז ההגדרה שנתתי היא בעלת משמעות.

יש בכל זאת בעיה אחת שמייד קופצת: כדי לכפול סקלרית שני וקטורים הם צריכים להיות מאותו האורך. אם אני כופל שורות של \(A\) בעמודות של \(B\), זה אומר שאני צריך שהאורך של כל שורה של \(A\) יהיה זהה לאורך של כל עמודה של \(B\). זה אומר, למשל, שאי אפשר לכפול יחד שתי מטריצות מסדר \(2\times3\)! במטריצה \(\left[\begin{array}{ccc}1 & 2 & 3\\1 & 2 & 3\end{array}\right]\) האורך של כל שורה הוא 3 (כמספר העמודות במטריצה) והאורך של כל עמודה הוא 2 (כמספר השורות במטריצה) וזה אומר שעל פי ההגדרה שנתתי אי אפשר לכפול אותה אפילו עם עצמה! זה מוזר למדי אבל זו אכן תוצאה הכרחית של ההגדרה שלי.

לכן הנה הכלל: אם \(A\) היא מטריצה מסדר \(n\times m\) (\(n\) שורות, \(m\) עמודות) ו-\(B\) היא מטריצה מסדר \(k\times l\) (\(k\) שורות, \(l\) עמודות) אז כדי שתהיה משמעות למכפלה \(AB\) חייב להתקיים \(m=k\) (מספר העמודות של \(A\) שווה למספר השורות של \(B\)). אם אכן \(m=k\), אז המכפלה \(AB\) תהיה מטריצה מסדר \(n\times l\) (\(n\) שורות, \(l\) עמודות), כי יש כניסה ב-\(AB\) לכל זוג של שורה ב-\(A\) ועמודה ב-\(B\) שמוכפלות סקלרית.

בואו נראה דוגמה: \(\left[\begin{array}{ccc}1 & 2 & \pi\\0 & 3 & 6\end{array}\right]\left[\begin{array}{cc}5 & 0\\1 & 0\\0 & 1\end{array}\right]=\left[\begin{array}{cc}7 & \pi\\3 & 6\end{array}\right]\). למה הכניסה \(1,1\) של המכפלה היא 7? כי זו התוצאה של המכפלה הסקלרית \(\left(1,2,\pi\right)\cdot\left(5,1,0\right)=5+2+\pi\cdot0=7\). נסו להבהיר לעצמכם למה שאר הכניסות קיבלו את הערכים שהן קיבלו, ולמה הממדים של התוצאה הם \(2\times2\). אם הצלחתם, כבר הבנתם את ההגדרה גם אם טרם הבנתם "למה".

בואו נגדיר כפל באופן פורמלי כדי שלא יהיו ספקות. אם \(A\) היא מטריצה מסדר \(n\times m\) ו-\(B\) היא מטריצה מסדר \(m\times k\) אז \(C=AB\) היא מטריצה מסדר \(n\times k\) כך ש-

\(C_{ij}=\sum_{r=1}^{m}A_{ir}B_{rj}\)

זה הכל.

לכפל מטריצות יש תכונה מוזרה אחת (מוזרה עבור מי שרגיל לכפל "רגיל") שצריך לשים על השולחן כמה שיותר מהר: לא בהכרח מתקיים \(AB=BA\). ראשית, בכלל לא ברור שתהיה משמעות גם ל-\(AB\) וגם ל-\(BA\); בשביל זה שתי המטריצות חייבות להיות עם אותו מספר שורות ועמודות – מטריצות כאלו מכונות מטריצות ריבועיות. אבל גם אם \(A,B\) שתיהן ריבועיות מסדר \(n\times n\) זה ממש לא נכון שבהכרח יתקיים \(AB=BA\) (אם כי לפעמים זה כן קורה). למשל, \(\left[\begin{array}{cc}1 & 1\\0 & 0\end{array}\right]\left[\begin{array}{cc}1 & 0\\1 & 0\end{array}\right]=\left[\begin{array}{cc}1 & 0\\0 & 0\end{array}\right]\) אבל \(\left[\begin{array}{cc}1 & 0\\1 & 0\end{array}\right]\left[\begin{array}{cc}1 & 1\\0 & 0\end{array}\right]=\left[\begin{array}{cc}1 & 1\\1 & 1\end{array}\right]\). אתם צריכים לחשוב על זה שהתכונה הזו לא מתקיימת בתור דבר טוב: זה אומר שאפשר לתאר עם כפל מטריצות עולם יותר עשיר משנדמה לנו, כי במציאות יש גם פעולות שהן לא חילופיות באופן הזה (למשל, הטרנספורמציות של צורות תלת ממדיות שהזכרתי בתחילת הפוסט אינן כאלו – לסובב ואז לשקף לא תמיד נותן אותו דבר כמו לשקף ואז לסובב).

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

\(2x+3y=17\)

\(8x-4y=6\)

ממש לא מעניין אותי הפתרון של המערכת. מה שכן מעניין אותי היא לתרגם את הבעיה "פתור את המערכת" לבעיה "פתור את המשוואה הבאה שמערבת מטריצות". לשם כך ראשית כל אסתכל על המטריצה של מקדמי המשוואה: \(\left[\begin{array}{cc}2 & 3\\8 & -4\end{array}\right]\). שימו לב שבניגוד לקודם, כעת אני לא לא מכניס פנימה גם את המספרים שמעבר לסימן השווה; אותם אני מכניס לוקטור נפרד – וקטור העמודה \(\left[\begin{array}{c}17\\6\end{array}\right]\). בנוסף, אני אכניס לתמונה וקטור חדש לגמרי – וקטור של משתנים: \(\left[\begin{array}{c}x\\y\end{array}\right]\). כעת מערכת המשוואות שלמעלה זהה לחלוטין למשוואה הבודדת הבאה על מטריצות:

\(\left[\begin{array}{cc}2 & 3\\8 & -4\end{array}\right]\left[\begin{array}{c}x\\y\end{array}\right]=\left[\begin{array}{c}17\\6\end{array}\right]\)

לא מאמינים? ובכן, קל לחשב על פי ההגדרה שנתתי שמתקיים \(\left[\begin{array}{cc}2 & 3\\8 & -4\end{array}\right]\left[\begin{array}{c}x\\y\end{array}\right]=\left[\begin{array}{c}2x+3y\\8x-4y\end{array}\right]\) (זכרו שוקטור עמודה הוא מטריצה, פשוט עם עמודה בודדת) ולכן השוויון שלמעלה הוא השוויון \(\left[\begin{array}{c}2x+3y\\8x-4y\end{array}\right]=\left[\begin{array}{c}17\\6\end{array}\right]\) ומכיוון שמשווים וקטורים "כניסה כניסה" זו בדיוק מערכת המשוואות המקורית.

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

ראשית, בואו נסתכל על מטריצה מיוחדת – מטריצת היחידה, \(I=\left[\begin{array}{ccc}1 & 0 & 0\\0 & 1 & 0\\0 & 0 & 1\end{array}\right]\). זו מטריצה מסדר \(3\times3\) אבל על פי אותו עיקרון ניתן להגדיר מטריצת יחידה לכל סדר (אבל היא חייבת להיות ריבועית) במילים, לכל כניסה \(ii\) יש במטריצת היחידה 1, ולכל כניסה \(ij\) כך ש-\(i\ne j\) יש בה 0. המקומות שבהם נמצאים ה-1-ים של המטריצה נקראים האלכסון הראשי של המטריצה.

המטריצה הזו מעניינת כי אם \(A\) היא מטריצה מסדר \(n\times m\) ו-\(I\) היא מטריצת יחידה מסדר \(n\times n\) אז \(IA=A\). כדי להבין למה, בואו ננסה להבין מהי הכניסה ה-\(ij\) של \(IA\): זו המכפלה הסקלרית של השורה ה-\(i\) של \(I\) בעמודה ה-\(j\) של \(A\). השורה ה-\(i\) של \(I\) כוללת רק אפסים חוץ ממקום אחד שכולל 1 – בדיוק המקום ה-\(i\). אז כשכופלים את השורה הזו בעמודה ה-\(j\) של \(A\) אנחנו מתעלמים מכל הכניסות בעמודה הזו חוץ מאחת – הכניסה ה-\(i\)-ית, שהיא בדיוק מה שנמצא בשורה ה-\(i\)-ית של \(A\). לכן בכניסה ה-\(ij\) של \(IA\) יהיה בדיוק את האיבר בכניסה ה-\(ij\) של \(A\).

כעת בואו נחזור על אותה פעולת כפל אבל עם מטריצה שהיא "כמעט \(I\)" פרט לכך שהחלפנו את השורה הראשונה עם השניה. מהי הכניסה ה-\(1j\) של המכפלה הפעם? היא תכיל את האיבר השני בעמודה ה-\(j\) של \(A\). כלומר, השורה הראשונה במכפלה תכיל את השורה השניה של \(A\), ובאופן לא מפתיע השורה השניה במכפלה תכיל את השורה הראשונה של \(A\). גם כאן מומלץ לבדוק אותי עצמאית.

מה שראינו פה הוא עקרון כללי: אם נבצע פעולה אלמנטרית כלשהי על מטריצת היחידה \(I\) – בין אם החלפת שורות, או כפל שורה במספר, או חיבור כפולה של שורה אחת לשורה אחרת – נקבל מטריצה (שמכונה, באופן לא מפתיע, "מטריצה אלמנטרית") שהכפל שלה ב-\(A\) זהה להפעלת הפעולה האלמנטרית הזו על \(A\).

אם כן, נניח ש-\(\overline{x}\) מסמן לנו וקטור של משתנים, ו-\(\overline{c}\) וקטור של מספרים, מערכת כללית של משוואות לינאריות מתוארת על ידי \(A\overline{x}=\overline{c}\) (שימו לב ש-\(\overline{x}\) ו-\(\overline{c}\) בכלל לא חייבים להיות מאותו האורך; אורכו של הראשון הוא מספר המשתנים ואורכו של השני הוא מספר המשוואות). כעת, אם \(E\) היא מטריצה אלמנטרית כלשהי, אפשר לכפול בה את שני אגפי המשוואה ולקבל \(\left(EA\right)\overline{x}=E\overline{c}\) (כמובן, צריך להוכיח שדברים כאלו באמת עובדים; אלו הוכחות לא מעניינות ולא אציג אותן כאן). אם אנחנו רוצים להפעיל שתי פעולות אלמנטריות, \(E_{1}\) ו-\(E_{2}\), אפשר לכפול את המשוואה בהן בזו אחר זו ולקבל \(\left(E_{2}\left(E_{1}A\right)\right)\overline{x}=E_{2}\left(E_{1}\overline{c}\right)\). כעת העובדה שכפל מטריצות מקיים את חוץ הקיבוץ הופכת לקריטית: זה אומר ש-\(E_{2}\left(E_{1}A\right)=\left(E_{2}E_{1}\right)A\), ולכן במקום לכפול את \(A\) קודם ב-\(E_{1}\) ואז ב-\(E_{2}\) אפשר לכפול את \(A\) רק פעם אחת במטריצה \(E_{2}E_{1}\) ש"מקודדת בתוכה" הפעלה של שתי פעולות אלמנטריות ולא רק אחת. באותו אופן, אם אנחנו רוצים להפעיל על \(A\) כמות סופית כלשהי של פעולות אלמנטריות, אפשר קודם כל לכפול את המטריצות האלמנטריות אלו באלו ובסוף לקבל מטריצה \(E\) שכבר מאחסנת בתוכה את כל הפעולות שרוצים לבצע על \(A\) כשהן מסודרות לפי הסדר הנכון. אחרי הכפל נקבל \(\left(EA\right)\overline{x}=E\overline{c}\); מכיוון ש-\(E\overline{c}\) הוא בעצמו וקטור אחר של מספרים, מה שקיבלנו בסופו של דבר הוא משוואה אחרת מהצורה \(B\overline{x}=\overline{d}\), שבה אנחנו יכולים להניח ש-\(B\) היא מטריצה מצומצמת. בקיצור, כשבפוסט הבא אחזור לעסוק בפתרון משוואות אוכל לצמצם את כל הבעיה שלנו למשוואות מהצורה \(B\overline{x}=\overline{d}\) עם מטריצות מצומצמות.

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

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

אנחנו רוצים לספור מסלולים בגרף. מסלול הוא פשוט סדרה של צמתים כל שכל שני צמתים בסדרה מחוברים בקשת, ואורכו הוא כמספר הקשתות שבו. לכל מסלול גם יש צומת התחלתי וצומת סופי – הצמתים הראשונים והאחרונים בסדרה. כך למשל \(v\to u\) הוא מסלול באורך 1 מ-\(v\) אל \(u\), ו-\(v\to u\to w\) הוא מסלול באורך 2 מ-\(v\) אל \(w\) (שעובר ב-\(u\)). גם \(v\) לבדו הוא מסלול: מסלול באורך 0 עם צומת התחלה \(v\) וצומת סיום \(v\). זה נשמע מטופש אבל תכף נראה שזו הגדרה מועילה.

בגרף שלנו נרשה שצומת יכיל קשת אל עצמו (מה שנקרא "חוג עצמי") ולכן \(v\to v\) הוא מסלול חוקי וגם נרשה כמה קשתות בין שני צמתים (מה שנקרא "קשתות מקבילות"); שני מסלולים שכוללים בדיוק את אותה סדרת צמתים אבל מתישהו משתמשים בקשתות שונות ייחשבו שונים. אפשר לאסור על כל השכלולים הללו ועדיין מה שאציג יעבוד, אבל אני רוצה להראות תוצאה כללית ככל האפשר ולכן מרשה את זה (ובפועל לעתים קרובות אכן יש צורך בחוגים עצמיים וקשתות מקבילות; למשל, כשהגרף שלנו מגיע מאוטומט סופי דטרמיניסטי). בנוסף, הגרף יכול להיות מכוון – קשת היא תמיד מצומת א' אל צומת ב' ומסלול חייב להיות עם כיוון הקשתות כדי להיות חוקי.

כעת, נניח שיש לנו גרף עם \(n\) צמתים, \(v_{1},\dots,v_{n}\). מגדירים עבורו מטריצה \(A\) מסדר \(n\times n\) – "מטריצת השכנויות/סמיכויות" שלו – באופן הבא: \(A_{ij}\) שווה למספר הקשתות מ-\(i\) אל \(j\). כלומר זה מספר שלם אי שלילי (בגלל שאנחנו מרשים קשתות מקבילות, \(A_{ij}\) יכול להיות גדול מ-1; ובגלל שהגרף מכוון \(A_{ij}\) לא בהכרח שווה ל-\(A_{ji}\)).

מכיוון ש-\(A\) היא מטריצה ריבועית, אפשר לכפול אותה בעצמה. \(A^{k}\) היא מה שמקבלים כשכופלים את \(A\) בעצמה \(k\) פעמים. כמו ש-\(a^{0}=1\) עבור מספרים, כך מגדירים גם ש-\(A^{0}=I\) כאשר \(I\) היא מטריצת היחידה מסדר \(n\times n\).

כעת אפשר לעבור לתוצאה המקסימה: \(A^{t}\) היא מטריצה שמקודדת בדיוק את מספרי המסלולים מאורך \(t\) בין כל שני צמתים בגרף; יותר בפירוט, \(A_{ij}^{t}\) הוא בדיוק מספר המסלולים מאורך \(t\) מ-\(v_{i}\) אל \(v_{j}\).

למה זה עובד? ובכן, עבור \(A^{0}\) זה ברור מההגדרה שנתתי: מסלול באורך 0 חייב להתחיל ולהסתיים באותו צומת, ויש בדיוק 1 כזה. זה מתאים בדיוק לכך שעל האלכסון הראשי של \(A^{0}\) יש 1 ובשאר הכניסות יש 0.

עבור \(A^{1}\) זה גם ברור: כל קשת \(v\to u\) מגדירה מסלול באורך 1 מ-\(v\) אל \(u\), ולכן מספר המסלולים הכולל מ-\(v\) אל \(u\) באורך 1 הוא כמספר הקשתות מ-\(v\) אל \(u\).

הכיף מתחיל עבור \(A^{2}\), וכאן ההגדרה של כפל מטריצות מתגלה במלוא כוחה. מהו מסלול באורך 2? מסלול מהצורה \(v\to u\to w\) (הצמתים לא חייבים להיות שונים אלו מאלו בהכרח). אם אנחנו מתעניינים במספר המסלולים מ-\(v\) אל \(w\), אז כל מסלול כזה נבנה באופן הבא: בחר צומת \(u\) שישמש בתור צומת האמצע; בחר קשת מ-\(v\) אל \(u\) (אם קיימת כזו), ואז בחר קשת מ-\(u\) אל \(w\) (אם קיימת כזו).

כמה מסלולים כאלו יש? אם קבענו את \(u\), אז נותר לבחור קשת מ-\(v\) אל \(u\), ולבחור קשת מ-\(u\) אל \(w\), ושתי הבחירות הללו בלתי תלויות זו בזו, ולכן מספר האפשרויות הוא מכפלה של מספר האפשרויות לבחור קשת מ-\(v\) אל \(u\) במספר האפשרויות לבחור קשת מ-\(u\) אל \(w\) (זהו "עקרון הכפל" הקומבינטורי). כעת, לכל \(u\) שיכול לשמש כצומת ביניים אנחנו מקבלים מספר אפשרויות כלשהו, ולכן מספר האפשרויות הכולל הוא סכום כל האפשרויות על כל ה-\(u\)-ים האפשריים (זהו "עקרון החיבור" הקומבינטורי).

בואו נסמן את הצמתים במספרים כדי שיהיה לנו קצת יותר קל. נניח שאנחנו רוצים לדעת כמה מסלולים יש מ-\(v_{i}\) אל \(v_{j}\), וש-\(v_{r}\) הוא צומת הביניים שלנו. אז יש \(A_{ir}\) קשתות מ-\(v_{i}\) אל \(v_{r}\); \(A_{rj}\) קשתות מ-\(v_{r}\) אל \(v_{j}\); ולכן \(A_{ir}A_{rj}\) מסלולים מ-\(v_{i}\) אל \(v_{j}\) שעוברים דרך \(v_{r}\); ולכן \(\sum_{r=1}^{n}A_{ir}A_{rj}\) מסלולים בסך הכל מ-\(v_{i}\) אל \(v_{j}\). אבל \(\sum_{r=1}^{n}A_{ir}A_{rj}\) ידידינו הוא בדיוק ההגדרה שלנו לכניסה ה-\(ij\) בכפל המטריצה \(A\) בעצמה, ולכן \(A^{2}\) אכן מקודד בדיוק את המסלולים מאורך 2 בין צמתים בגרף.

ההוכחה הכללית עבור \(A^{t}\) פשוטה באותה מידה, אם שמים לב לכך ש-\(A^{t}=A^{t-1}A\) ומשתמשים באינדוקציה כדי להניח ש-\(A^{t-1}\) כבר מקודד את מספר המסלולים מאורך \(t-1\) בין צמתים בגרף. במקרה זה, אפשר לחשוב על מסלול מאורך \(t\) בגרף מ-\(v_{i}\) אל \(v_{j}\) כאילו הוא מהצורה \(v_{i}\rightarrow v_{r}\to v_{j}\), כאשר \(v_{i}\rightarrow v_{r}\) מייצג לא קשת אחת אלא מסלול שלם מאורך \(t-1\) מ-\(v_{i}\) אל \(v_{r}\). שאר הניתוח זהה: מספר המסלולים מ-\(v_{i}\) אל \(v_{j}\) מאורך \(t\) שהצומת הלפני-אחרון בהם הוא \(v_{r}\) הוא כמספר המסלולים מאורך \(t-1\) מ-\(v_{i}\) אל \(v_{r}\) כפול מספר הקשתות מ-\(v_{r}\) אל \(v_{j}\). סוף הסיפור.

אני לא יכול להתאפק כאן ולהזכיר מאוד בחטף נושא מתקדם טיפה יותר. נניח שהמטריצה \(A\) שלנו, במקום לקודד את מספר הקשתות, הייתה מקודדת הסתברות למעבר מ-\(v_{i}\) אל \(v_{j}\)? כלומר, הגרף שלנו היה כזה שבו אם אתם נמצאים בצומת מסוייים, אז בסיבוב הבא עליכם לזוז לצומת אחר (או להישאר במקום – זה נחשב כאילו זזתם מהצומת אל עצמו) והייתם בוחרים לאן לעבור בהסתברות קבועה מסויימת על בסיס המיקום הנוכחי שלכם. אם \(A\) הייתה המטריצה שמקודדת את ההסתברויות הללו, מה הייתה המשמעות של \(A^{t}\)? כמעט אותו דבר – \(A_{ij}^{t}\) הייתה ההסתברות שבה אם התחלתם מ-\(v_{i}\) וביצעתם \(t\) סיבובים, תגיעו אל \(v_{j}\). לכן אם אנחנו יודעים איך מתנהגת \(A^{t}\) עבור ערכים גדולים מאוד של \(t\), אנחנו יודעים מה ההתנהגות לאורך זמן של ההילוך האקראי הזה – לאיזה מקומות בגרף יותר סביר להגיע ולבלות בהם יותר זמן, וכדומה. הרעיון הזה עמד בבסיס אלגוריתם הדירוג של גוגל (מה שידוע על אלגוריתם הדירוג של גוגל, לפחות) כאשר הגרף הוא "האינטרנט" (ואתרים חשובים בו הם כאלו שאליהם ההילוך המקרי מגיע לעתים קרובות יותר) והניתוח של התנהגות \(A^{t}\) עבור ערכים גדולים של \(t\) אכן מערב לו עוד אלגברה לינארית שטרם הגעתי אליה (בפרט, את המושגים של ערכים עצמיים ווקטורים עצמיים).

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

משפט המטריצה-עץ של קירכהוף

פורסם בתאריך 13 בספטמבר 2011 על ידי gadial

אני רוצה לדבר הפעם על מה שלטעמי הוא משפט יפהפה ביותר, גם בשל מה שהוא אומר וגם בשל ההוכחה שלו, שלטעמי מייצגת את כל מה שטוב במתמטיקה – גם דורשת הבנה טכנית לא טריוויאלית, וגם מכילה תובנה עמוקה שמאפשרת לראות מדוע המשפט נכון. העולם מסכים איתי, וההוכחה הזו מככבת בספר "Proofs from THE BOOK"; אני מקווה שכל מי שיתאמץ יצליח להבין אותה וליהנות כמוני ממנה.

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

ראשית אציג גרסה של המשפט שעוסקת בגרפים לא מכוונים כי ההוכחה שלו פשוטה מעט יותר; לאחר מכן אסביר כיצד ניתן להוכיח את המשפט גם לגרפים מכוונים (באותה הצורה אבל עם תיקונים קלים). המשפט בא לענות על השאלה הקומבינטורית הבאה: בהינתן גרף סופי \(G=\left(V,E\right)\), כמה עצים פורשים יש לו? כזכור, עץ פורש של \(G\) הוא תת-קבוצה של הקשתות שמהווה עץ (כלומר, כשמורידים מ-\(G\) את כל הקשתות שאינן בתת-הקבוצה נשארים עם גרף קשיר וחסר מעגלים). עובדה אחת שאתם אולי לא זוכרים והיא רלוונטית כאן היא שבגרף עם \(n=\left|V\right|\) צמתים, כל עץ הוא בעל בדיוק \(n-1\) קשתות (נסו להוכיח זאת לעצמכם!)

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

בואו נכניס מטריצות לתמונה. יש כמה וכמה מטריצות שאפשר להתאים לכל גרף \(G\), ואחת מהן היא מטריצת הלפלסיאן \(L_{G}\) (ובקיצור אכתוב סתם \(L\)). ההגדרה של \(L\) אולי תיראה קצת מוזרה במבט ראשון אבל היא שימושית; למשל, עבור משפט קירכהוף.

ראשית, מכיוון שמטריצות מאונדקסות בדרך כלל עם מספרים טבעיים, הבה ונאנדקס גם את הגרף עם מספרים כאלו: \(V=\left\{ v_{1},\dots,v_{n}\right\} \) ו-\(E=\left\{ e_{1},\dots,e_{m}\right\} \). בדרך כלל כשאתייחס לצומת זה יהיה עם אינדקס \(i\) או \(j\), ולקשת עם אינדקס \(k\).

כעת אנו מוכנים להגדיר את \(L\): ראשית, \(L_{ii}=d\left(v_{i}\right)\), כלומר הכניסה ה-\(i\) על האלכסון של \(L\) היא פשוט הדרגה של \(v_{i}\) – מספר הקשתות שמחוברות ל-\(v_{i}\). כעת, לכל \(i\ne j\) נגדיר את \(L_{ij}\) להיות מינוס מספר הקשתות בין \(v_{i}\)ל-\(v_{j}\) (בדרך כלל יש רק קשת אחת בין כל שני צמתים בגרף, אבל כאן אנחנו מרשים יותר; כמובן שככל שיש יותר קשתות יהיו יותר עצים פורשים). אם נסמן את המספר הזה בסימון שהמצאתי כרגע, \(d\left(v_{i},v_{j}\right)\) ונסכים ש-\(d\left(v_{i},v_{i}\right)\) הוא פשוט דרגת \(v_{i}\) (במקום מספר הקשתות מ-\(v_{i}\) לעצמו), הרי שאפשר לכתוב את הלפלסיאן כך: \(L_{ij}=d\left(v_{i},v_{j}\right)\).

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

הגדרת הלפלסיאן עבור גרפים מכוונים כמעט זהה, בשני שינויים קלים: ראשית, \(L_{ii}\) הוא דרגת הכניסה של \(v_{i}\) – מספר הקשתות שנכנסות אליו – ולא הדרגה הכוללת; שנית, \(L_{ij}\) הוא מינוס מספר הקשתות מ-\(v_{i}\) אל \(v_{j}\) (כלומר, קשתות מ-\(v_{j}\) אל \(v_{i}\) לא נספרות ב-\(L_{ij}\), אם כי הן כן ייספרו ב-\(L_{ji}\)). לא קשה לראות שההגדרה הזו מכלילה את ההגדרה לגרפים לא מכוונים אם נוקטים בתעלול הרגיל של לייצג גרף לא מכוון על ידי גרף מכוון שבו לכל זוג צמתים שיש ביניהם קשת בגרף הלא מכוון, היא מוחלפת בקשת לכל אחד משני הכיוונים בגרף המכוון.

כעת, יהא \(r\) אינדקס של צומת כלשהו בגרף, ונסמן ב-\(L^{\left(r\right)}\) את מטריצת המינור ה-\(r\)-ית של \(L\) – המטריצה שמתקבלת מ-\(L\) על ידי מחיקת השורה והעמודה ה-\(r\)-יות. אז הנה משפט קירכהוף, בגרסה שנכונה הן לגרפים מכוונים והן לגרפים לא מכוונים:

מספר העצים הפורשים של הגרף \(G\) שהשורש שלהם הוא \(v_{r}\) הוא \(\det L^{\left(r\right)}\).

(בגרף לא מכוון אין ממש משמעות ל"שורש" ולכן כדי למצוא את מספר העצים הפורשים אפשר לבחור \(r\) שרירותי; בגרף מכוון שורש הוא הצומת היחיד בעץ שקיים מסלול ממנו אל שאר הצמתים בגרף).

שימו לב שעניין המינור הכרחי: לא קשה לראות ש-\(\det L=0\) תמיד כי סכום כל עמודה במטריצה הוא 0 ולכן שורות המטריצה תלויות לינארית. כמובן ש-\(L\) מעניינת גם לכשעצמה – למשל, יש חשיבות גדולה לערך העצמי הבא החיובי הקטן ביותר שלה; אבל לא אכנס לכל זה כרגע.

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

את קושי-בינה לא רואים בדרך כלל בקורס בסיסי באלגברה לינארית וקצת חבל. יש לה גם הוכחה קומבינטורית יפהפיה משל עצמה (גם היא ב-Proofs from THE BOOK) שלא אציג כרגע. בבסיסה, הנוסחה היא הכללה של נוסחה בסיסית שכן רואים באלגברה לינארית: אם \(A,B\) הן מטריצות ריבועיות, אז \(\det\left(A\cdot B\right)=\det A\cdot\det B\).

העניין הוא בכך שמטריצות ריבועיות עשויות להתקבל גם כמכפלה של מטריצות לא ריבועיות: אם \(A\) היא מטריצה \(n\times m\) ו-\(B\) היא מטריצה \(m\times n\) אז מכפלתם \(AB\) היא מטריצה \(n\times n\), ולכן אפשר לדבר על הדטרמיננטה שלה. מצד שני, \(A,B\) אינן ריבועיות ולכן אין משמעות לדטרמינטטה שלהן. האם בכל זאת אפשר לעשות משהו?

אם \(m<n\) אין על מה לדבר, אבל רק כי אז מובן מאליו ש-\(\det AB=0\). למה מובן מאליו? ובכן, זה תרגיל טוב באלגברה לינארית: אם \(m<n\) אז דרגת \(A,B\) היא לכל היותר \(m\) כל אחד; ולכן דרגת המכפלה \(AB\) גם היא לכל היותר \(m\), ולכן \(AB\) היא מטריצה מדרגה לא מלאה ובהכרח הדטרמיננטה שלה היא 0.

מצד שנית אם \(m>n\), נוסחת קושי בינה נכנסת לפעולה. במילים מה שהולך כאן הוא הדבר הבא: \(A\) היא מטריצה מלבנית, אבל היא מכילה הרבה תת-מטריצות ריבועיות \(n\times n\), שמתקבלות מבחירת תת-קבוצה של \(n\) מתוך \(m\) העמודות שלה. באותו האופן גם \(B\) מכילה הרבה תת-מטריצות ריבועיות \(n\times n\) שמתקבלות מבחירת תת-קבוצה של \(n\) מתוך \(m\) השורות שלה. אם נסמן ב-\(\sigma\) בחירה מסויימת של \(n\) מתוך \(m\) אינדקסים, אז נוסחת קושי-בינה היא פשוט \(\det\left(AB\right)=\sum_{\sigma}\left(\det A_{\sigma}\cdot\det B_{\sigma}\right)\). כלומר: לכל בחירה אפשרית של \(n\) מתוך \(m\) אינדקסים \(\sigma\) ניקח מתוך \(A\) ו-\(B\) את תת המטריצות המתאימות (שימו לב שזו אותה בחירת אינדקסים לשתי המטריצות! זה מה שחשוב פה), נחשב את מכפלת הדטרמיננטות שלהן, ונסכום את הכל (אם \(m<n\) אז אפשר להסכים על כך שהסכום ריק ולכן שווה 0, ובכך לקבל נוסחה שתקפה לכל מקרה אפשרי).

איך נוסחת קושי-בינה מסייעת לנו כאן? ובכן, את הלפלסיאן קל למדי לכתוב כמכפלה של מטריצות. בואו נדבר לבינתיים על המקרה של גרף לא מכוון שהוא פשוט קצת יותר, ונגדיר מטריצה \(A\) – "מטריצת החילה" (Incidence matrix) של הגרף. זו תהיה מטריצה \(n\times m\) שבה כל שורה מייצגת צומת בגרף וכל עמודה מייצגת קשת בגרף, כך שלכל קשת \(e_{k}=\left(v_{i},v_{j}\right)\) עם \(i<j\) נקבע ש-\(A_{ik}=1,A_{jk}=-1\) וכל כניסה אחרת במטריצה היא 0. במילים אחרות, כל עמודה במטריצה הזו מכילה בדיוק 1 בודד ו-\(-1\) בודד, בשני הצמתים שמתאימים לקשת של אותה עמודה.

כעת זה תרגיל נחמד לבדוק שאכן \(L=A\cdot A^{T}\) (כאן \(A^{T}\) מייצג את השחלוף של \(A\): \(A_{ij}^{T}=A_{ji}\)). ומהו \(L^{\left(r\right)}\)? לא קשה לראות שהוא \(NN^{T}\) כאשר \(N\) מתקבלת מ-\(A\) על ידי מחיקת השורה ה-\(r\). שימו לב שאנחנו לא מוחקים מ-\(A\) עמודות; הקשתות שהיו מחוברות ל-\(v_{r}\) עדיין מיוצגות ב-\(N\), אבל באופן "חלקי" – העמודה שלהן מכילה רק 1 או רק \(-1\). זו אולי הנקודה הקריטית ביותר בהמשך ההוכחה.

עכשיו, על פי קושי-בינה, \(\det\left(L^{\left(r\right)}\right)=\sum_{\sigma}\det N_{\sigma}\det N_{\sigma}^{T}=\sum_{\sigma}\det\left(N_{\sigma}\right)^{2}\). הצטמצמנו להבנה של מהו \(\det\left(N_{\sigma}\right)\) לכל בחירה מתאימה של עמודות. שימו לב של-\(N\) יש \(n-1\) שורות (כי בגרף המקורי היו \(n\) צמתים והסרנו את השורה של הצומת \(v_{r}\) מהמטריצה \(A\) כדי לקבל את \(N\)), ולכן כל \(\sigma\) היא בחירה של \(n-1\) עמודות, כלומר של \(n-1\) קשתות מהגרף המקורי. והנה לב ההוכחה, התובנה המרכזית בה, מה שהופך את הכל לברור לדעתי: אותה בחירה \(\sigma\) של \(n-1\) עמודות היא בדיקה שלנו האם מועמד כלשהו לתפקיד עץ פורש הוא אכן עץ פורש. הדטרמיננטה \(\det N_{\sigma}\) תהיה בדיוק אבן הבוחן: אם \(\sigma\) אכן מהווה בחירה של \(n-1\) קשתות שיוצרות עץ פורש, נקבל ש-\(\det N_{\sigma}=\pm1\); ואחרת נקבל \(\det N_{\sigma}=0\). זה בבירור מסיים את ההוכחה שכן אז נקבל ש-\(\sum_{\sigma}\det\left(N_{\sigma}\right)^{2}\) הוא בדיוק מספר ה-\(\sigma\)-ות שעבורן קיבלנו עץ פורש, כלומר מספר העצים הפורשים של הגרף.

אתם עוד איתי? אם כן, הבנתם את ההוכחה; נותר לגהץ את הפרטים.

נתחיל במקרה שבו \(\sigma\) לא מגדירה עץ פורש בגרף \(G\). אנחנו רוצים להראות ש-\(\det N_{\sigma}=0\) במקרה הזה, ונעשה זאת על ידי כך שנוכיח שבמטריצה \(N_{\sigma}\) יש קבוצה של שורות שסכומן אפס. תוצאה בסיסית על עצים היא שאם גרף לא מכוון עם \(n\) צמתים ו-\(n-1\) קשתות הוא גם קשיר, אז הוא עץ; לכן אם \(\sigma\) אינה משרה עץ בהכרח יש שני רכיבי קשירות. \(v_{r}\) נמצא באחד מהם; בואו נסתכל דווקא על השני – וליתר דיוק, על השורות במטריצה \(N_{\sigma}\) שמתאימות לצמתים של אותו רכיב קשירות שני. אני טוען שסכום כל השורות הללו הוא 0. מדוע? ובכן, נעבור עמודה עמודה: כל עמודה מתאימה לקשת שמחברת שני צמתים. אם שניהם אינם ברכיב הקשירות ממילא, אז בשורות שמתאימות לרכיב הקשירות כל הכניסות בעמודה הזו יהיו 0. אם שניהם ברכיב הקשירות, אז תהיה שורה שבה יופיע 1, ושורה שבה יופיע \(-1\), ובשאר השורות 0 – ושוב, הסכום הוא 0. ואם אחד מהצמתים ברכיב הקשירות והשני לא? ובכן, זה בלתי אפשרי כי זה נוגד את ההגדרה של רכיב קשירות: אם צומת נמצא ברכיב קשירות מסויים, כך גם כל שכניו.

הטיעון הטכני ביותר יהיה ההוכחה ש-\(\det N_{\sigma}=\pm1\) כאשר \(\sigma\) כן מתאימה לעץ פורש, אבל אחר כך סיימנו את ההוכחה כולה. הרעיון הוא שבמקרה הזה, אפשר לסדר מחדש את שורות ועמודות \(N_{\sigma}\) כך שתתקבל מטריצה משולשית תחתונה (מטריצה שבה כל הכניסות מעל לאלכסון הראשי הן 0), ואת הדטרמיננטה של מטריצה משולשית קל לחשב – זו בסך הכל מכפלת האיברים שעל האלכסון. מכיוון שסידור מחדש של שורות או עמודות משנה רק את הסימן של הדטרמיננטה, זה יסיים את ההוכחה. את המטריצה המסודרת-מחדש אסמן ב-\(M\).

אמרנו ש-\(\sigma\) מהווה עץ. מה שנעשה הוא להתחיל לפרק את העץ לגורמים. ראשית, בואו נזכור שעלה בעץ הוא צומת מדרגה 1, כלומר שמחובר בדיוק לצומת אחר אחד. עוד משפט חשוב על עצים הוא שבעץ יש לפחות שני עלים; לא אוכיח אותו כרגע.

הבה ונסמן ב-\(u_{1}\) עלה שכזה שהוא שונה מ-\(v_{r}\) (תמיד יש כזה; אפילו אם \(v_{r}\) הוא עלה, יש עוד עלה שאפשר לבחור) וב-\(e_{1}\) את הקשת בעץ שמחוברת אליו. השורה הראשונה במטריצה-המסודרת-מחדש שלנו תהיה זו של \(u_{1}\), והעמודה הראשונה תהיה זו של \(e_{1}\). מכיוון ש-\(u_{1}\) מחובר רק ל-\(e_{1}\) בעץ, הכניסה \(M_{11}\) תהיה שווה ל-1 או ל-\(-1\)(לא משנה לנו איזה מהם), וכמו כן \(M_{1j}=0\) לכל \(j>1\) (ובכלל לא משנה איך אני הולך לסדר את יתר העמודות), שכן כל העמודות הללו מתאימות לקשתות ש-\(u_{1}\) לא מחובר אליהן.

כעת נסיר את \(u_{1}\) מהעץ שלנו (ויחד איתו את \(e_{1}\)), ושוב נקבל עץ, ולכן שוב יש בו צומת מדרגה 1 שאינו \(v_{r}\). זה יהיה \(u_{2}\) והקשת שמתאימה לו תהיה \(e_{2}\). זה אומר ש-\(M_{22}\) הוא שוה \(\pm1\); ואנו יודעים בודאות שעבור הקשתות שטרם טיפלנו בהן, \(u_{2}\) אינו מחובר לאף אחת מהן ולכן \(M_{2j}=0\) לכל \(j>2\) (אולי הוא היה מחובר ל-\(e_{1}\), אבל זה אומר רק שאולי \(M_{12}\ne0\) וזה לא מפריע לנו כי כניסה זו היא מתחת לאלכסון הראשי). העיקרון ברור – נמשיך לבנות כך סדרה \(u_{1},u_{2},\dots,u_{n-1}\) של צמתים ו-\(e_{1},e_{2},\dots,e_{n-1}\) של קשתות. הצומת היחיד שלא נגענו בו הוא \(v_{r}\) עצמו, שהשורה שמתאימה לו בכלל לא מופיעה ב-\(N\) כך שהוא לא רלוונטי לבניה שעשינו. קיבלנו מטריצה משולשת תחתונה שעל האלכסון יש לה רק \(\pm1\) וזה מסיים את ההוכחה.

אני מאוד מקווה שנהניתם מההוכחה הזו כפי שאני נהניתי ממנה.

בואו נעבור עכשיו לדבר על מה צריך להשתנות בהוכחה אם נרצה להוכיח את המשפט לגרפים מכוונים. כבר אמרתי שצריך לשנות את הגדרת מטריצת הלפלסיאן עצמה קצת: \(L_{ii}\) הוא דרגת הכניסה של כל צומת ו-\(L_{ij}\) הוא מינוס מספר הקשתות מ-\(v_{i}\) אל \(v_{j}\). זו לא מטריצה סימטרית ולכן גם לא בהכרח ניתן לכתוב אותה בתור \(A\cdot A^{T}\); אבל אפשר לעשות משהו טוב כמעט באותה מידה.

הבה ונגדיר שוב מטריצה \(A\) מסדר \(n\times m\) (כלומר – שורה לכל צומת ועמודה לכל קשת, כמקודם) באופן הבא: לכל קשת \(e_{k}=v_{i}\to v_{j}\) (כלומר, מהצומת \(v_{i}\) אל הצומת \(v_{j}\)) יתקיים \(A_{ik}=1,A_{jk}=-1\) ושאר הכניסות יהיו אפס; במילים אחרות, זו בדיוק אותה מטריצה \(A\) כמו קודם רק שעכשיו אנחנו קובעים איזו כניסה תהיה חיובית ואיזו כניסה תהיה שלילית על פי כיוון הקשת \(e_{k}\).

בנוסף, נגדיר מטריצה \(B\) מסדר \(n\times m\) באופן הבא: לכל קשת \(e_{k}=v_{i}\to v_{j}\) יתקיים \(B_{ik}=0,B_{jk}=-1\) ושאר הכניסות יהיו אפס. כלומר, \(B\) זהה ל-\(A\) פרט לכך שבכל עמודה יש רק \(-1\) עבור הצומת שאליו הקשת נכנסת; לא מופיע 1 עבור הצומת שממנו הקשת יוצאת.

עכשיו לא קשה לראות ש-\(L=A\cdot B^{T}\) וש-\(L^{\left(r\right)}\) הוא \(N_{A}N_{B}^{T}\) כאשר \(N_{A},N_{B}\) מתקבלים מ-\(A,B\) בהתאמה על ידי מחיקת השורה ה-\(r\). אז קושי-בינה מניבה פה \(\det\left(L^{\left(r\right)}\right)=\sum_{\sigma}\det\left(N_{A\sigma}\right)\det\left(N_{B\sigma}\right)\). עכשיו צריך להבין מה קורה פה.

היינו רוצים לומר שאם \(\sigma\) לא מגדיר עץ, אז נקבל ש-\(\det\left(N_{A\sigma}\right)=0\) בדיוק כמו קודם ואז גם המכפלה תתאפס. לרוע המזל, "\(\sigma\) לא מגדיר עץ" הוא מקרה הרבה יותר מסובך כאשר הגרף שלנו מכוון, כי הקריטריון של "גרף עם \(n-1\) קשתות שהוא קשיר הוא עץ" פשוט לא נכון. בעץ מכוון, צריך שיהיה צומת (השורש) שקיים מסלול ממנו לכל הצמתים האחרים, ומספיקה קשת אחת בכיוון הלא נכון כדי לקלקל את זה. לכן בואו נתחיל קודם כל דווקא מדיבור על המקרה שבו \(\sigma\) כן מגדיר עץ. מה נשתנה הפעם?

ובכן, הפעם צריכים להיות קצת יותר זהירים בגלל ש-\(\det\left(N_{A\sigma}\right)\det\left(N_{B\sigma}\right)\) הוא לא ריבוע. מה שאנחנו רוצים לטעון הוא שמתקיים \(\det\left(N_{A\sigma}\right)=\det\left(N_{B\sigma}\right)\) וששניהם שווים או 1 או \(-1\). אפשר להשתמש בשיטת הסידור-מחדש של מטריצה כמו קודם; רק צריך להיות זהירים ולסדר את \(N_{A\sigma}\) ואת \(N_{B\sigma}\) באותו האופן בדיוק כדי שהשינוי בסימן, אם היה כזה, יהיה זהה אצל שניהם.

אחרי הסידור מחדש של המטריצה, מה שמתקבל מ-\(N_{A\sigma}\) ומ-\(N_{B\sigma}\) היא כמקודם מטריצה משולשית תחתונה, אבל מה נמצא על האלכסון? כאן האופן שבו ביצענו את הסדר הופך להיות קריטי: להזכירכם, בשיטה שלנו בשלב ה-\(i\) קבענו את השורה ה-\(i\) להיות צומת \(u_{i}\) שבשלב הזה היה עלה, ואת העמודה להיות קשת \(e_{i}\) שהיא הקשת שנכנסת אל \(u_{i}\). כלומר, הן על פי ההגדרה של \(A\) והן על פי ההגדרה של \(B\), הכניסה המתאימה תהיה \(-1\). זה מבטיח שהדטרמיננטה תהיה מכפלה של \(-1\)-ים ושלא ישתרבב פנימה איזה 0 שיאפס את כולה (מה שהיה עלול לקרות עם \(B\), שבו יש אפסים שלא היו בהוכחה עבור גרפים לא מכוונים).

עכשיו נחזור למקרה שבו \(\sigma\) הוא לא עץ. מי שיושיע אותנו כאן הוא שאנחנו משתמשים גם ב-\(N_{A\sigma}\) וגם ב-\(N_{B\sigma}\): הדטרמיננטה של אחד מהם תתאפס, ולא משנה מה. התעלול פשוט: אם \(\sigma\) הוא כזה שאפילו גרף התשתית של העץ שלנו (מה שמקבלים כשמוחקים את כיווני הקשתות) איננו עץ אז \(\det\left(N_{A\sigma}\right)=0\) מאותו שיקול כמו במקרה הלא מכוון (סכום שורות שהוא אפס, מה שמובטח על ידי ה-1 וה-\(-1\) שיש בכל עמודה שם – וזה משהו שאין ב-\(B\)), ואילו אם גרף התשתית הוא כן עץ, אז נסדר מחדש את \(N_{B\sigma}\) על פי אותה שיטה שבה השתמשנו עד כה במקרים שבהם \(\sigma\) הגדיר עץ. נקבל מטריצה משולשית תחתונה כמו תמיד, רק שהפעם אחד מהאיברים על האלכסון יהיה 0. מדוע? כי אם \(\sigma\) איננו עץ למרות שגרף התשתית הוא כן עץ, זה אומר שיש קשת אחת שמכוונת בכיוון "הלא נכון", ואז הכניסה על האלכסון שמתאימה לקשת הזו ולצומת שמחוברת אליה תהיה 0 (כי הקשת יוצאת מהצומת במקום להיכנס אליו).

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

משפט טורן והולדת תורת הגרפים האקסטרמלית

פורסם בתאריך 2 בספטמבר 2011 על ידי gadial

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

הפעם אני רוצה לעסוק בתחום דומה בקומבינטוריקה (תת-תחום של תורת רמזי? המעמד הרשמי לא ממש חשוב) – תורת הגרפים האקסטרמלית. כפי שניתן לנחש, האובייקטים שלנו כאן הם גרפים (אבל נו באמת – איזה אובייקט ביקום לא ניתן לתיאור על ידי גרף?) ואנחנו רוצים להבין את תכונותיהם של הגרפים הקיצוניים ביותר שמקיימים (או שלא מקיימים) תכונה כלשהי. באופן קצת יותר קונקרטי, עבור תכונה \(\Phi\) כלשהי של גרפים, שאלה מרכזית היא זו: מה המספר המקסימלי של קשתות שגרף עם \(n\) צמתים יכול להכיל ועדיין לקיים את התכונה \(\Phi\)? המספר הזה מסומן לרוב כ-\(\mbox{ex}\left(n,\Phi\right)\) (אפשר לחשוב עליו כפונקציה של \(n\) עם פרמטר \(\Phi\)). לא תמיד אפשר לדעת במדויק את \(\mbox{ex}\left(n,\Phi\right)\), כמובן, ולרוב מסתפקים בהערכה.

המקרה המעניין הראשון הוא זה שבו \(\Phi\) היא התכונה "להכיל תת-גרף מסויים". אז אנחנו שואלים את השאלה הקלאסית של תורת רמזי – מתי אובייקט הוא גדול דיו כדי שמבנה מסויים יצוץ בתוכו לבטח? ומשפט טורן מטפל בתת גרף פשוט במיוחד: קליק. קליק מגודל \(t\), שאותו אסמן ב-\(K_{t}\), הוא פשוט קבוצה של \(t\) צמתים שכולם מחוברים אלה לאלה בקשתות. שימו לב להבדל בין זה ומשפט רמזי, שמדבר על מספר הצמתים שצריך להיות בגרף לפני שיצוץ בו קליק מגודל מסויים או קבוצה בלתי תלויה מגודל מסויים; כאן מספר הצמתים \(n\) קבוע ונתון מראש ואנחנו רוצים לדעת מה מספר הקשתות; ולהבדיל ממשפט רמזי, כאן אנחנו יודעים את \(\mbox{ex}\left(n,K_{t}\right)\) במדויק וגם יודעים בדיוק איך הגרפים הקיצוניים (בעלי המספר המקסימלי של קשתות שאינם מכילים את \(K_{t}\)) נראים.

בואו נתחיל עם מקרה פרטי שהיה ידוע בימיו של טורן – \(K_{3}\), משולש. השאלה הראשונה, שעליה אתם יכולים לחשוב בעצמכם, היא איך אפשר לבנות גרף "גדול" (כלומר, עם הרבה קשתות – \(n\) קבוע, זוכרים?) שעדיין לא יכיל משולש. אספיילר אותה כעת מייד אז מי שרוצה לחשוב בעצמו, שיפסיק לקרוא.

התעלול הוא להשתמש במה שנקרא "גרף דו צדדי". גרף דו צדדי הוא כזה שניתן לחלק את צמתיו לשתי קבוצות – הטובים והרעים – כך שכל צומת שייך לאחת מהקבוצות, וכל קשת בהכרח מחברת בין טוב ורע; אין קשת בין שני טובים, או קשת בין שני רעים. בגרף כזה לא יכול להיות משולש, כי בקבוצה של שלושה קודקודים יש שני טובים (שאינם מחוברים בקשת) או שני רעים (שאינם מחוברים בקשת). מצד שני, בגלל שאנחנו יודעים שבגרף דו צדדי מובטח לנו שלא יהיה משולש אנחנו יכולים להתפרע ולהוסיף כמה קשתות שבא לנו כל עוד הן לא מחברות שני טובים או שני רעים. באופן כללי אם יש \(a\) טובים ו-\(b\) רעים וכל טוב מחובר לרע בקשת יהיו לנו \(ab\) קשתות בגרף. מכיוון ש-\(n=a+b\), זה אומר שיהיו לנו \(a\left(n-a\right)=na-a^{2}\) קשתות בגרף, והשאלה היא איזה ערך של \(a\) ייתן לנו את המקסימום. קצת חשבון דיפרנציאלי (אני לא אומר שאין דרכים אחרות, ועוד נראה כאלו) נותן בקלות את התשובה הלא מפתיעה – \(a=\frac{n}{2}\) (אם \(n\) אי זוגי מעגלים כלפי מטה או מעלה, זה לא משנה). כלומר המספר המקסימלי של קשתות מתקבל כאשר מחלקים את הגרף לשתי קבוצות שוות של צמתים, ואז יהיו \(\frac{n^{2}}{4}\) קשתות. כלומר, \(\mbox{ex}\left(n,K_{3}\right)=\frac{n^{2}}{4}\). כל זה היה ידוע בימיו של טורן; המשפט שלו הוא פשוט הכללה רדיקלית שנותנת את \(\mbox{ex}\left(n,K_{t}\right)\)לכל \(t\).

כדי לפשט טיפה את הסימונים מכאן ואילך אניח שאנחנו מנסים למצוא את \(\mbox{ex}\left(n,K_{t+1}\right)\); עוד שניה יהיה ברור לכולם למה עדיף לדבר על \(t+1\) כאן.

הצעד הראשון הוא לנסות ולבנות גרפים גדולים ככל האפשר שאינם מכילים קליק מגודל \(t+1\). ממש מתבקש להכליל כאן את הרעיון שכבר הצגתי – במקום גרף דו-צדדי, לקחת גרף \(t\) צדדי, כלומר כזה שבו הצמתים מחולקים ל-\(t\) קבוצות ואין קשת בין שני חברי אותה קבוצה (אבל כל צומת מקבוצה מסויימת יכול להיות מחובר לכל צומת מכל קבוצה אחרת). ההוכחה שאין בגרף כזה קליק מגודל \(t+1\) זהה: אם יש \(t+1\) צמתים יש לפחות שני צמתים מאותה קבוצה (זהו עקרון שובך היונים בפעולה) ולכן זוג צמתים בלי קשת ביניהם).

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

לצורך פשטות נניח מכאן ואילך ש-\(t\) מחלק את \(n\), אחרת סתם הסימונים שלנו יהיו מסורבלים בהרבה. במקרה הזה, כל הקבוצות יהיו מאותו גודל – \(\frac{n}{t}\). כמה קשתות יהיו? כמו שראינו קודם, בין כל שתי קבוצות של צמתים מחברות \(\frac{n^{2}}{t^{2}}\) קשתות; ויש לנו \({t \choose 2}=\frac{t\left(t-1\right)}{2}\) זוגות (למי שלא מכיר את הסימון הזה – נעים להכיר). לכן יש בסך הכל \(\frac{t\left(t-1\right)}{2}\cdot\frac{n^{2}}{t^{2}}=\frac{t-1}{t}\frac{n^{2}}{2}=\left(1-\frac{1}{t}\right)\frac{n^{2}}{2}\) קשתות.

כעת אפשר לנסח את משפט טורן. פורמלית, הוא אומר ש-\(\mbox{ex}\left(n,K_{t+1}\right)=\left(1-\frac{1}{t}\right)\frac{n^{2}}{2}\), אבל ניסוחים כאלו הם אחד מהדברים השנואים עלי במתמטיקה. לא כי הוא לא נכון או לא מדויק או כל דבר אחר, אלא כי אם זה מה שתראו למישהו מבחוץ הוא לא יבין את הקטע. אוקיי, אז יש לנו איזו נוסחה לא יפה במיוחד עבור \(\mbox{ex}\left(n,K_{t+1}\right)\), אז מה? הפואנטה כאן לטעמי היא שמשפט טורן אומר שהגרפים האקסטרמליים במקרה הזה הם אכן הגרפים ה-\(t\) צדדיים שבנינו – דרך הרבה יותר ציורית ויפה להבין את המספר \(\left(1-\frac{1}{t}\right)\frac{n^{2}}{2}\) (כמובן, לערך המספרי יש חשיבות ביישומים של המשפט). כך זה תמיד במתמטיקה – המטרה היא לא איזו נוסחה סגורה מפוצצת, אלא ההבנה של התופעה שמאחורי הנוסחה (הבנה שלא תהיה שלמה עד שההוכחות לא יסייעו לנו להבין למה הגרפים ה-\(t\) צדדיים הם אכן אקסטרמליים).

אני רוצה להציג שלוש הוכחות למשפט. הראשונה של טורן עצמו שהיא פשוטה ויפה וברורה. השניה של אלון וספנסר שהיא קסם וודו מוחלט, אבל ממחישה יפה את כוחה של השיטה ההסתברותית (שאלון וספנסר כתבו את הספר עליה, תרתי משמע). והשלישית היא אלמנטרית לחלוטין, מבהירה מיידית ובצורה מוחלטת למה הגרפים ה-\(t\) צדדיים הם האקסטרימליים, ולא ברור מי המציא אותה. כל ההוכחות מגיעות מהספר Proofs from THE BOOK שכולל גם שתי הוכחות שלא אראה כאן.

ראשית, ניסוח מדויק של המשפט שכוחו יפה גם ל-\(n\) שלא מתחלק על ידי \(t\): אם \(G\) הוא גרף בעל \(n\) צמתים ואין בו קליק מגודל \(t+1\) (כאשר \(t\ge2\)), אז מספר הקשתות ב-\(G\) הוא לא יותר מ-\(\left(1-\frac{1}{t}\right)\frac{n^{2}}{2}\).

נתחיל עם טורן. טורן מוכיח את המשפט באינדוקציה על \(n\), כש-\(t\) קבוע. כל עוד \(n\le t\) אז לא משנה אילו קשתות יהיו בגרף, לא יוכל להיות בו קליק מגודל \(t+1\) כי אין מספיק צמתים; לכן צריך לוודא שמספר הקשתות הכולל בגרף לא יכול לעלות על החסם. מספר הקשתות המקסימלי האפשרי בגרף עם \(n\) צמתים הוא \(\frac{n\left(n-1\right)}{2}\), ובעזרת אי השוויון \(n\le t\) מקבלים:

\(\frac{n\left(n-1\right)}{2}\le\left(t-1\right)\frac{n}{2}\le\frac{t-1}{t}\cdot\frac{n^{2}}{2}=\left(1-\frac{1}{t}\right)\frac{n^{2}}{2}\)

כך שעם זה סיימנו. החלק המעניין הוא לטפל במקרה שבו \(n>t\). מספיק להראות שבגרף עם מספר קשתות מקסימלי (ביחס לתכונה "לא מכיל את \(K_{t+1}\)) מתקיים החסם הנדרש, כי לכל גרף אחר אפשר להוסיף קשתות עד שמגיעים לגרף מקסימלי שכזה. גרף מקסימלי שכזה בהכרח יכיל את \(K_{t}\) (כי אם לא, הוא לא היה מקסימלי; הוספה של קשת לא הייתה יכול ליצור את \(K_{t+1}\) כי מ-\(K_{t+1}\) אפשר לקבל את \(K_{t}\) על ידי הסרה של קשת אחת וסילוק אחד הצמתים שמחוברים אליה). הרעיון הוא כעת לחלק את הגרף לשני חלקים: \(A\) תהיה קבוצת הצמתים של הקליק מגודל \(t\) הזה, ו-\(B\) תהיה קבוצת שאר הצמתים.

ב-\(A\) יש בדיוק \({t \choose 2}\) קשתות שהרי בין כל זוג צמתים שם יש קשת. על \(B\) אנחנו יכולים להשתמש בהנחת האינדוקציה כי מספר הצמתים בה קטן מ-\(n\), כך שאנחנו יודעים שיש בה לכל היותר \(\left(1-\frac{1}{t}\right)\frac{\left(n-t\right)^{2}}{2}\) קשתות. אילו עוד קשתות יכולות להתקיים בגרף? כאלו שמחברות את \(A\) עם \(B\). כל צומת ב-\(B\) יכולה להתחבר כמעט לכל הצמתים של \(A\), אבל רק כמעט; אם היא תתחבר לכל הצמתים של \(A\), אז היא יחד עם \(A\) יהוו קליק מגודל \(t+1\). לכן כל צומת מ-\(B\) מחוברת בקשת לכל היותר ל-\(t-1\) צמתים מ-\(A\). אלו כל האבחנות שצריך, והיתר הוא חשבון מכולת. אנחנו מקבלים שמספר הקשתות הכולל בגרף חסום על ידי:

\({t \choose 2}+\left(1-\frac{1}{t}\right)\frac{\left(n-t\right)^{2}}{2}+\left(n-t\right)\left(t-1\right)\)

אחרי סידור מחדש קטן מקבלים שזה שווה ל:

\(\left(t-1\right)\left[\frac{t}{2}+\frac{\left(n-t\right)^{2}}{2t}+\left(n-t\right)\right]=\left(t-1\right)\left[\frac{t}{2}+\frac{\left(n-t\right)\left(n+t\right)}{2t}\right]\)

\(=\left(t-1\right)\left[\frac{t^{2}+n^{2}-t^{2}}{2t}\right]=\left(1-\frac{1}{t}\right)\frac{n^{2}}{2}\)

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

כמובן, אין כאן שום קסם אמיתי, זה היופי בהוכחה הזו – התוצאה חייבת להתקבל, אין מנוס מכך. יש לנו כאן דוגמה קלאסית להוכחה באינדוקציה: ראשית, טורן מזהה מרכיב כלשהו שחייב להופיע בגרף אקסטרימלי כלשהו (\(K_{t}\)). האבחנה הזו היא המפתח לנצחון, ומאותו רגע ההמשך מתבקש: לפרק את הגרף, למתוח כמה קשתות שרק אפשר בין הרכיבים, ולהשתמש בהנחת האינדוקציה על מה שנשאר. בעצם טורן מראה כאן ש-\(\mbox{ex}\left(n,K_{t+1}\right)\) מקיים את נוסחת הנסיגה \(\mbox{ex}\left(n,K_{t+1}\right)=\mbox{ex}\left(n-t,K_{t+1}\right)+{t \choose 2}+\left(n-t\right)\left(t-1\right)\) עבור \(n>t\), רק שכאן אין לנו צורך לפתור את הנוסחה הזו כי כבר היה לנו ניחוש מוצלח לגבי הערך של \(\mbox{ex}\left(n,K_{t+1}\right)\) מלכתחילה (בסיטואציות קומבינטוריות אחרות לא יהיה לנו כזה ואז נוסחת נסיגה שכזו תעזור גם להבין מה בדיוק הערך שאנחנו מחפשים).

נעבור כעת להוכחה השניה, של אלון וספנסר. הם לוקחים גרף כלשהו \(G\) בעל \(n\) צמתים שמסומנים לצורך נוחות ב-\(v_{1},\dots,v_{n}\), מסמנים ב-\(d_{i}\) את הדרגה של הצומת \(v_{i}\), כלומר מספר הקשתות שמחוברות אליו. כעת, אם נסמן ב-\(\omega\left(G\right)\) את גודל הקליק הגדול ביותר ב-\(G\), אלון וספנסר טוענים שמתקיים:

\(\omega\left(G\right)\ge\sum_{i=1}^{n}\frac{1}{n-d_{i}}\)

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

אז איך הטענה מסיימת את ההוכחה? כאן שולפים כלי מתמטי סטנדרטי מהשרוול – אי שוויון קושי-שוורץ. לאי השוויון הזה מספר ניסוחים ואבחר את הניסוח הפשוט יחסית שרלוונטי עבורנו: אם \(a_{1},\dots,a_{n}\) ו-\(b_{1},\dots,b_{n}\) הן סדרות מספרים אז:

\(\left(\sum_{i=1}^{n}a_{i}b_{i}\right)^{2}\le\left(\sum_{i=1}^{n}a_{i}^{2}\right)\left(\sum_{i=1}^{n}b_{i}^{2}\right)\)

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

השימוש כאן בקושי-שוורץ הוא פשוט יחסית. נבחר \(a_{i}=\sqrt{n-d_{i}}\) ו-\(b_{i}=\left(\sqrt{n-d_{i}}\right)^{-1}\), נציב בנוסחה ונקבל:

\(n^{2}\le\left(\sum_{i=1}^{n}\left(n-d_{i}\right)\right)\left(\sum_{i=1}^{n}\frac{1}{n-d_{i}}\right)\le\omega\left(G\right)\sum_{i=1}^{n}\left(n-d_{i}\right)\)

עכשיו יש לנו עוד שני תעלולים לשלוף מהשרוול: ראשית, אנחנו מניחים ש-\(\omega\left(G\right)\le t\) – זו ההנחה הבסיסית שלנו, לפיה הגרף לא מכיל את הקליק \(K_{t+1}\). שנית, יש לנו דרך לקשר בין הדרגות של כל הצמתים בגרף ובין מספר הקשתות בו. אם מספר הקשתות הוא \(e\), אז בכל גרף (סופי) שהוא מתקיים השוויון \(2e=\sum_{i=1}^{n}d_{i}\), שכן כל קשת בגרף תורמת 1 לדרגות של שני הצמתים שהיא מחוברת אליהם. מכל אלה אפשר להסיק כעת:

\(n^{2}\le t\cdot\left(n^{2}-2e\right)\)

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

\(2et\le n^{2}\left(t-1\right)\)

חלוקה ונקבל:

\(e\le\left(1-\frac{1}{t}\right)\frac{n^{2}}{2}\)

בדיוק מה שרצינו.

בינתיים זה היה טכני ולא הכי מעניין, אני חייב להודות; לב ההוכחה הוא בטענה \(\omega\left(G\right)\ge\sum_{i=1}^{n}\frac{1}{n-d_{i}}\) וההוכחה ההסתברותית שלה שאציג כעת.

במבט ראשון לא ברור איך הסתברות יכולה להשתחל לכאן. הגרף \(G\) נתון וקבוע; מה בדיוק נגריל ואיך? הרעיון של אלון וספנסר הוא להגריל סדר על הצמתים – פורמלית, פרמוטציה \(\pi\) כלשהי שלהם, כשכל פרמוטציה נבחרת בהסתברות שווה, \(\frac{1}{n!}\). נניח שהצמתים \(v_{1},\dots,v_{n}\) כבר מסודרים על פי הפרמוטציה הזו, ונגדיר קבוצת צמתים \(C_{\pi}\) שמכילה את כל הצמתים \(v_{i}\) שמחוברים בקשת לכל הצמתים שבאים לפניהם בפרמוטציה, כלומר לכל \(v_{j}\) כך ש-\(j<i\).

הנקודה המהותית כאן היא ש-\(C_{\pi}\) היא קליק. למה? ובכן, קחו ב-\(C_{\pi}\) את הצומת עם האינדקס המקסימלי; על פי הגדרה, הוא מחובר לכל הצמתים עם אינדקס קטן יותר ובפרט לכל צמתי \(C_{\pi}\). כעת קחו את הצומת המקסימלי הבא בתור… הבנתם את הרעיון.

יפה, אז הצלחנו להגדיר איכשהו מרחב הסתברות שמערב קליקים. אנחנו מעוניינים בחסם כלשהו על גדלי הקליקים, אז נגדיר משתנה מקרי \(X=\left|C_{\pi}\right|\) – גודל \(C_{\pi}\). בגלל האופן שבה \(C_{\pi}\) נבנתה, קל לפרק את \(X\) לסכום של אינדיקטורים (משתנים מקריים שמקבלים 0 או 1 בלבד): \(X=\sum_{i=1}^{n}X_{i}\) כאשר \(X_{i}\) מקבל 1 אם \(v_{i}\) מחובר בקשת לכל הצמתים שקדמו לו.

כעת השאלה הפשוטה היא – מה ההסתברות ש-\(X_{i}=1\)? מכיוון שכל הקשתות כבר נקבעו, זה תלוי בדרגה של \(v_{i}\): אם \(v_{i}\) מחובר ל-\(d_{i}\) צמתים, ההסתברות לכך שכל הצמתים שיהיו לפני \(v_{i}\) בפרמוטציה יהיו מתוך \(d_{i}\) הצמתים שהוא מחובר אליהם היא בעצם ההסתברות שמבין כל \(n-d_{i}\) הצמתים שאינם מחוברים אל \(v_{i}\), כולל \(v_{i}\) עצמו, יהיה זה \(v_{i}\) שמופיע ראשון. מכיוון שיש סימטריה בין כל \(n-d_{i}\) הצמתים הללו, ההסתברות לכך היא \(\frac{1}{n-d_{i}}\) (אתם מוזמנים לעשות חישוב פורמלי אם לא שוכנעתם).

זה מסיים את העניין אם זוכרים מה קורה בדרך כלל בשלב הזה בשיטה ההסתברותית. תוחלת של אינדיקטור היא ההסתברות שהוא יקבל 1, כלומר \(\mbox{E}\left[X_{i}\right]=\frac{1}{n-d_{i}}\). לינאריות התוחלת נותנת לנו כעת

\(\mbox{E}\left[X\right]=\mbox{E}\left[\sum_{i=1}^{n}X_{i}\right]=\sum_{i=1}^{n}\mbox{E}\left[X_{i}\right]=\sum_{i=1}^{n}\frac{1}{n-d_{i}}\)

ואנחנו מסיימים כי במרחב ההסתברות שלנו חייב להיות איבר שנותן ל-\(X\) לפחות את ערך התוחלת שלו, כלומר קליק שגודלו לפחות \(\sum_{i=1}^{n}\frac{1}{n-d_{i}}\).

שלא יהיה לכם ספק; אני לא מקבל שום אינטואיציה ל"מה הולך פה" מההוכחה הזו. היא פשוט מגניבה.

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

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

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

למה אם הטענה נכונה הגרף הוא \(k\) צדדי מלא? ובכן, למי שמכיר את המושג: כי היחס "\(u,v\) לא מחוברים בקשת" הוא יחס שקילות; ולמי שלא מכיר, אפשר לבנות את הצדדים כך – ניקח צומת תמים \(u\), ונגדיר את "הצד של \(u\)" בתור אוסף כל הצמתים ש-\(u\) לא מחובר אליהם. לא ייתכן שבקבוצה הזו יהיו שני צמתים \(v,w\) שמחוברים בקשת (כי אז העובדה ש-\(u\) לא מחובר לאף אחד מהם סותרת את הטענה שלנו), לכן זה אכן צד חוקי של גרף \(k\) צדדי. בנוסף, אם ניקח צומת \(v\) כלשהו בצד הזה, הוא יהיה חייב להיות מחובר לכל צומת שאינה באותו צד איתו; כי אם יש צומת \(w\) שאינה באותו צד איתו אז על פי הגדרת הצד, \(w\) מחובר ל-\(u\), ולא ייתכן ש-\(v\) לא יהיה מחובר לא ל-\(u\) ולא ל-\(w\).

יפה, אז יש לנו אפיון לוקלי פשוט, וכל שצריך להראות הוא שהאפיון מתקיים בגרף האקסטרמלי. נניח בשלילה שהוא לא, אז יש לנו שלושה צמתים בגרף: \(u,v,w\), כך ש-\(u,v\) מחוברים בקשת ואילו \(w\) לא מחובר לאף אחד מהם. הרעיון הוא לבנות עכשיו מהגרף הקיים גרף חדש שבו יש יותר קשתות ואותו מספר צמתים ועדיין אין בו את \(K_{t+1}\), בסתירה לאקסטרימליות של הגרף שלנו.

איך עושים את זה? פשוט: מעיפים מהגרף את אחד מהצמתים \(u,v,w\) שיש לו מעט קשתות ושמים במקומו עותק של אחד מהצמתים האחרים. אם למשל מתקיים ש-\(d\left(u\right)>d\left(w\right)\), אז נעיף מהגרף את \(w\); בכך איבדנו \(d\left(w\right)\) קשתות. כפיצוי, נוסף לגרף צומת \(u^{\prime}\) שמחובר בדיוק לאותם צמתים ש-\(u\) מחובר אליהם; זה ייתן לנו עוד \(d\left(u\right)\) קשתות, כלומר הרווחנו. לא קשה לראות שהוספת \(u^{\prime}\) לגרף לא יכולה ליצור קליק מגודל \(t+1\): אם יש קליק כזה, אז היה קליק כזה גם בגרף המקורי, רק עם \(u\) במקום \(u^{\prime}\) (לא ייתכן שיש קליק שמערב הן את \(u\) והן את \(u^{\prime}\) יחד, שכן אין קשת ביניהם).

באופן דומה מטפלים במקרה שבו \(d\left(v\right)>d\left(w\right)\). המקרה היחיד שנותר לנו הוא זה שבו \(d\left(w\right)\ge d\left(u\right),d\left(v\right)\). כאן נעיף מהגרף את \(u,v\) שניהם גם יחד ונשים שני עותקים של \(w\); הסיבה שבגללה נרוויח כך קשת היא שכשמסירים את \(u,v\) לא מאבדים \(d\left(u\right)+d\left(v\right)\) קשתות אלא רק \(d\left(u\right)+d\left(v\right)-1\) קשתות, שכן הקשת המשותפת של \(u,v\) מוסרת רק פעם אחת. זה מסיים את ההוכחה הזו.

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

בעיית וויל האנטינג

פורסם בתאריך 18 בפברואר 2010 על ידי gadial

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

ובכן, נתון גרף (ראו תמונה) ונשאלות עליו השאלות הבאות:

מצאו את מטריצת השכנויות \(A\) של הגרף \(G\).
מצאו את המטריצה שנותנת את מספר המסלולים מאורך 3 ב-\(G\).
מצאו את הפונקציה היוצרת של המסלולים מ-\(i\) אל \(j\).
מצאו את הפונקציה היוצרת של המסלולים מ-\(1\) אל \(3\).

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

הבה ונבהיר מה בעצם רוצים בשאלה הזו. ראשית, נותנים גרף \(G\) על ידי ציור. גרף מורכב (כפי שניתן לראות בציור) מאוסף של עיגולים – "הצמתים" – וקווים שמחברים חלק מהם – "הקשתות". כך למשל בין הצומת 1 לצומת יש קשת אחת, בין 2 ו-3 יש שתי קשתות, בין 1 ו-3 אין אף קשת וכו'. מסלול בגרף מתחיל מצומת א', ואז מבצע סדרת "צעדים", כשכל צעד הוא מעבר מהצומת הנוכחי לצומת שמחובר לצומת הנוכחי בקשת. אם יש כמה קשתות בין שני צמתים, לרוב זה נחשב כאילו יש מספר דרכים לעבור בין שני הצמתים. כך למשל אפשר לקבל את המסלולים הבאים מצומת 1 לצומת 3 מאורך 2: ראשית הולכים מצומת 1 לצומת 2, ולאחר מכן הולכים מ-2 ל-3, אלא שיש שתי דרכים לעשות זאת כי יש שתי קשתות בין 2 ו-3. לכן יש שני מסלולים מאורך 2 מ-1 אל 3.

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

\(A=\left(\begin{array}{cccc}0 & 1 & 0 & 1\\1 & 0 & 2 & 1\\0 & 2 & 0 & 0\\1 & 1 & 0 & 0\end{array}\right)\)

עד כאן, שום דבר מורכב. התחכום מתחיל בשאלה הבאה – מי שלא בקיא בתורת הגרפים האלגברית (או בתחומים אחרים שבהם אותם רעיונות מופיעים, כמו למשל הילוכים מקריים בדידים) יכול לתהות מה הקשר בין מטריצה ובין מספר המסלולים ומה הולך כאן. כאן נכנסת לתמונה הפעולה של כפל מטריצות. מכיוון שמושג המטריצה, והמוטיבציה להגדרת כפל המטריצות באופן שבו הוא מוגדר, ראויים שניהם לפוסט שלם, לא אכנס לכך בינתיים אלא אניח כי ההגדרות מוכרות כבר לקורא (ועם מי שטרם יודעים הסליחה). כדי לראות כיצד כפל מטריצות עוזר לנו ניאלץ לשלוף את ההגדרה הפורמלית-טכנית של הכפל. אם נכפול את \(A\) בעצמה, אז בקוארדינטה ה-\(i,j\) של המכפלה נקבל את \(\sum_{k=1}^{n}a_{ik}a_{kj}\). מה המספר הזה אומר? לכל \(k\), \(a_{ik}\cdot a_{kj}\) הוא מכפלה של מספר המסלולים מאורך 1 מ-\(i\) ל-\(k\), במספר המסלולים מאורך 1 מ-\(k\) אל \(j\). כלומר, זה מייצג את מספר הדרכים להגיע בשני צעדים מ-\(i\) אל \(j\) תוך מעבר בצומת הביניים \(k\). כשסוכמים זאת על כל הערכים האפשריים של \(k\) מקבלים את כל הדרכים לעבור מ-\(i\) אל \(j\) ב-2 צעדים.

באופן דומה אם נכפול את \(A^{2}\) ב-\(A\), הקוארדינטה ה-\(i,j\) תהיה סכום של מכפלות, כשכל מכפלה היא של מספר הדרכים להגיע מ-\(i\) אל \(k\) בשני צעדים, ומ-\(k\) אל \(j\) בצעד אחד. אני מקווה שהרעיון ברור: לכל \(m\) טבעי, הקוארדינטה ה-\(i,j\)-ית במטריצה \(A^{m}\) מייצגת את מספר המסלולים מאורך \(m\) מ-\(i\) אל \(j\) (אפילו עבור \(m=0\) זה עובד: \(A^{0}\) היא על פי הגדרה המטריצה שבה הכניסה ה-\(i,i\) היא 1 לכל \(i\), וה-\(i,j\) היא 0 אם \(i\ne j\), וזה מתאים ל"מסלול מאורך 0" מ-\(i\) לעצמו שפשוט לא מכיל צעדים). מכאן שכדי לענות על שאלה 2 בסך הכל צריך לחשב את \(A^{3}\). זה חישוב טכני לא מעניין במיוחד ואפשר לתת לתוכנות מחשב דוגמת מטלאב לבצע אותו. מקבלים:

\(A^{3}=\left(\begin{array}{cccc}2 & 7 & 2 & 3\\7 & 2 & 12 & 7\\2 & 12 & 0 & 2\\3 & 7 & 2 & 2\end{array}\right)\)

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

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

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

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

ובכן, מה שמבקשים מאיתנו הוא הצגה מפורשת לפונקציה \(f\left(x\right)=\sum_{n=0}^{\infty}b_{n}x^{n}\) כאשר \(b_{n}\) הוא מספר המסלולים מ-\(i\) אל \(j\) מאורך \(n\). אם נסמן ב-\(\left[A\right]_{ij}\) את הכניסה ה-\(i,j\) של המטריצה \(i,j\) וננפנף בידיים ממש מהר, נקבל את החישוב הבא: \(\sum_{n=0}^{\infty}b_{n}x^{n}=\sum_{n=0}^{\infty}\left[A^{n}\right]_{ij}x^{n}=\sum_{n=0}^{\infty}\left[\left(Ax\right)^{n}\right]_{ij}=\left[\sum_{n=0}^{\infty}\left(Ax\right)^{n}\right]_{ij}=\left[\frac{1}{1-Ax}\right]_{ij}\).

מה שעשיתי כאן היה להשתמש בוריאציה על הנוסחה הישנה והטובה לסכום סדרה הנדסית אינסופית מתכנסת: \(1+x+x^{2}+\dots=\frac{1}{1-x}\). כמובן שצריך להצדיק את השימוש בה עבור מטריצות, אבל אמרתי שאנפנף בידיים.

כעת השאלה היא האם באופן כללי בהינתן מטריצה \(B\), יש נוסחה "יפה"עבור הכניסה ה-\(ij\) בהופכית שלה, כלומר \(\left[B^{-1}\right]_{ij}\)? התשובה היא שכן (אם כי "יפה" זה עניין סובייקטיבי כאן) והיא מכונה "כלל קרמר". הכלל מסתמך על שני מושגים לא פשוטים – מטריצה מצורפת (Adjugate) ודטרמיננטה של מטריצה, ולכן עבור מי שאינו מכיר את המושגים הללו הנוסחה תיראה פשוט כמו אוסף של סימנים חסרי משמעות – אבל זה לא חשוב כל כך לבינתיים. הנקודה היא ששני היצורים הללו ניתנים לחישוב יחסית באופן פשוט. כעת, כלל קרמר אומר כי \(B^{-1}=\frac{\mbox{Adj}B}{\det B}\) (כאן אנו מחלקים מטריצה – \(\mbox{Adj}B\) – בסקלר – \(\det B\)). לכן \(\left[B^{-1}\right]_{ij}=\frac{\left[AdjB\right]_{ij}}{\det B}\). אם רוצים לפשט את הביטוי עוד יותר צריך לחפור בהגדרה של \(\mbox{Adj}B\): הכניסה ה-\(ij\) של \(\mbox{Adj}B\) מוגדרת בתור \(\left(-1\right)^{i+j}M_{ji}\), כאשר \(M_{ji}\) הוא המינור ה-\(ji\)-י של \(B\) – הדטרמיננטה של המטריצה שמתקבלת ממחיקת השורה ה-\(j\) והעמודה ה-\(i\) של \(B\). כאן כנראה וויל משתעמם ומשתמש בסימונים שאיני מכיר, כי הנוסחה הסופית שהוא כותב על הלוח היא \(\frac{\det\left(B_{ij}\right)}{\det B}\) – אני משער שכוונתו זהה לכוונה שלי (למעשה, הוא לא כותב \(B\) אלא \(I-Ax\) כמו שכתבתי קודם – ולמעשה, אפילו לא את זה, אלא \(I-zA\), שכמובן אומר את אותו הדבר בדיוק).

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

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

מים, חשמל וגז, והקשר שלהם לגרפים מישוריים

פורסם בתאריך 29 בספטמבר 2008 על ידי gadial

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

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

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

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

נתחיל בתזכורת קצרה. גרף מתמטי (מהסוג שעליו אנחנו מדברים עליו – לא זה שהוא שרטוט של פונקציה) הוא אוסף של צמתים, שמסומנים לרוב בנקודות או בעיגולים, וקשתות שמחברות חלק מזוגות הצמתים. באופן כללי גרף לא צריך להיות מתואר באמצעות ציור; מספיק לתאר אותו באמצעות קבוצת הצמתים (שיכולה פשוט להיות קבוצה של מספרים: "צומת מס' 1", "צומת מס' 2" וכו') וקבוצת הקשתות ("צומת 3 מחובר לצומת 5"…). כל גרף ניתן לצייר בהמוני דרכים שונות על נייר, בפרט אם לא דורשים שהקשתות יהיו קווים ישרים; הנה דוגמה לאותו גרף כשאנו מציירים אותו בשתי דרכים שונות:

מה שמעניין כאן הוא שבציור השמאלי, הקשתות של הגרף חותכות זו את זו (הקשת שמחברת את 2 עם 3 חותכת את הקשת שמחברת את 4 עם 1), אבל בציור הימני אף קשת לא חותכת זו את זו. מכאן אנו למדים שהתכונה "אם מציירים את הגרף על נייר, אין שתי קשתות שחותכות זו את זו" איננה טריוויאלית לחלוטין; יכולים להיות גרפים שהתיאור הרגיל שלהם על הנייר נראה מסובך ומלא חיתוכים פנימיים, אבל אפשר איכשהו לצייר אותם בלי שאף שתי קשתות יחתכו זו את זו. לגרף כזה, שניתן לצייר איכשהו על נייר דו ממדי ("מישור") מבלי שאף שתי קשתות יחתכו זו את זו קוראים "גרף מישורי" (Planar Graph).

כעת יש לנו ניסוח טוב יותר של חידת המים-חשמל-גז: האם הגרף הבא הוא מישורי?

לגרף הזה יש שם: "הגרף הדו צדדי השלם עם 3 על 3 צמתים". גרף דו צדדי הוא גרף שניתן לחלק את צמתיו לשתי קבוצות (ללא איברים משותפים), כך שאין קשת בין אברי אותה קבוצה (ובמילים אחרות – קשת עוברת רק בין איבר מקבוצה א' לאיבר מקבוצה ב'). כאן אברי הקבוצה האחת מסומנים במספרים, ואברי הקבוצה האחרת – באותיות. בדוגמה המקורית קבוצה אחת הייתה קבוצת הבתים, והקבוצה השנייה הייתה קבוצת המקורות. פירוש המילה "שלם" כאן היא שכל קשת אפשרית (שתשאיר את הגרף דו-צדדי) קיימת בגרף – כל צומת מקבוצה א' מחובר לכל צומת מקבוצה ב'. ה"3 על 3 צמתים" פירושו שכל אחת משתי הקבוצות היא מגודל 3. את הגרף הדו צדדי הספציפי הזה מסמנים בתור \(K_{3,3}\) (באופן כללי, \(K_{p,q}\) פירושו גרף דו צדדי שלם על קבוצות מגודל \(p\) ו-\(q\)).

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

אם כן, הניסוח הסטנדרטי של המשפט המתמטי שהורג את חידת המים-חשמל-גז הוא "הגרף \(K_{3,3}\) איננו מישורי". אביא כאן שתי הוכחות לטענה הזו; האחת ישירה למדי, וקרוב לודאי שכל ילד מסוגל להבין אותה. לרוע המזל, היא גם קרובה ככל שהדבר ניתן אל אותו שיקוץ שהמתמטיקאים מכנים "הוכחה באמצעות ציור"; הדרך היחידה לפרמל אותה בצורה שתשביע את רצונו של כל מתמטיקאי קפדן היא באמצעות שימוש במשפט כבד למדי – משפט עקומת ז'ורדן. משפט ז'ורדן אומר דבר מה שנראה טריוויאלי לחלוטין – שכל עקומה (לצורך העניין עקומה היא מה שמקבלים כששמים עיפרון על דף ומציירים בלי להרים את העיפרון מהדף) שלא חותכת את עצמה ושני קצותיה מתלכדים מחלקת את העולם (הדף שעליו ציירנו) ל"פנים" ו"חוץ", ולא ניתן להגיע מהאחד לשני בלי לחתוך את העקומה בדרך. למרות שהמשפט נשמע טריוויאלי, הוכחתו מסובכת למדי. מצד אחד, זה נשמע אבסורדי. מצד שני, חשוב להבין שהמושג המדוייק של עקומה מוגדר בצורה יותר מורכבת ממה שהצגתי כאן (מה שהצגתי כאן לא ראוי להיקרא "הגדרה"), ולפורמליזם ולדיוק הזה יש מחיר.

הרעיון הבסיסי הוא זה: נסתכל על המעגל שנוצר מחיבור הקשתות 1-א'-2-ב'-3-ג'-1 (הקשת מ-1 אל א'; הקשת מא' אל 2, וכו'). זה לא מעגל במובן הרגיל מגאומטריה, אלא פשוט מסלול בגרף שמתחיל ומסתיים באותו מקום. בכל צורה שבה נצייר את הגרף במישור, אוסף כל הקשתות הללו יתחום איזור כלשהו ויחלק אותו ל"פנים" ו"חוץ". גם את זה כדאי להמחיש עם ציור:

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

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

אם כן, נמתח את הקשת בחוץ ונקבל משהו שכזה:

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

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

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

שאלה מעניינת היא האם מספר הפאות של גרף נובעות מאופן הציור שלו, או שלא משנה איך נצייר אותו, תמיד נקבל אותו מספר פאות (כך שמספר הפאות הוא שמורה (invariant) של הגרף). התשובה היפה יותר, מבחינה מתמטית, היא השנייה; ואכן, מסתבר שכך הדבר, אבל טוב מכך – יש קשר פשוט להדהים בין מספר הפאות של הגרף ובין מספר הצמתים והקשתות שלו. אם הגרף קשיר (כלומר, יש מסלול מכל צומת לכל צומת אחר), בעל \(n\) צמתים, \(m\) קשתות ו-\(f\) פאות, אז מתקיים \(n-m+f=2\). ההוכחה היא אינדוקטיבית על מספר הפאות, ואינה מסובכת במיוחד; אם יש רק פאה אחת, אז בהכרח הגרף הוא עץ, דהיינו גרף קשיר וחסר מעגלים (כי אחרת היה בו מעגל, ועל פי משפט ז'ורדן זה היה גורר שתי פאות), וידוע שבעץ מתקיים \(m=n-1\); וכאשר יש לנו \(f+1\) פאות אפשר לבחור קשת שנמצאת על מעגל, להסיר אותה, לקבל פאה אחת פחות (כי איחדנו שתי פאות) וקשת אחת פחות וגרף שעודנו קשיר, כך שניתן להשתמש עליו בהנחת האינדוקציה. ההכללה של הנוסחה לגרפים שאינם קשירים אינה מסובכת; חשבו על כך שכל גרף ניתן להציג כאיחוד זר של גרפים קשירים.

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

חזרה לגרף \(K_{3,3}\) האומלל. מכיוון שיש בו (קל לספור) \(n=6\) צמתים ו-\(m=9\) קשתות, נוסחת אוילר מראה לנו מייד שאם הוא מישורי, אז בכל ציור שלו במישור יהיו לו \(f=2+m-n=5\) פאות. כעת נשים לב כי ניתן לספור את \(m\) באמצעות הפאות. אם \(p\) היא פאה כלשהי של הגרף, ו-\(d(p)\) הוא מספר הקשתות שנמצאות בפאה הזו (בתוכה או על השפה שלה), אז נקבל ש-\(m\ge\frac{1}{2}\sum d(p)\) כשהסכום נלקח על כל הפאות של הגרף; זאת מכיוון שאנו סופרים כל קשת לכל היותר פעמיים כי היא שייכת לכל היותר לשתי פאות (יש קשתות שנמצאות כולן בפאה אחת; לפעמים מסכימים לספור אותן פעמיים כדי שיתקבל שוויון מלא בנוסחה, אך אין לנו צורך בכך כאן).

כעת לפואנטה. בגרף שמכיל יותר מפאה אחת, כל פאה נקבעת באמצעות מעגל שיוצרות הקשתות שעל שפתה; אבל בגרף הדו צדדי, האורך המינימלי של מעגל הוא 4 (בדרך כלל הוא 3, אבל כאן זה בלתי אפשרי – מדוע?) ולכן \(d(p)\ge 4\). לכן נקבל:

\(9=m\ge\frac{1}{2}\sum d(p)\ge\frac{1}{2}\cdot f\cdot 4=2f=10\)

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

הבטחתי שיש לחידת המים-חשמל-גז חשיבות רבה במתמטיקה, הרבה מעבר למה שנדמה; כעת אסביר מדוע. ראשית, אציג עוד גרף חביב ומוכר: \(K_5\), "הגרף השלם על 5 צמתים". ההבדל המהותי בין גרף זה לגרף \(K_{3,3}\) הוא ש-\(K_5\) אינו דו צדדי; כל אחד מחמשת צמתיו מחובר לארבעת הצמתים האחרים. זה נראה ככה:

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

מה שמעניין ב-\(K_5\) זה שהוא הגרף השלם הקטן ביותר שאינו מישורי; כבר ראינו בפוסט זה עצמו ש-\(K_4\) הוא מישורי (חזרו לציור שבתחילת הפוסט). ההוכחה ש-\(K_5\) אינו מישורי דומה באופיה להוכחה ש-\(K_{3,3}\) אינו מישורי, אך מסובכת מעט יותר ולא אביא אותה כאן. הסיבה לכך שטורחים להוכיח את אי המישוריות של שני הגרפים הללו דווקא היא שמתברר כי די בכך כדי לאפיין את כל הגרפים שאינם מישוריים: כל גרף שאינו מישורי יכיל, בצורה מסויימת, אחד משני הגרפים הללו – או את \(K_{3,3}\) או את \(K_5\).

צריך קצת להיזהר בכל הנוגע ל"צורה מסויימת" – בפירוש אין הכוונה לכך שכל גרף לא מישורי יכיל אחד משני הגרפים הללו כתת-גרף (כלומר, מה שנשאר אחרי שמוחקים חלק מהצמתים ואת הקשתות שנגעו באותם צמתים). ישנם שני משפטים שונים, הראשון של ווגנר והשני של קורטובסקי, שנותנים שני אפיונים שונים של גרפים מישוריים המשתמשים ב \(K_{3,3}\) ו-\(K_5\).

ווגנר מדבר על מה שנקבל מהגרף שאנו בודקים באמצעות סדרה של כיווצים (Contractions), כש"כיווץ" הוא פעולה שבה לוקחים קשת כלשהי ומאחדים את שני הצמתים שבקצותיה לצומת בודד, שמחובר לכל מי ששני הצמתים המקוריים חוברו אליו. פרט לכך ווגנר מתיר גם מחיקת קשתות, וסילוק מהגרף של צמתים שאף קשת לא מחוברת אליהם. אם ניתן באמצעות שלוש הפעולות הללו להגיע אל \(K_{3,3}\) או אל \(K_5\), אז על פי ווגנר הגרף אינו מישורי; ואחרת הוא כן. למעשה, התוצאה הזו היא רק בסיס לתיאוריה כללית יותר העוסקת בגרפים ובהגדרה שלהם באמצעות "מינורים אסורים" (מינור של גרף הוא כל גרף שניתן לקבל ממנו על ידי הפעולות שלעיל), ויש לה שימושים אפילו בלוגיקה; אך לא אכנס לזה כעת.

האפיון השני, של קורטובסקי, עוסק בפעולה "הפוכה" לכאורה, של הרחבה. בהינתן גרף, אפשר לקחת קשתות ולתקוע להן צמתים "באמצע" (כלומר, להוסיף צמתים שמחוברים אך ורק לשני הצמתים שבמקור היו קצות הקשת הזו). הגרף שמתקבל נקרא "תת-חלוקה" (Subdivision) של הגרף המקורי. קורטובסקי אומר שגרף איננו מישורי אם ורק אם יש לו תת גרף שהוא חלוקה של אחד משני הגרפים \(K_{3,3}\) או אל \(K_5\).

ויקיפדיה האנגלית מביאה דוגמה נאה להמחשת שני המשפטים:

הגרף הזה נראה "כמעט" כמו \(K_{3,3}\), אבל הוא אינו מכיל כתת גרף לא את \(K_{3,3}\) ולא את \(K_5\). מצד שני, הוא די בבירור התקבל מ-\(K_{3,3}\) על ידי הוספת הצומת B באמצע הקשת CF, כלומר הוא חלוקה של \(K_{3,3}\) ולכן על פי קורטובסקי הוא אינו מישורי; ואם נכווץ את הגרף על ידי כך שנאחד את B עם C (או את B עם F) נקבל את \(K_{3,3}\) ולכן על פי ווגנר הוא אינו מישורי.

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

“הוא חיפש על העץ…”

פורסם בתאריך 18 במאי 2008 על ידי gadial

להגיב

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

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

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

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

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

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

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

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

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

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

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

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

הרעיון בעצים (ובאח הקטן שלהם, רשימות מקושרות) הוא לשמור את המידע ב"תפזורת" בתוך הזכרון של המחשב – כל פריט מידע מאוחסן בשטח משלו, בלי הרציפות שמערך מבטיח. הרעיון הוא שכל פריט מידע "מצביע" על פריטי מידע אחרים – כלומר, זוכר את הכתובת שלהם. למשל, ברשימה מקושרת עם האיברים , A,B, כל מה שצריך לזכור הוא את כתובת A; ב-A עצמו יש את הכתובת של B וב-B את הכתובת של C, כך שאם רוצים להגיע ל-C צריך רק "לטייל" על הרשימה.

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

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

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

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

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

דוגמת עצי החיפוש היא סטנדרטית ובסיסית; משתמשים בהם בכל מקום. עם זאת, אני חותר לדוגמה שלטעמי היא מעניינת עוד יותר, ובעלת יישומים מפתיעים יותר – עצי סיומות (Suffix trees) ושימושיהם בחיפוש מילים בטקסט ובכיווץ מידע.

איך אוילר עוזר לנו לבנות בתים ולטייל על גשרים

פורסם בתאריך 6 במאי 2008 על ידי gadial

שעשוע ידוע שנהוג לתת לילדים הוא זה:

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

אחרי שהילדים פותרים את החידה הזו, נותנים להם חדשה דומה מאוד, זו:

מה ההבדל המהותי בין שני המקרים? והאם יש שיטה כללית ("אלגוריתם") שבודקת האם ניתן לצייר במשיכה אחת צורה כלשהי, ואם כן, איך?

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

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

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

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

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

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

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

הנה דוגמאות סטנדרטיות לגרפים:

הגרף השני מכוון והראשון לא, אבל פרט לכך אלו בדיוק אותם גרפים; אותם קודקודים (A,B,C,D,E) ואפילו אותן קשתות. אם מוחקים את החצים מהקשתות בגרף השני, מקבלים את הגרף הראשון (אומרים בכזו סיטואציה שהגרף הלא מכוון הוא "גרף התשתית" של הגרף המכוון). זוהי דרך הציור הסטנדרטית והמקובלת של גרפים (למי שתוהה, הגרפים הללו ציורו באמצעות התוכנות שבחבילה graphviz, שמאפשרות ציור אוטומטי של גרפים אם מספקים תיאור סכמטי טקסטואלי פשוט שלהם. מומלץ בחום).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

לא מדויק

"There’s no sense in being precise when you don’t even know what you’re talking about" (ג'ון פון נוימן)

ארכיון הקטגוריה: תורת הגרפים