תקציר תורת הגרפים, סמסטר א תשע״ג: הבדלים בין גרסאות בדף

גרסה מ־20:04, 12 בפברואר 2013

בתקציר זה, אלא אם צוין אחרת, נסמן [math]\displaystyle{ [n]:=\{1,2,\dots,n\} }[/math]. [math]\displaystyle{ G,H }[/math] גרפים. [math]\displaystyle{ (\cdot,\cdot) }[/math] הוא זוג לא סדור (אלא אם מדובר בגרפים לא מכוונים) ומכפלה קרטזית [math]\displaystyle{ A\times B }[/math] של קבוצות היא קבוצת הזוגות הלא סדורים של איברי [math]\displaystyle{ A,B }[/math].

הגדרות

גרף הוא זוג [math]\displaystyle{ G=(V,E) }[/math] כך ש־[math]\displaystyle{ V }[/math] קבוצת קודקודים (נקראים גם "צמתים") ו־[math]\displaystyle{ E }[/math] רב קבוצה של זוגות לא סדורים של קודקודים (הזוגות נקראים "צלעות" או "קשתות").
לולאה היא צלע [math]\displaystyle{ (v,v) }[/math] כאשר [math]\displaystyle{ v\in V }[/math].
גרף פשוט הוא גרף ללא לולאות וללא ריבוי צלעות (כלומר, אף צלע לא מופיע פעמיים ב־[math]\displaystyle{ E }[/math]).
גרף מכוון הוא גרף בו הצלעות הן זוגות סדורים.
- אי־הכוונה של גרף מכוון היא הפיכתו לגרף לא מכוון ע״י הפיכת צלעותיו לזוגות לא סדורים.
- הכוונה של גרף לא מכוון היא הפיכתו לגרף מכוון. תיתכן יותר מהכוונה אפשרית אחת.
  - הכוונה מעגלית היא הכוונה שבה יש מעגל מכוון.
גרף סופי הוא גרף בו [math]\displaystyle{ |V|,|E|\lt \infty }[/math].
סדר של גרף הוא מספר הקודקודים בו, כלומר [math]\displaystyle{ |V| }[/math]. לעתים מסומן [math]\displaystyle{ n(G) }[/math].
מידה של גרף היא מספר הצלעות – [math]\displaystyle{ |E| }[/math]. לעתים מסומנת [math]\displaystyle{ e(G) }[/math] או [math]\displaystyle{ m(G) }[/math].
דרגה של קודקוד [math]\displaystyle{ v\in V }[/math] היא מספר הצלעות העוברות בו. מסומנת [math]\displaystyle{ d(v) }[/math] או [math]\displaystyle{ d_G(v) }[/math].
- הדרגה המקסימלית: [math]\displaystyle{ \Delta(G):=\max\{d_G(v):\ v\in V(G)\} }[/math].
- הדרגה המינימלית: [math]\displaystyle{ \delta(G):=\min\{d_G(v):\ v\in V(G)\} }[/math].
- דרגות החוץ והפנים של קודקוד בגרף מכוון הן [math]\displaystyle{ d_G^+(v):=|\{(v,u)\in E:\ u\in V\}|,\ d_G^-(v):=|\{(u,v)\in E:\ u\in V\}| }[/math] בהתאמה, כלומר מספר הצלעות היוצאות ומספר הצלעות הנכנסות לקודקוד בהתאמה.
איחוד של גרפים פשוטים [math]\displaystyle{ G,H }[/math] הוא [math]\displaystyle{ G\cup H:=\Big(V(G)\cup V(H),E(G)\cup E(H)\Big) }[/math]. באותו אופן מוגדר איחוד זר.
קבוצת השכנים של קודקוד [math]\displaystyle{ v }[/math] בגרף [math]\displaystyle{ G }[/math] היא [math]\displaystyle{ N_G(v):=\{u:\ (v,u)\in E(G)\} }[/math]. אם [math]\displaystyle{ A\subseteq V(G) }[/math] אז [math]\displaystyle{ N_G(A):=\bigcup_{v\in A}N_G(v)=\{u:\ \exists v\in A:\ (u,v)\in E(G)\} }[/math].

סוגי גרפים נפוצים

גרף ריק [math]\displaystyle{ N_n }[/math] הוא הגרף שסדרו [math]\displaystyle{ n }[/math] ומידתו 0.
גרף מלא/שלם [math]\displaystyle{ K_n }[/math] הוא הגרף שסדרו [math]\displaystyle{ n }[/math] ובין כל שני קודקודים יש צלע אחת בדיוק.

-** קליקה בגרף היא תת־גרף מלא. -** מספר הקליקה של גרף [math]\displaystyle{ G }[/math] מסומן [math]\displaystyle{ \omega(G) }[/math] ושווה לסדר המקסימלי של קליקה ב־[math]\displaystyle{ G }[/math].

