שינויים

קפיצה אל: ניווט, חיפוש

תקציר תורת הגרפים, סמסטר א תשע״ג

אין שינוי בגודל, 20:09, 12 בפברואר 2013
/* תורת הגרפים האלגברית */
* '''מטריצת השכנות''' של גרף סופי <math>G</math> (מכוון או לא) כך ש־<math>V=\{v_i\}_{i=1}^n</math> היא <math>A_G\in\mathbb N_0^{n\times n}</math> שבה <math>a_{ij}</math> הוא מספר הצלעות מ־<math>v_i</math> ל־<math>v_j</math>.
* נסמן <math>\operatorname{spec}(A_G)=\operatorname{spec}(G)</math> כרב־קבוצה של הע״ע של <math>A_G</math> (כאשר כל ע״ע מופיע בריבוי השווה לריבוי האלגברי שלו).
* '''מטריצת הדרגות''' של גרף <math>G</math> מסדר <math>n</math> שקודקודיו <math>V(G)=\{v_i\}_{i=1}^n</math> הוא היא המטריצה <math>D_G:=\Big(\delta_{ij}d_G(v_i)\Big)_{i,j=1}^n</math>.
* '''הלפלסיאן''' של <math>G</math> הוא <math>L_G:=D_G-A_G</math>.