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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


נהניתם? התעניינתם? אם תרצו, אתם מוזמנים לתת טיפ:

Buy Me a Coffee at ko-fi.com