משפט קירכהוף

בתחום המתמטי של תורת הגרפים משפט קירכהוף או משפט מטריצת העץ של קירכהוף, הנקרא על שם הפיזיקאי הגרמני גוסטב קירכהוף, מספק את מספר העצים הפורשים בגרף. המשפט הוא הכללה לנוסחת קיילי הקובעת כי מספר העצים הפורשים בגרף שלם בעל n צמתים הוא $\ n^{n-2}$.

הלפלסיאן של גרף

עבור גרף $G$ בעל $n$ קודקודים הלפלסיאן $L$ של $G$ הוא המטריצה $L$ המתקבלת מההפרש בין מטריצת הדרגות (מטריצה אלכסונית בה דרגות הצמתים מופיעות על האלכסון) למטריצת השכנויות של $G$. הערכים העצמיים של מטריצה זו $\lambda _{0}\leq \lambda _{1}\leq \cdots \leq \lambda _{n-1}$ מקיימים: $\displaystyle \lambda _{0}=0$ (הווקטור העצמי המתאים לו הוא $[1,1,\dots ,1]$) ולכל $\displaystyle i$, $\lambda _{i}\geq 0$. מספר הפעמים שהערך 0 מופיע כערך עצמי הוא כמספר רכיבי הקשירות של $G$, ולכן אם הגרף קשיר אז $\displaystyle \lambda _{1},\lambda _{2},...,\lambda _{n-1}$ חיוביים ממש.

המשפט

יהא $G$ גרף קשיר בעל $n$ קודקודים, ויהיו $\displaystyle \lambda _{1},\lambda _{2},...,\lambda _{n-1}$ ערכים עצמיים שונים מאפס של הלאפלסיאן $L$ של $G$. אזי $\displaystyle t(G)$, מספר העצים הפורשים של $G$, הוא:

$t(G)={\frac {1}{n}}\lambda _{1}\lambda _{2}\cdots \lambda _{n-1}\,.$

במילים אחרות, מספר העצים הפורשים שווה למינור של $L$.

נוסחת קיילי ומשפט קירכהוף

נוסחת קיילי נגזרת ממשפט קירכהוף כמקרה פרטי, על ידי חישוב הערכים העצמיים של הלפלסיאן של גרף שלם בעל $n$ צמתים: כל וקטור בעל הערך 1 באיבר אחד, 1- באיבר אחר ו-0 בכל מקום אחר בווקטור העצמי של הלפלסיאן של הגרף השלם, כאשר הערך העצמי המתאים לו הוא $\displaystyle n$. הווקטורים הללו פורשים מרחב בעל ממד מסדר $n-1$ ולכן אין שום ערכים עצמיים נוספים השונים מ-0, כלומר $\displaystyle \lambda _{1}=\lambda _{2}=...,=\lambda _{n-1}=n$.

קישורים חיצוניים

• גדי אלכסנדרוביץ', משפט המטריצה-עץ של קירכהוף, באתר "לא מדויק", 13 בספטמבר 2011