משפט קירכהוף – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
|||
שורה 2:
בתחום ה[[מתמטיקה|מתמטי]] של [[תורת הגרפים]] '''משפט קירכהוף''' או '''משפט מטריצת העץ של קירכהוף''', הנקרא על שם הפיזיקאי הגרמני [[גוסטב קירכהוף]], מאפיין את מספר [[עץ פורש|העצים הפורשים]] [[גרף (תורת הגרפים)|בגרף]]. המשפט הינו [[הכללה (מתמטיקה)|הכללה]] ל[[נוסחת קיילי]] הקובעת כי מספר העצים הפורשים ב[[גרף שלם]] בעל n צמתים הוא <math>\ n^{n-2}</math>.
==הלפלאסיאן של גרף==
<math>\lambda_i \ge 0 </math>.
מספר הפעמים שהערך 0 מופיע כערך עצמי הוא כמספר [[גרף קשיר#רכיבי קשירות|רכיבי הקשירות]] של <math>G</math>, ולכן אם ה[[גרף קשיר]] אז <math>\displaystyle \lambda_1, \lambda_2,...,\lambda_{n-1}</math> חיוביים ממש.
==המשפט==
יהא <math>G</math> [[גרף קשיר]] בעל <math>n</math> [[קודקוד]]ים, ויהיו <math>\displaystyle \lambda_1, \lambda_2,...,\lambda_{n-1}</math> [[ערך עצמי|ערכים עצמיים]] שונים מ[[0 (מספר)|אפס]] של הלאפלסיאן <math>L </math> של <math>G</math>. אזי <math>\displaystyle t(G)</math>, מספר העצים הפורשים של של <math>G</math>, הוא:
:<math>t(G)=\frac{1}{n}\lambda_1\lambda_2\cdots\lambda_{n-1}\,.</math>
במילים אחרות, מספר העצים הפורשים שווה ל[[מינור (אלגברה)|מינור]]
==הערות==
| |||