שינויים
יסודר בהמשך
* '''דרגה''' של קודקוד <math>v\in V</math> היא מספר הצלעות העוברות בו. מסומנת <math>d(v)</math> או <math>d_G(v)</math>.
** מתקיים <math>\sum_{v\in V}d_G(v)=2|E|</math>.
** '''הדרגה המקסימלית:''' <math>\Delta(G):=\max\{d_G(v):\ v\in V(G)\}</math>.
** '''הדרגה המינימלית:''' <math>\delta(G):=\min\{d_G(v):\ v\in V(G)\}</math>.
* '''איחוד''' של גרפים פשוטים <math>G,H</math> הוא <math>G\cup H:=\Big(V(G)\cup V(H),E(G)\cup E(H)\Big)</math>. באותו אופן מוגדר איחוד זר.
* '''גרף ריק''' מסדר <math>n</math> מסומן <math>N_n</math> הוא הגרף שסדרו <math>n</math> ומידתו 0.
* '''גרף מלא/שלם''' מסדר <math>n</math> (<math>K_n</math>) הוא הגרף שסדרו <math>n</math> ובין כל שני קודקודים יש צלע אחת בדיוק.
* '''מסילה''' מסדר <math>n</math> (<math>P_n</math>) הוא הגרף שסדרו <math>n</math> ושניתן לסדר את קודקודיו כ־<math>v_1,\dots,v_n</math> ואז <math>E=\{(v_i,v_{i+1}):i\in[1,\le i<n-1]\cap\mathbb N\}</math>.* '''מעגל''' מסדר <math>n>2</math> (<math>C_n</math>) הוא הגרף שסדרו <math>n</math> ושניתן לסדר את קודקודיו כ־<math>v_1,\dots,v_n</math> ואז <math>E=\{(v_i,v_{i+1}):i\in[1,\le i<n-1]\cap\mathbb N\}\cup\{(v_n,v_1)\}</math>.
* '''גרף <math>d</math>־רגולרי''' הוא גרף שבו דרגת כל קודקוד היא <math>d</math>.
** גרף הוא ריק אם״ם הוא 0־רגולרי.
* '''יער''' הוא גרף פשוט ללא מעגלים.
** '''עץ''' הוא יער קשיר.
*** גרף פשוט הוא עץ אם״ם בין כל שני קודקודים יש מסילה יחידה.
*** '''עלה'' הוא קודקוד בעץ שדרגתו 1.
*** בכל עץ סופי מסדר גדול מ־1 יש עלה.
*** גרף הוא עץ אם״ם הוא קשיר מינימלי, כלומר הוא קשיר וכל השמטת צלע יוצרת תת־גרף לא קשיר.
*** גרף הוא עץ אם״ם הוא מקסימלי ללא מעגלים, כלומר הוא עץ וכל הוספת צלע יוצרת מעגל.
*** '''חיפוש DFS:''' נרצה ליצור הילוך שעובר על כל קודקודי העץ. מתחילים באחד מהעלים. בכל צעד אם אנו נמצאים על קודקוד שעל כל ילדיו כבר נערך חיפוש, נפנה להורה שלו. אחרת נפנה לאחד מילדיו.
*** '''עץ פורש''' הוא תת־גרף פורש קשיר ללא מעגלים.
**** לכל גרף קשיר וסופי קיים עץ פורש.
***** '''בעיית הסוכן הנוסע:''' נתו גרף קשיר וסופי ורוצים למצוא את ההילוך הקצר ביותר העובר דרך כל קודקודי הגרף. הפתרון הכי יעיל לא ידוע, אבל יש פתרון הנותן הילוך שאורכו לכל היותר פי 2 מהפתרון המינימלי: מוצאים עץ פורש לגרף ומבצעים עליו חיפוש DFS.
** ביער מסדר <math>n\in\mathbb N</math> עם <math>k</math> רכיבי קשירות יש <math>n-k</math> צלעות.
=== הילוכים ===
* '''הילוך''' בגרף הוא סדרת קודקודים (חזרות מותרות) כך שכל קודקוד שכן של הסמוכים לו. כלומר, זו סדרה <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>\mbox{dist}_G(u,v)</math>.
**** '''הקוטר''' של גרף הוא <math>\mbox{diameter}(G)=\max\{\mbox{dist}_G(u,v):\ u,v\in V(G)\}</math>.
** ההילוך '''סגור''' אם <math>v_0=v_n</math>.
* '''מסלול''' הוא הילוך שבו אין צלעות חוזרות.
* '''רכיב קשירות''' בגרף לא מכוון הוא מחלקת שקילות של יחס השקילות <math>\rightarrow</math> המקיים <math>u\rightarrow v</math> אם״ם יש מסילה בין <math>u,v</math>.
** מספר רכיבי הקשירות בגרף <math>G</math> יסומן <math>K(G)</math>.
** '''גרף קשיר''' הוא גרף שבו יש מחלקת שקילות אחתרכיב קשירות אחד.
*** גרף הוא קשיר אם״ם הוא אינו איחוד זר של שני גרפים.
** '''תת־גרף מושרה''' הוא תת־גרף המתקבל מסדרה של השמטות קודקודים בלבד.
*** אם <math>H</math> תת־גרף מושרה של <math>G</math> אזי <math>\forall u,v\in V(H):\ \Big((u,v)\in E(G)\iff(u,v)\in E(H)\Big)</math>. כלומר, כל שני קודקודים שכנים ב־<math>H</math> הם שכנים ב־<math>G</math>.
=== איזומורפיזם ===
* '''איזומורפיזם''' בין מגרף <math>G</math> לגרף <math>H</math> הוא פונקציה <math>\varphi:V(G)\to V(H)</math> חח״ע ועל ששומרת צלעות, כלומר <math>(u,v)\in E(G)\iff(\varphi(u),\varphi(v))\in E(H)</math> לכל <math>u,v\in V(G)</math>. אם קיים איזומורפיזם בין <math>G,H</math> אז נאמר שהם איזומורפיים ונסמן <math>G\cong H</math> (זה יחס שקילות).
* אם <math>G\cong H</math> אז הפרמטרים הבאים שווים:
** סדר: <math>|V(G)|=|V(H)|</math>.
** מידה: <math>|E(G)|=|E(H)|</math>.
** מספר רכיבי הקשירות: <math>K(G)=K(H)</math>.
** וקטורי הדרגות: אם נגדיר לשני הגרפים וקטורים הבנויים מדרגות הקודקודים מסודרים בסדר יורד חלש אז וקטורי הדרגות שווים.
** הקטרים: <math>\mbox{diameter}(G)=\mbox{diameter}(H)</math>.
=== גרף משלים ===
* '''הגרף המשלים''' של גרף <math>G=(V,E)</math> הוא <math>\overline G:=(V,V^2\setminus E)</math>.
* <math>G\cong H</math> אם״ם <math>\overline G\cong\overline H</math>.
