משפט קירכהוף (מכונה גם משפט מטריצת העץ של קירכהוף) נותן את מספר העצים הפורשים בגרף. עבור גרף G עם n קודקודים הלפלסיאן L הוא המטריצה L = D - A. D היא מטריצת הדרגות, מטריצה אלכסונית שבה דרגת כל קודקוד מופיעה על האלכסון. A היא מטריצת השכנויות.
הערכים העצמיים (eigenvalues, מספרים שמראים תכונות חשובות של המטריצה) של L מסודרים כך ש־
0 = λ0 ≤ λ1 ≤ ... ≤ λ_{n-1}, וכלם לא שליליים. הערך λ0 שווה ל־0, והווקטור העצמי המתאים לו הוא [1,1,…,1]. מספר הפעמים ש־0 מופיע בין הערכים העצמיים שווה למספר רכיבי הקשירות של הגרף. לכן, אם הגרף קשיר, כל הערכים λ1,...,λ_{n-1} חיוביים.
יהי G גרף קשיר בעל n קודקודים, ויהיו λ1,...,λ_{n-1} הערכים העצמיים השונים מאפס של הלפלסיאן L. מספר העצים הפורשים של G, t(G), נתון על ידי:
t(G) = (1/n)·λ1·λ2·...·λ_{n-1}.
במילים אחרות, מספר העצים הפורשים שווה למינור של L.
נוסחת קיילי היא מקרה פרטי של משפט קירכהוף. בלפלסיאן של גרף שלם בעל n קודקודים כל הערכים העצמיים השונים מאפס שווים ל־n. לכן מכפלתם היא n^{n-1} והחלוקה ב־n נותנת t(G)=n^{n-2}, כפי שקיילי קבע.
משפט קירכהוף מסביר איך לחשב כמה עצים פורשים יש בגרף. מטריצה (טבלה של מספרים) חשובה כאן נקראת הלפלסיאן. הלפלסיאן L נוצרת מ־D - A. D היא טבלה עם דרגות הקודקודים על האלכסון. דרגה = כמה שכנים יש לקודקוד. A היא טבלת השכנויות, שמראה מי מחובר למי.
ערכים עצמיים (מספרים מיוחדים של המטריצה) של הלפלסיאן אינם שליליים. אחד הערכים האלה הוא 0. וקטור (רשימה של מספרים) כמו [1,1,…,1] מתאים לערך 0. מספר הפעמים ש־0 מופיע הוא מספר החלקים הנפרדים בגרף. אם הגרף מחובר, יש רק ערך 0 אחד.
אם הגרף מחובר ובו n קודקודים, מחשבים את כל הערכים העצמיים שאינם 0. מכפילים אותם יחד. אחרי זה מחלקים ב־n. התוצאה היא מספר העצים הפורשים.
בגרף שלם, שבו כל שני קודקודים מחוברים, כל הערכים העצמיים שאינם 0 שווים ל־n. לכן מספר העצים הוא n^{n-2}.
תגובות גולשים