מסילה [math]\displaystyle{ P_n }[/math] היא הגרף שסדרו [math]\displaystyle{ n }[/math] ושניתן לסדר את קודקודיו כ־[math]\displaystyle{ v_1,\dots,v_n }[/math] ואז [math]\displaystyle{ E=\{(v_i,v_{i+1}):\ 1\le i\lt n\} }[/math].
מעגל [math]\displaystyle{ C_n }[/math] ([math]\displaystyle{ n\ge3 }[/math]) הוא הגרף שסדרו [math]\displaystyle{ n }[/math] ושניתן לסדר את קודקודיו כ־[math]\displaystyle{ v_1,\dots,v_n }[/math] ואז [math]\displaystyle{ E=\{(v_i,v_{i+1}):\ 1\le i\lt n\}\cup\{(v_n,v_1)\} }[/math].

-** מותן (girth) של גרף [math]\displaystyle{ G }[/math] הוא אורך המעגל הקטן ביותר בגרף, ומסומן [math]\displaystyle{ g(G) }[/math]. אם אין בגרף מעגלים (יער) אז [math]\displaystyle{ g(G)=\infty }[/math].

גרף d־רגולרי הוא גרף שבו דרגת כל קודקוד היא [math]\displaystyle{ d }[/math].
- גרף d⁺־רגולרי הוא גרף מכוון שבו הדרגה היוצאת של כל קודקוד היא [math]\displaystyle{ d }[/math]. באותו אופן מגדירים גרף [math]\displaystyle{ d^- }[/math]־רגולרי.
גרף דו־צדדי (דו״צ) הוא גרף פשוט [math]\displaystyle{ G }[/math] שבו קיימת חלוקה [math]\displaystyle{ V(G)=V^1\uplus V^2 }[/math] כך ש־[math]\displaystyle{ E(G)\subseteq V^1\times V^2 }[/math].
- גרף דו־צדדי מלא [math]\displaystyle{ K_{m,n} }[/math] הוא הגרף שקודקודיו הם [math]\displaystyle{ V^1\uplus V^2 }[/math] (כאשר [math]\displaystyle{ \left|V^1\right|=n,\left|U^2\right|=m }[/math]) וצלעותיו [math]\displaystyle{ V^1\times V^2 }[/math].
- גרף r־צדדי הוא גרף [math]\displaystyle{ G }[/math] בו יש חלוקה [math]\displaystyle{ V(G)=\biguplus_{i=1}^r V^i }[/math] ל־[math]\displaystyle{ r }[/math] תתי־קבוצות כך שלכל [math]\displaystyle{ i }[/math] הקודקודים ב־[math]\displaystyle{ V^i }[/math] אינם שכנים, כלומר [math]\displaystyle{ E(G)\subseteq\bigcup_{i\ne j}V^i\times V^j }[/math].
- גרף r־צדדי מלא הוא גרף [math]\displaystyle{ r }[/math]־צדדי [math]\displaystyle{ G }[/math] בו [math]\displaystyle{ E(G)=\bigcup_{i\ne j}V^i\times V^j }[/math], כלומר שני קודקודים הם שכנים אם״ם הם נמצאים בצדדים שונים.
- גרף r־צדדי סימטרי הוא גרף [math]\displaystyle{ r }[/math]־צדדי בו [math]\displaystyle{ \forall i\in[r]:\ \left|V^i\right|\in\left\{\left\lfloor\frac{|V(G)|}r\right\rfloor,\left\lceil\frac{|V(G)|}r\right\rceil\right\} }[/math].
- גרף טורן [math]\displaystyle{ T(n,r) }[/math] הוא הגרף ה־[math]\displaystyle{ r }[/math]־צדדי סימטרי מלא מסדר [math]\displaystyle{ n }[/math].
גרף מסומן הוא גרף שקודקודיו סומנו ע״י [math]\displaystyle{ \{v_i\}_{i=1}^n }[/math]. שני גרפים מסומנים הם זהים אם״ם קיים איזומורפיזם [math]\displaystyle{ \varphi }[/math] בינהם כך ש־[math]\displaystyle{ \forall i:\ \varphi(v_i)=v_i }[/math].

עצים

יער הוא גרף פשוט ללא מעגלים.
עץ הוא יער קשיר.
עלה הוא קודקוד בעץ שדרגתו 1.
עץ פורש הוא תת־גרף פורש קשיר ללא מעגלים.

הילוכים

