שינויים
* '''הילוך''' בגרף הוא סדרת קודקודים (חזרות מותרות) כך שכל קודקוד שכן של הסמוכים לו. כלומר, זו סדרה <math>v_0,v_1,\dots,v_n</math> כך ש־<math>\forall i:\ (v_i,v_{i+1})\in E</math>.
** אורך ההילוך הוא <math>n</math> – מספר הצלעות שבו, כלומר מספר הקודקודים פחות 1.
*** '''המרחב בין שני קודקודים''' <math>u,v</math> הוא המרחק המינימלי של הילוך בינהם (אם יש כזה) ומסומן <math>\mboxoperatorname{dist}_G(u,v)</math>.**** '''הקוטר''' של גרף הוא <math>\mboxoperatorname{diameter}(G)=\max\{\mboxoperatorname{dist}_G(u,v):\ u,v\in V(G)\}</math>.
** ההילוך '''סגור''' אם <math>v_0=v_n</math>.
* '''מסלול''' הוא הילוך שבו אין צלעות חוזרות.
** מספר רכיבי הקשירות: <math>K(G)=K(H)</math>.
** וקטור דרגות (וקטור דרגות של גרף הוא וקטור שרכיביו הם דרגות הקודקודים מסודרות בסדר יורד חלש).
** קוטר: <math>\mboxoperatorname{diameter}(G)=\mboxoperatorname{diameter}(H)</math>.
* '''גרף מסומן''' הוא גרף שקודקודיו סומנו ע״י <math>\{v_i\}_{i=1}^n</math>. שני גרפים מסומנים הם זהים אם״ם קיים איזומורפיזם <math>\varphi</math> בינהם כך ש־<math>\forall i:\ \varphi(v_i)=v_i</math>.
** '''משפט קיילי:''' יש <math>n^{n-2}</math> עצים מסומנים מסדר <math>n</math>.
=== בעיות קיצון ===
==== בעיית טורן ====
* '''בעיית טורן:''' בהנתן גרף <math>H</math> (או קבוצת גרפים <math>\mathbb H</math>) ומספר טבעי <math>n</math> יש למצוא את המידה המקסימלית האפשרית בגרף פשוט מסדר <math>n</math> שאין לו תת־גרף איזומורפי ל־<math>H</math> (או לאחד מהגרפים ב־<math>\mathbb H</math>). מספר זה מסומן כ־<math>\mboxoperatorname{ex}(n,H)</math> או <math>\mboxoperatorname{ex}(n,\mathbb H)</math> וגרף כזה נקרא ''גרף מרבי נמנע <math>H</math> (או <math>\mathbb H</math>)''.
* '''משפט טורן:''' הגרף המרבי נמנע <math>K_r</math> היחיד מסדר <math>n</math> הוא <math>T(n,r-1)</math>.
** אם <math>r\mid n</math> אז <math>T(n,r)</math> הוא <math>\left(n-\frac nr\right)</math>־רגולרי ו־<math>\mboxoperatorname{ex}(n,K_{n+1})=\frac{n^2}2\left(1-\frac1r\right)</math>.
==== תורת רמזי ====
* '''מספר רמזי''' <math>R(s,t)</math> הוא הסדר המינימלי כך שאם <math>G</math> גרף מסדר זה אז <math>K_s</math> תת־גרף של <math>G</math> או ש־<math>K_t</math> תת־גרף של <math>\overline G</math>.
* אם <math>G</math> לא מכוון אז <math>A_G</math> סימטרית.
* לכל גרף סופי מתקיים <math>\sum_{i=1}^n a_{ij}=d_G^-(v_j)\ \and\ \sum_{j=1}^n a_{ij}=d_G^+(v_i)</math>.
* העקבה <math>\mboxoperatorname{tr}(A_G)</math> היא מספר הלולאות ב־<math>G</math>.* יהי <math>G</math> פשוט ולא מכוון. אזי <math>\mboxoperatorname{tr}\!\left(A_G^2\right)=\frac122|E(G)|</math>.
* יהי <math>G</math> לא מכוון. אזי <math>|E(G)|=\sum_{i\le j}a_{ij}</math>.
* מספר ההילוכים מ־<math>v_i</math> ל־<math>v_j</math> מאורך <math>t</math> הוא <math>(A_G^t)_{i,j}</math>.
** מספר ההילוכים הסגורים מאורך <math>t</math> ב־<math>G</math> הוא <math>\mboxoperatorname{tr}\!\left(A_G^t\right)</math> (כאשר שני הילוכים שמתחילים בנקודות שונות הם שונים גם אם הם עוברים על אותן נקודות).* נסמן <math>\operatorname{spec}(A_G)=\operatorname{spec}(G)</math> כרב־קבוצה של הע״ע של <math>A_G</math> (כאשר כל ע״ע מופיע בריבוי השווה לריבוי האלגברי שלו).* אם <math>G,H</math> סופיים ולא מכוונים אז <math>\operatorname{spek}(G\times H)=\operatorname{spec}(G)+\operatorname{spec}(H)</math>.* אם <math>G</math> גרף <math>d</math>־רגולרי אז <math>d\in\operatorname{spec}(G)</math> וו״ע מתאימים הם <math>v_A=(I_A(i))_{i=1}^{|V(G)|}</math> לכל רכיב קשירות <math>A\subseteq V(G)</math>.* יהא <math>G</math> סופי ולא מכוון. <math>G</math> דו־צדדי אם״ם מתקיים התנאי הבא: <math>\lambda</math> ע״ע של <math>A_G</math> מריבוי אלגברי <math>k</math> אם״ם <math>-\lambda</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>.* הלפלסיאנים של שני גרפים זהים אם״ם יש להם תתי־גרפים פורשים איזומורפיים.* הלפלסיאן של גרף לא מכוון היא מטריצה סימטרית.* הלפלסיאן אינו מטריצה הפיכה.* אם <math>G</math> לא מכוון סופי אז <math>\operatorname{rank}(L_G)=|V(G)|-K(G)</math>.
=== הילוכים אקראיים ===
* '''הסתברות החזרה הממוצעת''' בזמן <math>t</math> היא <math>P_G(t):=\frac1{|V(G)|}\sum_{v\in V(G)}P_G(v,t)</math>.
* בגרף טרנזיטיבי קודקודים <math>\forall v\in V(G):\ P_G(v,t)=P_G(t)</math>.
* יהא <math>G</math> לא מכוון, סופי ו־<math>d</math>־רגולרי מסדר <math>n</math>. נסמן <math>\mbox{spec}(A_G)</math> כרב־קבוצה של הע״ע (כאשר כל ע״ע מופיע בריבוי השווה לריבוי האלגברי שלו). הע״ע ממשיים ולכן ניתן לסדר אותם בסדר יורד חלש <math>\lambda_0\ge\lambda_1\ge\dots\ge\lambda_{n-1}</math>. אזי <math>\forall t\in\mathbb N_0:\ P_G(t)=\sum_{i=0\lambda\in\operatorname{spec}(A_G)}\frac{\lambda^t}{n-1d^tn}=\frac{\lambda_ioperatorname{tr}\!\left(A_G^t\right)}{d^tn}</math>. === עצים פורשים ===*'''עץ פורש''' הוא תת־גרף פורש מסוג עץ.* מספר העצים הפורשים של גרף של <math>K_n</math> הוא <math>n^{n-2}</math>.* '''משפט מטריצה–עץ:''' כידוע, מינור <math>A[i,j]</math> של מטריצה <math>A</math> הוא המטריצה המתקבלת מהשמטת השורה ה־<math>i</math> והעמודה ה־<math>j</math>. נסמן <math>\hat A</math> כמינור המוחק את השורה והעמודה האחרונות. עתה יהי <math>G</math> גרף לא מכוון וסופי מסדר הגדול מ־1. מספר העצים הפורשים שלו שווה ל־<math>\det\!\left(\hat L_G\right)</math>.
