משפט קירכהוף

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

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

הלפלסיאן של גרף[עריכת קוד מקור | עריכה]

עבור גרף G בעל n קודקודים הלפלסיאן L של G הוא המטריצה L המתקבלת מההפרש בין מטריצת הדרגות (מטריצה אלכסונית בה דרגות הצמתים מופיעות על האלכסון) למטריצת השכנויות של G. הערכים העצמיים של מטריצה זו \lambda_0 \le \lambda_1 \le \cdots \le \lambda_{n-1} מקיימים: \displaystyle \lambda_0 = 0 (הווקטור העצמי המתאים לו הוא [1,1,\dots,1]) ולכל \displaystyle i, \lambda_i \ge 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.

קישורים חיצוניים[עריכת קוד מקור | עריכה]