הילוך בגרף הוא סדרת קודקודים (חזרות מותרות) כך שכל קודקוד שכן של הסמוכים לו. כלומר, זו סדרה [math]\displaystyle{ v_0,v_1,\dots,v_n }[/math] כך ש־[math]\displaystyle{ \forall i:\ (v_i,v_{i+1})\in E }[/math].
- אורך ההילוך הוא [math]\displaystyle{ n }[/math] – מספר הצלעות שבו, כלומר מספר הקודקודים פחות 1.
- ההילוך סגור אם [math]\displaystyle{ v_0=v_n }[/math].
המרחק בין שני קודקודים [math]\displaystyle{ u,v }[/math] הוא המרחק המינימלי של הילוך בינהם (אם יש כזה) ומסומן [math]\displaystyle{ \operatorname{dist}_G(u,v) }[/math].
הקוטר של גרף הוא [math]\displaystyle{ \operatorname{diameter}(G)=\max\{\operatorname{dist}_G(u,v):\ u,v\in V(G)\} }[/math].
מסלול הוא הילוך שבו אין צלעות חוזרות.
מסילה היא הילוך שבו אין קודקודים חוזרים, למעט אם הקודקוד הראשון שווה לקודקוד האחרון.
רכיב קשירות בגרף לא מכוון הוא מחלקת שקילות של יחס השקילות [math]\displaystyle{ \rightarrow }[/math] המקיים [math]\displaystyle{ u\rightarrow v }[/math] אם״ם יש מסילה בין [math]\displaystyle{ u,v }[/math].
מספר רכיבי הקשירות בגרף [math]\displaystyle{ G }[/math] יסומן [math]\displaystyle{ K(G) }[/math].
גרף קשיר הוא גרף שבו יש רכיב קשירות אחד.
מסלול אוילר בגרף ללא לולאות הוא מסלול המכיל את כל צלעות הגרף.
אוילריאן הוא גרף בו קיים מסלול אוילר סגור.
סמי־אוילריאן הוא גרף בו קיים מסלול אוילר.
מסילה המילטוניאנית בגרף היא מסילה המכילה את כל קודקודיו.
מעגל המילטוניאני הוא מסילה המילטוניאנית סגורה.
המילטוניאן הוא גרף בו קיים מעגל המילטוניאני.
הילוך אקראי: יהי [math]\displaystyle{ G }[/math] גרף לא מכוון וסופי. במצב ההתחלתי [math]\displaystyle{ p_0 }[/math] נמצאים על הקודקוד [math]\displaystyle{ v_0\in V(G) }[/math] בהסתברות 1, ובכל צעד פונים לשכן של הקודקוד הנוכחי כאשר לכל שכן הסתברות שווה. ההילוך שנוצר מקודקודים אלו נקרא הילוך אקראי.
הסתברות החזרה בזמן [math]\displaystyle{ t }[/math] היא ההסתברות שלאחר [math]\displaystyle{ t }[/math] צעדים נהיה על הקודקוד בו התחלנו, ומסומנת [math]\displaystyle{ P_G(v_0,t) }[/math] כאשר [math]\displaystyle{ v_0 }[/math] הקודקוד ההתחלתי.
הסתברות החזרה הממוצעת בזמן [math]\displaystyle{ t }[/math] היא [math]\displaystyle{ P_G(t):=\frac1{|V(G)|}\sum_{v\in V(G)}P_G(v,t) }[/math].

איזומורפיזם

איזומורפיזם בין מגרף [math]\displaystyle{ G }[/math] לגרף [math]\displaystyle{ H }[/math] הוא פונקציה [math]\displaystyle{ \varphi:V(G)\to V(H) }[/math] חח״ע ועל ששומרת צלעות, כלומר [math]\displaystyle{ (u,v)\in E(G)\iff(\varphi(u),\varphi(v))\in E(H) }[/math] לכל [math]\displaystyle{ u,v\in V(G) }[/math]. אם קיים איזומורפיזם בין [math]\displaystyle{ G,H }[/math] אז נאמר שהם איזומורפיים ונסמן [math]\displaystyle{ G\cong H }[/math] (זה יחס שקילות).
גרף טרנזיטיבי קודקודים הוא גרף [math]\displaystyle{ G }[/math] בו לכל [math]\displaystyle{ u,v\in V(G) }[/math] קיים אוטומורפיזם [math]\displaystyle{ \varphi:V(G)\to V(G) }[/math] כך ש־[math]\displaystyle{ \varphi(u)=v }[/math].

גרפים הנוצרים מגרפים אחרים

תת־גרף

השמטת צלע [math]\displaystyle{ e\in E }[/math] מגרף [math]\displaystyle{ G }[/math] היא הפיכת הגרף ל־[math]\displaystyle{ G\setminus\{e\}:=(V,E\setminus\{e\}) }[/math].
השמטת קודקוד [math]\displaystyle{ v\in V }[/math] מגרף [math]\displaystyle{ G }[/math] היא הפיכת הגרף ל־[math]\displaystyle{ G\setminus\{v\}:=(V\setminus\{v\},E\setminus\{(v,u):\ u\in V\}) }[/math].
תת־גרף הוא הגרף המתקבל מסדרה של השמטות קודקודים ו/או צלעות.
תת־גרף פורש הוא תת־גרף המתקבל מסדרה של השמטות צלעות בלבד.
תת־גרף מושרה הוא תת־גרף המתקבל מסדרה של השמטות קודקודים בלבד.

חלוקה

חלוקה אלמנטרית של צלע [math]\displaystyle{ e=(u,v) }[/math] בגרף [math]\displaystyle{ G }[/math] היא [math]\displaystyle{ G\setminus\{e\}\cup\Big(\{e\},\{(u,e),(v,e)\}\Big) }[/math].
חלוקה של גרף היא היא גרף המתקבל מסדרה של חלוקות אלמנטריות.

כיווץ

כיווץ של גרף [math]\displaystyle{ G }[/math] בצלע [math]\displaystyle{ e=(u,v) }[/math] הוא [math]\displaystyle{ G/e:=G\setminus\{u,v\}\cup\Big(\{e\},\{e\}\times(N_G(u)\cup N_G(v))\Big) }[/math].
מינור של גרף פשוט הוא גרף המתקבל ממנו ע״י סדרה של השמטות קודקודים, השמטות צלעות וכיווצי צלעות.
תכונה מונוטונית של גרף היא תכונה הסגורה תחת מינור, כלומר אם גרף מקיים אותה אז כל מינור שלו מקיים אותה.

