משפט קירכהוף – הבדלי גרסאות

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

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

[[נוסחת קיילי]] נגזרת ממשפט קירכהוף כ[[מקרה פרטי]], על ידי חישוב הערכים העצמיים של הלפלאסיאןהלפלסיאן של גרף שלם בעל <math>n</math> צמתים: כל [[וקטור (אלגברה)|וקטור]] בעל הערך 1 באיבר אחד, 1- באיבר אחר ו-0 בכל מקום אחר ב[[וקטור עצמי|ווקטור העצמי]] של הלפלאסיאןהלפלסיאן של הגרף השלם, כאשר [[ערך עצמי|הערך העצמי]] המתאים לו הוא <math>\displaystyle n</math>. הווקטורים הללו פורשים מרחב בעל [[ממד (אלגברה לינארית)|ממד]] מסדר <math>n-1</math> ולכן אין שום ערכים עצמיים נוספים השונים מ-0, כלומר <math>\displaystyle \lambda_1= \lambda_2=...,=\lambda_{n-1}=n</math>.