שינויים
המשך יבוא
* '''גרף פשוט''' הוא גרף ללא לולאות וללא ריבוי צלעות (כלומר, אף צלע לא מופיע פעמיים ב־<math>E</math>).
* '''גרף מכוון''' הוא גרף בו הצלעות הן זוגות סדורים.
** '''אי־הכוונה''' של גרף מכוון היא הפיכתו לגרף לא מכוון ע״י הפיכת צלעותיו לזוגות לא סדורים.
* '''גרף סופי''' הוא גרף בו <math>|V|,|E|<\infty</math>.
* '''סדר''' של גרף הוא מספר הקודקודים בו, כלומר <math>|V|</math>. לעתים מסומן <math>n(G)</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>d_G^+(v):=|\{(v,u)\in E:\ u\in V\}|,\ d_G^-(v):=|\{(u,v)\in E:\ u\in V\}|</math> בהתאמה, כלומר מספר הצלעות היוצאות ומספר הצלעות הנכנסות לקודקוד בהתאמה.
*** מתקיים <math>\sum_{v\in V}d_G^+(v)=\sum_{v\in V}d_G^-(v)=|E|</math>.
* '''איחוד''' של גרפים פשוטים <math>G,H</math> הוא <math>G\cup H:=\Big(V(G)\cup V(H),E(G)\cup E(H)\Big)</math>. באותו אופן מוגדר איחוד זר.
* קבוצת השכנים של קודקוד <math>v</math> בגרף <math>G</math> היא <math>N_G(v):=\{u:\ (v,u)\in E(G)\}</math>.
=== סוגים נפוצים ===
* '''גרף ריק''' מסדר <math>n</math> מסומן <math>N_n</math> הוא הגרף שסדרו <math>n</math> ומידתו 0.
* '''גרף מלא/שלם''' מסדר <math>n</math> (<math>K_n</math>) הוא הגרף שסדרו <math>n</math> ובין כל שני קודקודים יש צלע אחת בדיוק.
** <math>K_{m,n}</math> הוא הגרף שקודקודיו הם <math>V\uplus U</math> (כאשר <math>|V|=n,|U|=m</math>) וצלעותיו <math>\{(v,u):\ v\in V\ \and\ u\in U\}</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}):\ 1\le i<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}):\ 1\le i<n\}\cup\{(v_n,v_1)\}</math>.
** אם <math>\delta(G)\ge 2</math> אז יש ב־<math>G</math> מעגל.** '''מותן (girth)''' של גרף <math>dG</math>הוא אורך המעגל הקטן ביותר בגרף, ומסומן <math>g(G)</math>. אם אין בגרף מעגלים (יער) אז <math>g(G)=\infty</math>.*** <math>g(G)\le2</math> אם״ם הגרף לא פשוט.* '''גרף ''d''־רגולרי''' הוא גרף שבו דרגת כל קודקוד היא <math>d</math>.
** גרף הוא ריק אם״ם הוא 0־רגולרי.
** גרף 1־רגולרי ופשוט הוא איחוד זר של צלעות.
** גרף 2־רגולרי ופשוט הוא איחוד זר של מעגלים.
** אם גרף סופי ופשוט הוא <math>d</math>־רגולרי כך ש־<math>d</math> אי־זוגי אזי הגרף מסדר זוגי.
** '''גרף {{ltr|''d<sup>+</sup>''}}־רגולרי''' הוא גרף מכוון שבו הדרגה היוצאת של כל קודקוד היא <math>d</math>. באותו אופן מגדירים גרף <math>d^-</math>־רגולרי.
==== עצים ====
* '''יער''' הוא גרף פשוט ללא מעגלים.
** '''עץ''' הוא יער קשיר.
*** גרף פשוט הוא עץ אם״ם בין כל שני קודקודים יש מסילה יחידה.
*** '''עלה''' הוא קודקוד בעץ שדרגתו 1.
*** בכל עץ סופי מסדר גדול מ־1 יש עלה.
*** גרף הוא עץ אם״ם הוא קשיר מינימלי, כלומר הוא קשיר וכל השמטת צלע יוצרת תת־גרף לא קשיר.
***** '''בעיית הסוכן הנוסע:''' נתו גרף קשיר וסופי ורוצים למצוא את ההילוך הקצר ביותר העובר דרך כל קודקודי הגרף. הפתרון הכי יעיל לא ידוע, אבל יש פתרון הנותן הילוך שאורכו לכל היותר פי 2 מהפתרון המינימלי: מוצאים עץ פורש לגרף ומבצעים עליו חיפוש DFS.
** ביער מסדר <math>n\in\mathbb N</math> עם <math>k</math> רכיבי קשירות יש <math>n-k</math> צלעות.
** גרף הוא יער אם״ם אין לו מינור שאיזומורפי ל־<math>K_3</math>.
=== הילוכים ===
** '''גרף קשיר''' הוא גרף שבו יש רכיב קשירות אחד.
*** גרף הוא קשיר אם״ם הוא אינו איחוד זר של שני גרפים.
* '''מסלול אוילר''' בגרף ללא לולאות הוא מסלול המכיל את כל צלעות הגרף.
** '''אוילריאן''' הוא גרף בו קיים מסלול אוילר סגור.
** '''סמי־אוילריאן''' הוא גרף בו קיים מסלול אוילר.
** '''משפט אוילר:''' גרף קשיר וסופי ללא לולאות הוא אוילריאן אם״ם דרגות כל הקודקודים זוגיות.
*** גרף <math>G</math> קשיר וסופי ללא לולאות הוא סמי־אוילריאן שאינו אוילריאן אם״ם דרגות כל הקודקודים זוגיות פרט לשני קודקודים.
* '''מסילה המילטוניאנית''' בגרף היא מסילה המכילה את כל קודקודיו.
** '''מעגל המילטוניאני''' הוא מסילה המילטוניאנית סגורה.
*** '''המילטוניאן''' הוא גרף בו קיים מעגל המילטוניאני.
**** '''משפט דיראק:''' יהי <math>G</math> גרף פשוט מסדר <math>n</math>. אם <math>\delta(G)\ge\frac n2</math> אז <math>G</math> המילטוניאן.
=== תתי גרפים ===
** מידה: <math>|E(G)|=|E(H)|</math>.
** מספר רכיבי הקשירות: <math>K(G)=K(H)</math>.
** וקטורי הדרגות: אם נגדיר לשני הגרפים וקטורים הבנויים מדרגות וקטור דרגות (וקטור דרגות של גרף הוא וקטור שרכיביו הם דרגות הקודקודים מסודרים מסודרות בסדר יורד חלש אז וקטורי הדרגות שווים).** הקטריםקוטר: <math>\mbox{diameter}(G)=\mbox{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>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>.
=== גרף הקו ===
* '''גרף הקו''' של גרף פשוט <math>G</math> מסומן <math>L(G)</math> ומוגדר כגרף שקודקודיו הם <math>E(G)</math> וצלעותיו הם זוגות של צלעות שיש להן קודקוד משותף ב־<math>G</math>, כלומר <math>E(L(G)):=\Big\{\Big((u_1,v),(u_2,v)\Big):\ (u_1,v),(u_2,v)\in E(G)\Big\}</math>.
** <math>L(P_n)\cong P_{n-1}</math>, <math>L(C_n)\cong C_n</math>.
=== מכפלה קרטזית של גרפים ===
* '''המכפלה הקרטזית''' של הגרפים <math>G,H</math> היא גרף המסומן כ־<math>G\times H</math>. קודקודיו הם <math>V(G)\times V(H)</math> וצלעותיו <math>\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>K_2^{\times n}:=\prod_{i=1}^n K_2</math>. היא איזומורפית ל־<math>B_n:=(\mathcal P([n]),\{(I,J):\ I\subset J\subseteq[n]\ \and\ |I|=|J|-1\})</math> ול־<math>H_n:=(\mathbb Z_2^n,\{(u,v):\ u,v\in\mathbb Z_2^n\ \and\ |u-v|=1\})</math>.
=== שיכון ===
* '''שיכון''' של גרף <math>G</math> ב־<math>\mathbb R^n</math> הוא העתקה חח״ע <math>\varphi:V(G)\to\mathbb R^n</math>. כל צלע <math>(u,v)\in E(G)</math> מועתקת למסילה רציפה ופשוטה (כלומר, שאינה חותכת את עצמה) מ־<math>\varphi(u)</math> ל־<math>\varphi(v)</math>.
* '''שיכון נאות''' הוא שיכון אם אין חיתוך צלעות לא טריוויאלי, כלומר התמונות של הצלעות ב־<math>\mathbb R^n</math> חותכות זו את זו רק בתמונות של קודקודי הגרף.
* לכל גרף עם מספר בן מנייה של קודקודים קיים שיכון נאות ב־<math>\mathbb R^3</math> כך שהתמונות של הצלעות הן קטעים ישרים. אם הגרף הוא סופי ופשוט אז שיכון נאות מתאים הוא, לדוגמה, <math>\forall i:\ \varphi(v_i)=(i,i^2,i^3)</math> כאשר <math>V=\{v_i\}_{i=1}^n</math>.
* '''גרף מישורי''' הוא גרף שניתן לשיכון נאות ב־<math>\mathbb R^2</math>.
* '''פאה''' של שיכון נאות ב־<math>\mathbb R^2</math> היא רכיב קשירות ב־<math>\mathbb R^2</math> לאחר שהוציאו ממנו את התמונה של השיכון.
* '''משפט הפאון של אוילר:''' לכל גרף מישורי סופי קשיר מסדר <math>n</math> וממידה <math>m</math> מספר הפאות <math>f</math> לא תלוי בשיכון הנאות ומקיים <math>n-m+f=2</math>.
* יהי <math>G</math> גרף פשוט וקשיר מסדר <math>n\ge3</math>. אם <math>G</math> מישורי אז <math>|E(G)|\le3n-6</math>.
* יהי <math>G</math> פשוט וקשיר מסדר <math>n</math> ומותן <math>g<\infty</math>. אם <math>G</math> מישורי אז <math>|E(G)|\le g\frac{n-2}{g-2}</math>.
* '''משפט קורטובסקי:''' גרף אינו מישורי אם״ם יש לו תת־גרף שאיזומורפי לחלוקה של <math>K_5</math> או של <math>K_{3,3}</math>.
* '''משפט וגנר:''' גרף אינו מישורי אם״ם יש לו מינור שאיזומורפי ל־<math>K_5</math> או ל־<math>K_{3,3}</math>.
* '''גרף חוץ־מישורי''' הוא גרף שניתן לשכן באופן נאות במישור כך שקודקודיו על מעגל וצלעותיו קטעים ישרים.
* גרף הוא חוץ־מישורי אם״ם אין לו מינור שאיזומורפי ל־<math>K_4</math> או ל־<math>K_{2,3}</math>.
=== חלוקות ====
* '''חלוקה אלמנטרית''' של צלע <math>e=(u,v)</math> בגרף <math>G</math> היא <math>G\setminus\{e\}\cup\Big(\{e\},\{(u,e),(v,e)\}\Big)</math>.
* '''חלוקה''' של גרף היא היא גרף המתקבל מסדרה של חלוקות אלמנטריות.
=== כיווץ ===
* '''כיווץ''' של גרף <math>G</math> בצלע <math>e=(u,v)</math> הוא <math>G/e:=G\setminus\{u,v\}\cup\Big(\{e\},\{e\}\times(N_G(u)\cup N_G(v))\Big)</math>.
* '''מינור''' של גרף פשוט הוא גרף המתקבל ממנו ע״י סדרה של השמטות קודקודים, השמטות צלעות וכיווצי צלעות.
* '''תכונה מונוטונית''' של גרף היא תכונה הסגורה תחת מינור, כלומר אם גרף מקיים אותה אז כל מינור שלו מקיים אותה.
* '''השערת וגנר:''' כל תכונה היא מונוטונית אם״ם היא מוגדרת ע״י קבוצה סופית של מינורים אסורים, כלומר קיים מספר סופי של גרפים שאיזומורפים למינור כלשהו של <math>G</math> אם״ם הוא אינו מקיים את התכונה.
* '''משפט רוברטסון–סימור:''' השערת וגנר נכונה.
<gallery widths="75" hights="75" perrow="5" style="float:left;">
תמונה:Tetrahedron.jpg|טטרהדרון
תמונה:Hexahedron.jpg|הקסהדרון
תמונה:Octahedron.jpg|אוקטהדרון
תמונה:Dodecahedron.jpg|דודקהדרון
תמונה:Icosahedron.jpg|איקוסהדרון
</gallery>
=== גופים אפלטוניים ===
* '''גוף אפלטוני''' הוא פאון תלת־מימדי שכל פאותיו מצולעים משוכללים חופפים.
* הגופים האפלטונים הם הטטרהדרון (<math>K_4</math>), ההקסהדרון (קובייה, <math>K_2^{\times3}</math>), האוקטהדרון (<math>K_{2,4}</math>), הדודקהדרון והאיקוסהדרון.
* הגרף של כל גוף אפלטוני הוא מישורי.
* '''פאון דואלי''' של גוף אפלטוני הוא הפאון המתקבל לאחר שלכל פאה בגוף האפלטוני שמים קודקוד במרכז ומחברים צלעות בין קודקודים של פאות להן צלע משותפת.
=== צביעת קודקודים ===