גרף משלים

הגרף המשלים של גרף [math]\displaystyle{ G=(V,E) }[/math] הוא [math]\displaystyle{ \overline G:=(V,V^2\setminus E) }[/math].

גרף הקו

גרף הקו של גרף פשוט [math]\displaystyle{ G }[/math] מסומן [math]\displaystyle{ L(G) }[/math] ומוגדר כגרף שקודקודיו הם [math]\displaystyle{ E(G) }[/math] וצלעותיו הם זוגות של צלעות שיש להן קודקוד משותף ב־[math]\displaystyle{ G }[/math], כלומר [math]\displaystyle{ E(L(G)):=\Big\{\Big((u_1,v),(u_2,v)\Big):\ (u_1,v),(u_2,v)\in E(G)\Big\} }[/math].

מכפלה קרטזית של גרפים

המכפלה הקרטזית של הגרפים [math]\displaystyle{ G,H }[/math] היא גרף המסומן כ־[math]\displaystyle{ G\times H }[/math]. קודקודיו הם [math]\displaystyle{ V(G)\times V(H) }[/math] וצלעותיו [math]\displaystyle{ \Big\{\Big((u_1,v),(u_2,v)\Big):\ \forall \{F_1,F_2\}=\{G,H\}:\ v\in V(F_1)\ \and\ (u_1,u_2)\in E(F_2)\Big\} }[/math].
קובייה n־מימדית היא [math]\displaystyle{ K_2^{\times n}:=\prod_{i=1}^n K_2 }[/math].

שיכון

שיכון של גרף [math]\displaystyle{ G }[/math] ב־[math]\displaystyle{ \mathbb R^n }[/math] הוא העתקה חח״ע [math]\displaystyle{ \varphi:V(G)\to\mathbb R^n }[/math]. כל צלע [math]\displaystyle{ (u,v)\in E(G) }[/math] מועתקת למסילה רציפה ופשוטה (כלומר, שאינה חותכת את עצמה) מ־[math]\displaystyle{ \varphi(u) }[/math] ל־[math]\displaystyle{ \varphi(v) }[/math].
שיכון נאות הוא שיכון אם אין חיתוך צלעות לא טריוויאלי, כלומר התמונות של הצלעות ב־[math]\displaystyle{ \mathbb R^n }[/math] חותכות זו את זו רק בתמונות של קודקודי הגרף.
גרף מישורי הוא גרף שניתן לשיכון נאות ב־[math]\displaystyle{ \mathbb R^2 }[/math].
פאה של שיכון נאות ב־[math]\displaystyle{ \mathbb R^2 }[/math] היא רכיב קשירות ב־[math]\displaystyle{ \mathbb R^2 }[/math] לאחר שהוציאו ממנו את התמונה של השיכון.
גרף חוץ־מישורי הוא גרף שניתן לשכן באופן נאות במישור כך שקודקודיו על מעגל וצלעותיו קטעים ישרים.

גופים אפלטוניים

טטרהדרון
הקסהדרון
אוקטהדרון
דודקהדרון
איקוסהדרון

גוף אפלטוני הוא פאון תלת־מימדי שכל פאותיו מצולעים משוכללים חופפים. הגופים האפלטונים הם הטטרהדרון ([math]\displaystyle{ K_4 }[/math]), ההקסהדרון (קובייה, [math]\displaystyle{ K_2^{\times3} }[/math]), האוקטהדרון ([math]\displaystyle{ K_{2,4} }[/math]), הדודקהדרון והאיקוסהדרון.
פאון דואלי של גוף אפלטוני הוא הפאון המתקבל לאחר שלכל פאה בגוף האפלטוני שמים קודקוד במרכז ומחברים צלעות בין קודקודים של פאות להן צלע משותפת.

צביעה

k־צביעת קודקודים או k־צביעה בגרף [math]\displaystyle{ G }[/math] ללא לולאות היא פונקציה [math]\displaystyle{ f:V(G)\to[k] }[/math].
k־צביעה כשרה היא [math]\displaystyle{ k }[/math]־צביעה [math]\displaystyle{ f }[/math] שבה לכל צלע [math]\displaystyle{ (u,v) }[/math] מתקיים [math]\displaystyle{ f(u)\ne f(v) }[/math]. כלומר, קודקודים שכנים צבועים בצבעים שונים.
מספר הצביעה או המספר הכרומטי של גרף [math]\displaystyle{ G }[/math] מסומן כ־[math]\displaystyle{ \chi(G) }[/math] ומוגדר כ־[math]\displaystyle{ k }[/math] המינימלי עבורו קיימת [math]\displaystyle{ k }[/math]־צביעה כשרה.
גרף k־צביע הוא גרף שקיימת לו [math]\displaystyle{ k }[/math]־צביעה כשרה, כלומר [math]\displaystyle{ \chi\le k }[/math].
פולינום הצביעה בגרף פשוט וסופי מסומן [math]\displaystyle{ f_G }[/math]. לכל [math]\displaystyle{ x }[/math] טבעי [math]\displaystyle{ f_G(x) }[/math] מוגדר כמספר ה־[math]\displaystyle{ x }[/math]־צביעות הכשרות. לשאר ה־[math]\displaystyle{ x }[/math]־ים [math]\displaystyle{ f_G(x) }[/math] הוא ההשלמה של [math]\displaystyle{ f_G }[/math] לפולינום.
k־צביעת צלעות בגרף [math]\displaystyle{ G }[/math] היא פונקציה [math]\displaystyle{ f:E(G)\to[k] }[/math].
k־צביעת צלעות כשרה היא [math]\displaystyle{ k }[/math]־צביעת צלעות בה אם לשתי צלעות יש קודקוד משותף אז הן צבועות בצבעים שונים.
אינדקס הצביעה [math]\displaystyle{ i(G) }[/math] של גרף [math]\displaystyle{ G }[/math] הוא ה־[math]\displaystyle{ k }[/math] המינימלי עבורו קיימת [math]\displaystyle{ k }[/math]־צביעת צלעות כשרה.

