משפט קירכהוף

מתוך ויקיפדיה, האנציקלופדיה החופשית

ערך זה עוסק במשפט במתמטיקה; לערך העוסק בחוקים בתחום החשמל, ראו חוקי קירכהוף.

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

[עריכה] הגדרה

יהא גרף מקושר G בעל n קודקודים, נניח λ12,...,λn − 1 ערכים עצמיים שונים מאפס של מטריצת קירכהוף של G, אזי מספר העצים הפורשים של G הוא:

G=\frac{1}{n}\lambda_1\lambda_2\cdots\lambda_{n-1}\,.

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

[עריכה] הערות

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

שפות אחרות