שידוך

שידוך בגרף [math]\displaystyle{ G }[/math] הוא התאמה חח״ע ועל [math]\displaystyle{ f:A\to B }[/math] כאשר [math]\displaystyle{ A\uplus B\subseteq V(G) }[/math] ו־[math]\displaystyle{ \forall u\in A:\ (u,f(u))\in E(G) }[/math].
שידוך מושלם [math]\displaystyle{ f:A\to B }[/math] הוא שידוך בו [math]\displaystyle{ A\uplus B=V(G) }[/math].
שידוך מלא מ־[math]\displaystyle{ V^1 }[/math] ל־[math]\displaystyle{ V^2 }[/math] בגרף [math]\displaystyle{ G }[/math] דו־צדדי ש־[math]\displaystyle{ V^1,V^2 }[/math] הם צדדיו הינו התאמה חח״ע (לאו דווקא על) [math]\displaystyle{ f:V^1\to V^2 }[/math] כך ש־[math]\displaystyle{ \forall u\in V^1:\ (u,f(u))\in E(G) }[/math].

אי־תלות

קבוצה בלתי־תלויה של צלעות בגרף [math]\displaystyle{ G }[/math] היא תת־קבוצה של [math]\displaystyle{ E(G) }[/math] שבה אין שתי צלעות בעלות קודקוד משותף.
קבוצה בלתי תלויה של קודקודים בגרף [math]\displaystyle{ G }[/math] היא תת־קבוצה של [math]\displaystyle{ V(G) }[/math] שמשרה גרף ריק, כלומר שבה אין שני קודקודים שכנים.
[math]\displaystyle{ \alpha(G) }[/math] הוא הגודל המקסימלי של קבוצה בלתי־תלויה של קודקודים ב־[math]\displaystyle{ G }[/math].

בעיות קיצון

בעיית טורן: בהנתן גרף [math]\displaystyle{ H }[/math] (או קבוצת גרפים [math]\displaystyle{ \mathbb H }[/math]) ומספר טבעי [math]\displaystyle{ n }[/math] יש למצוא את המידה המקסימלית האפשרית בגרף פשוט מסדר [math]\displaystyle{ n }[/math] שאין לו תת־גרף איזומורפי ל־[math]\displaystyle{ H }[/math] (או לאחד מהגרפים ב־[math]\displaystyle{ \mathbb H }[/math]). מספר זה מסומן כ־[math]\displaystyle{ \operatorname{ex}(n,H) }[/math] או [math]\displaystyle{ \operatorname{ex}(n,\mathbb H) }[/math] וגרף כזה נקרא גרף מרבי נמנע [math]\displaystyle{ H }[/math] (או [math]\displaystyle{ \mathbb H }[/math]).
מספר רמזי [math]\displaystyle{ R(s,t) }[/math] הוא הסדר המינימלי כך שאם [math]\displaystyle{ G }[/math] גרף מסדר זה אז [math]\displaystyle{ K_s }[/math] תת־גרף של [math]\displaystyle{ G }[/math] או ש־[math]\displaystyle{ K_t }[/math] תת־גרף של [math]\displaystyle{ \overline G }[/math].

תורת הגרפים האלגברית

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

משפטים

[math]\displaystyle{ \sum_{v\in V}d_G(v)=2|E(G)| }[/math].
[math]\displaystyle{ \sum_{v\in V}d_G^+(v)=\sum_{v\in V}d_G^-(v)=|E(G)| }[/math].
אם [math]\displaystyle{ \delta(G)\ge 2 }[/math] אז יש ב־[math]\displaystyle{ G }[/math] מעגל.
[math]\displaystyle{ g(G)\le2 }[/math] אם״ם הגרף לא פשוט.
גרף הוא ריק אם״ם הוא 0־רגולרי.
גרף 1־רגולרי ופשוט הוא איחוד זר של צלעות.
גרף 2־רגולרי ופשוט הוא איחוד זר של מעגלים.
אם גרף סופי ופשוט הוא [math]\displaystyle{ d }[/math]־רגולרי כך ש־[math]\displaystyle{ d }[/math] אי־זוגי אזי הגרף מסדר זוגי.
גרף פשוט הוא עץ אם״ם בין כל שני קודקודים יש מסילה יחידה.
בכל עץ סופי מסדר גדול מ־1 יש עלה.
גרף הוא עץ אם״ם הוא קשיר מינימלי, כלומר הוא קשיר וכל השמטת צלע יוצרת תת־גרף לא קשיר.
גרף הוא עץ אם״ם הוא מקסימלי ללא מעגלים, כלומר הוא עץ וכל הוספת צלע יוצרת מעגל.
לכל גרף קשיר וסופי קיים עץ פורש.
מספר העצים הפורשים של גרף של [math]\displaystyle{ K_n }[/math] הוא [math]\displaystyle{ n^{n-2} }[/math].
משפט מטריצה–עץ/משפט עצים פורשים: כידוע, מינור [math]\displaystyle{ A[i,j] }[/math] של מטריצה [math]\displaystyle{ A }[/math] הוא המטריצה המתקבלת מהשמטת השורה ה־[math]\displaystyle{ i }[/math] והעמודה ה־[math]\displaystyle{ j }[/math]. נסמן [math]\displaystyle{ \hat A }[/math] כמינור המוחק את השורה והעמודה האחרונות. עתה יהי [math]\displaystyle{ G }[/math] גרף לא מכוון וסופי מסדר הגדול מ־1. מספר העצים הפורשים שלו שווה ל־[math]\displaystyle{ \det\!\left(\hat L_G\right) }[/math].
בעיית הסוכן הנוסע: נתו גרף קשיר וסופי ורוצים למצוא את ההילוך הקצר ביותר העובר דרך כל קודקודי הגרף. הפתרון הכי יעיל לא ידוע, אבל יש פתרון הנותן הילוך שאורכו לכל היותר פי 2 מהפתרון המינימלי: מוצאים עץ פורש לגרף ומבצעים עליו חיפוש DFS.
ביער מסדר [math]\displaystyle{ n\in\mathbb N }[/math] עם [math]\displaystyle{ k }[/math] רכיבי קשירות יש [math]\displaystyle{ n-k }[/math] צלעות.
גרף הוא יער אם״ם אין לו מינור שאיזומורפי ל־[math]\displaystyle{ K_3 }[/math].
כל מסילה היא מסלול.
קיים הילוך בין שני קודקודים אם״ם קיימת מסילה בינהם.
גרף הוא קשיר אם״ם הוא אינו איחוד זר של שני גרפים.
משפט אוילר: גרף קשיר וסופי ללא לולאות הוא אוילריאן אם״ם דרגות כל הקודקודים זוגיות.
גרף [math]\displaystyle{ G }[/math] קשיר וסופי ללא לולאות הוא סמי־אוילריאן שאינו אוילריאן אם״ם דרגות כל הקודקודים זוגיות פרט לשני קודקודים.
משפט דיראק: יהי [math]\displaystyle{ G }[/math] גרף פשוט מסדר [math]\displaystyle{ n }[/math]. אם [math]\displaystyle{ \delta(G)\ge\frac n2 }[/math] אז [math]\displaystyle{ G }[/math] המילטוניאן.
אם [math]\displaystyle{ G\cong H }[/math] אז הפרמטרים הבאים שווים:
- סדר: [math]\displaystyle{ |V(G)|=|V(H)| }[/math].
- מידה: [math]\displaystyle{ |E(G)|=|E(H)| }[/math].
- מספר רכיבי הקשירות: [math]\displaystyle{ K(G)=K(H) }[/math].
- וקטור דרגות (וקטור דרגות של גרף הוא וקטור שרכיביו הם דרגות הקודקודים מסודרות בסדר יורד חלש).
- קוטר: [math]\displaystyle{ \operatorname{diameter}(G)=\operatorname{diameter}(H) }[/math].
משפט קיילי: יש [math]\displaystyle{ n^{n-2} }[/math] עצים מסומנים מסדר [math]\displaystyle{ n }[/math].
[math]\displaystyle{ G\cong H }[/math] אם״ם [math]\displaystyle{ \overline G\cong\overline H }[/math].
[math]\displaystyle{ L(P_n)\cong P_{n-1},L(C_n)\cong C_n }[/math].
הקובייה ה־[math]\displaystyle{ n }[/math] מימדית [math]\displaystyle{ K_2^{\times n} }[/math] איזומורפית ל־[math]\displaystyle{ B_n:=(\mathcal P([n]),\{(I,J):\ I\subset J\subseteq[n]\ \and\ |I|=|J|-1\}) }[/math] ול־[math]\displaystyle{ H_n:=(\mathbb Z_2^n,\{(u,v):\ u,v\in\mathbb Z_2^n\ \and\ |u-v|=1\}) }[/math].
לכל גרף עם מספר בן מנייה של קודקודים קיים שיכון נאות ב־[math]\displaystyle{ \mathbb R^3 }[/math] כך שהתמונות של הצלעות הן קטעים ישרים. אם הגרף הוא סופי ופשוט אז שיכון נאות מתאים הוא, לדוגמה, [math]\displaystyle{ \forall i:\ \varphi(v_i)=(i,i^2,i^3) }[/math] כאשר [math]\displaystyle{ V=\{v_i\}_{i=1}^n }[/math].
משפט הפאון של אוילר: לכל גרף מישורי סופי קשיר מסדר [math]\displaystyle{ n }[/math] וממידה [math]\displaystyle{ m }[/math] מספר הפאות [math]\displaystyle{ f }[/math] לא תלוי בשיכון הנאות ומקיים [math]\displaystyle{ n-m+f=2 }[/math].
יהי [math]\displaystyle{ G }[/math] גרף פשוט וקשיר מסדר [math]\displaystyle{ n\ge3 }[/math]. אם [math]\displaystyle{ G }[/math] מישורי אז [math]\displaystyle{ |E(G)|\le3n-6 }[/math].
יהי [math]\displaystyle{ G }[/math] פשוט וקשיר מסדר [math]\displaystyle{ n }[/math] ומותן [math]\displaystyle{ g\lt \infty }[/math]. אם [math]\displaystyle{ G }[/math] מישורי אז [math]\displaystyle{ |E(G)|\le g\frac{n-2}{g-2} }[/math].
לכל גרף מישורי פשוט סופי [math]\displaystyle{ G }[/math] מתקיים [math]\displaystyle{ \delta(G)\le5 }[/math].
משפט קורטובסקי: גרף אינו מישורי אם״ם יש לו תת־גרף שאיזומורפי לחלוקה של [math]\displaystyle{ K_5 }[/math] או של [math]\displaystyle{ K_{3,3} }[/math].
גרף הוא חוץ־מישורי אם״ם אין לו מינור שאיזומורפי ל־[math]\displaystyle{ K_4 }[/math] או ל־[math]\displaystyle{ K_{2,3} }[/math].
השערת וגנר: כל תכונה היא מונוטונית אם״ם היא מוגדרת ע״י קבוצה סופית של מינורים אסורים, כלומר קיים מספר סופי של גרפים שאיזומורפים למינור כלשהו של [math]\displaystyle{ G }[/math] אם״ם הוא אינו מקיים את התכונה.
משפט רוברטסון–סימור: השערת וגנר נכונה.
הגרף של כל גוף אפלטוני הוא מישורי.
לכל גרף [math]\displaystyle{ G }[/math] פשוט [math]\displaystyle{ 1\le\chi(G)\le|V(G)| }[/math]. [math]\displaystyle{ \chi(G)=1 }[/math] אם״ם [math]\displaystyle{ G }[/math] גרף ריק ו־[math]\displaystyle{ \chi(G)=|V(G)| }[/math] אם״ם הוא גרף מלא.
משפט ברוקס: לכל גרף [math]\displaystyle{ G }[/math] פשוט וסופי [math]\displaystyle{ \chi(G)\le\Delta(G)+1 }[/math] ושוויון מתקיים אם״ם [math]\displaystyle{ \omega(G)=\Delta(G)+1 }[/math] או אם [math]\displaystyle{ G }[/math] איחוד זר של מעגלים ומסילות ויש מעגל מסדר אי־זוגי.
יהא [math]\displaystyle{ G }[/math] פשוט וסופי. [math]\displaystyle{ \chi(G)\le2 }[/math] אם״ם אין ב־[math]\displaystyle{ G }[/math] מעגלים מאורך אי־זוגי.
גרף הוא 2־צביע אם״ם הוא דו־צדדי.
בעיית 4 הצבעים: לכל גרף מישורי סופי פשוט [math]\displaystyle{ G }[/math] הוא 4־צביע.
[math]\displaystyle{ f_{N_n}(x)=x^n\ \and\ f_{K_n}(x)=(x)_n=\begin{cases}\frac{x!}{(x-n)!},&x\ge n\\0,&\text{else}\end{cases}\ \and\ f_{P_n}(x)=x(x-1)^{n-1} }[/math].
[math]\displaystyle{ \forall x\in\mathbb N\ \and\ e\in E(G):\ f_G(x)=f_{G\setminus e}(x)-f_{G/e}(x) }[/math].
[math]\displaystyle{ f_G }[/math] פולינום מתוקן ודרגתו [math]\displaystyle{ |V(G)| }[/math].
[math]\displaystyle{ \chi(G)=\max\{x\in\mathbb N_0:\ f_G(x)=0\}+1 }[/math].
משפט סטנלי: מספר ההכוונות הלא מעגליות של [math]\displaystyle{ G }[/math] הוא [math]\displaystyle{ (-1)^n f_G(-1) }[/math].
לכל גרף [math]\displaystyle{ G }[/math] סופי [math]\displaystyle{ \Delta(G)\le i(G) }[/math]. אם הוא לא ריק אז [math]\displaystyle{ i(G)\le2\Delta(G)-1 }[/math].
אם [math]\displaystyle{ G }[/math] דו־צדדי ו־[math]\displaystyle{ d }[/math]־רגולרי אז [math]\displaystyle{ i(G)=d }[/math].
אם [math]\displaystyle{ f:A\to B }[/math] שידוך אז [math]\displaystyle{ \{(u,f(u)):\ u\in A\} }[/math] קבוצה בלתי־תלויה.
משפט הול (Hall): לכל גרף דו־צדדי שצדדיו [math]\displaystyle{ V^1,V^2 }[/math] קיים שידוך מלא מ־[math]\displaystyle{ V^1 }[/math] ל־[math]\displaystyle{ V^2 }[/math] אם״ם [math]\displaystyle{ \forall A\subseteq V^1:\ |N_G(A)|\ge|A| }[/math].
משפט טורן: הגרף המרבי נמנע [math]\displaystyle{ K_r }[/math] היחיד מסדר [math]\displaystyle{ n }[/math] הוא [math]\displaystyle{ T(n,r-1) }[/math].
אם [math]\displaystyle{ r\mid n }[/math] אז [math]\displaystyle{ T(n,r) }[/math] הוא [math]\displaystyle{ \left(n-\frac nr\right) }[/math]־רגולרי ו־[math]\displaystyle{ \operatorname{ex}(n,K_{n+1})=\frac{n^2}2\left(1-\frac1r\right) }[/math].
למת לחיצות הידיים: עבור כל גרף פשוט מסדר 6 או ש־[math]\displaystyle{ G }[/math] מכיל משולש או ש־[math]\displaystyle{ \overline G }[/math] מכיל משולש. (למעשה, [math]\displaystyle{ R(3,3)=6 }[/math].)
[math]\displaystyle{ R(1,t)=1\ \and\ R(2,t)=t\ \and\ R(s,t)=R(t,s) }[/math] ואם [math]\displaystyle{ t,s\ge3 }[/math] אז [math]\displaystyle{ R(s,t)\le R(s-1,t)+R(s,t-1) }[/math].
[math]\displaystyle{ R(s,t)\le\binom{s+t-2}{s-1} }[/math].
אם [math]\displaystyle{ G }[/math] לא מכוון אז [math]\displaystyle{ A_G }[/math] סימטרית.
לכל גרף סופי מתקיים [math]\displaystyle{ \sum_{i=1}^n a_{ij}=d_G^-(v_j)\ \and\ \sum_{j=1}^n a_{ij}=d_G^+(v_i) }[/math].
העקבה [math]\displaystyle{ \operatorname{tr}(A_G) }[/math] היא מספר הלולאות ב־[math]\displaystyle{ G }[/math].
יהי [math]\displaystyle{ G }[/math] פשוט ולא מכוון. אזי [math]\displaystyle{ \operatorname{tr}\!\left(A_G^2\right)=2|E(G)| }[/math].
יהי [math]\displaystyle{ G }[/math] לא מכוון. אזי [math]\displaystyle{ |E(G)|=\sum_{i\le j}a_{ij} }[/math].
מספר ההילוכים מ־[math]\displaystyle{ v_i }[/math] ל־[math]\displaystyle{ v_j }[/math] מאורך [math]\displaystyle{ t }[/math] הוא [math]\displaystyle{ (A_G^t)_{i,j} }[/math].
מספר ההילוכים הסגורים מאורך [math]\displaystyle{ t }[/math] ב־[math]\displaystyle{ G }[/math] הוא [math]\displaystyle{ \operatorname{tr}\!\left(A_G^t\right) }[/math] (כאשר שני הילוכים שמתחילים בנקודות שונות הם שונים גם אם הם עוברים על אותן נקודות).
אם [math]\displaystyle{ G,H }[/math] סופיים ולא מכוונים אז [math]\displaystyle{ \operatorname{spek}(G\times H)=\operatorname{spec}(G)+\operatorname{spec}(H) }[/math].
אם [math]\displaystyle{ G }[/math] גרף [math]\displaystyle{ d }[/math]־רגולרי אז [math]\displaystyle{ d\in\operatorname{spec}(G) }[/math] וו״ע מתאימים הם [math]\displaystyle{ v_A=(I_A(i))_{i=1}^{|V(G)|} }[/math] לכל רכיב קשירות [math]\displaystyle{ A\subseteq V(G) }[/math].
יהא [math]\displaystyle{ G }[/math] סופי ולא מכוון. [math]\displaystyle{ G }[/math] דו־צדדי אם״ם מתקיים התנאי הבא: [math]\displaystyle{ \lambda }[/math] ע״ע של [math]\displaystyle{ A_G }[/math] מריבוי אלגברי [math]\displaystyle{ k }[/math] אם״ם [math]\displaystyle{ -\lambda }[/math] ע״ע מאותו ריבוי.
הלפלסיאנים של שני גרפים זהים אם״ם יש להם תתי־גרפים פורשים איזומורפיים.
הלפלסיאן של גרף לא מכוון הוא מטריצה סימטרית.
הלפלסיאן אינו מטריצה הפיכה.
אם [math]\displaystyle{ G }[/math] לא מכוון סופי אז [math]\displaystyle{ \operatorname{rank}(L_G)=|V(G)|-K(G) }[/math].
בגרף טרנזיטיבי קודקודים [math]\displaystyle{ \forall v\in V(G):\ P_G(v,t)=P_G(t) }[/math].
יהא [math]\displaystyle{ G }[/math] לא מכוון, סופי ו־[math]\displaystyle{ d }[/math]־רגולרי מסדר [math]\displaystyle{ n }[/math]. אזי [math]\displaystyle{ \forall t\in\mathbb N_0:\ P_G(t)=\sum_{\lambda\in\operatorname{spec}(A_G)}\frac{\lambda^t}{d^tn}=\frac{\operatorname{tr}\!\left(A_G^t\right)}{d^tn} }[/math].