שינויים

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

=== סוגים סוגי גרפים נפוצים ===* '''גרף ריק''' מסדר <math>n</math> מסומן <math>N_n</math> הוא הגרף שסדרו <math>n</math> ומידתו 0.* '''גרף מלא/שלם''' מסדר <math>n</math> (<math>K_n</math>) הוא הגרף שסדרו <math>n</math> ובין כל שני קודקודים יש צלע אחת בדיוק.-** '''קליקה''' בגרף היא תת־גרף מלא.-** '''מספר הקליקה''' של גרף <math>G</math> מסומן <math>\omega(G)</math> ושווה לסדר המקסימלי של קליקה ב־<math>G</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>2C_n</math> (<math>C_nn\ge3</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>G</math> הוא אורך המעגל הקטן ביותר בגרף, ומסומן <math>g(G)</math>. אם אין בגרף מעגלים (יער) אז <math>g(G)=\infty</math>.*** <math>g(G)\le2</math> אם״ם הגרף לא פשוט.

* '''גרף דו־צדדי (דו״צ)''' הוא גרף פשוט <math>G</math> שבו קיימת חלוקה <math>V(G)=AV^1\uplus BV^2</math> כך שאם ש־<math>(u,v)\in E(G)</math> אז <math>u\in Asubseteq V^1\ \and\ v\in B</math> או <math>v\in A\ \and\ u\in Btimes V^2</math>.** '''גרף דו־צדדי מלא''' <math>K_{m,n}</math> הוא הגרף שקודקודיו הם <math>V^1\uplus UV^2</math> (כאשר <math>\left|V^1\right|=n,\left|U^2\right|=m</math>) וצלעותיו <math>V^1\{(v,u):\ v\in times V\ \and\ u\in U\}^2</math>.** '''גרף ''r''־צדדי''' הוא גרף <math>G</math> בו ישר יש חלוקה <math>V(G)=\biguplus_{i=1}^r V^i</math> ל־<math>r</math> תתי־קבוצות כך שלכל <math>i</math>, הקודקודים ב־<math>V^i</math> אינם שכנים, כלומר <math>E(G)\subseteq\bigcup_{i\ne j}V^i\times V^j</math>.** '''גרף ''r''־צדדי מלא''' הוא גרף <math>r</math>־צדדי <math>G</math> בו <math>E(G)=\forall bigcup_{i\ne j:\ \forall u\in }V^i\ \and\ v\in times V^j:\ (u,v)\in E(G)</math>, כלומר שני קודקודים הם שכנים אם״ם הם נמצאים בצדדים שונים.

** '''גרף טורן''' <math>T(n,r)</math> הוא הגרף ה־<math>r</math>־צדדי סימטרי מלאמסדר <math>n</math>.* '''גרף מסומן''' הוא גרף שקודקודיו סומנו ע״י <math>\{v_i\}_{i=1}^n</math>. שני גרפים מסומנים הם זהים אם״ם קיים איזומורפיזם <math>\varphi</math> בינהם כך ש־<math>\forall i:\ \varphi(v_i)=v_i</math>.

** '''עץ''' הוא יער קשיר.*** גרף פשוט הוא עץ אם״ם בין כל שני קודקודים יש מסילה יחידה.*** '''עלה''' הוא קודקוד בעץ שדרגתו 1.*** בכל עץ סופי מסדר גדול מ־1 יש עלה.*** גרף הוא עץ אם״ם הוא קשיר מינימלי, כלומר הוא קשיר וכל השמטת צלע יוצרת תת־גרף לא קשיר.*** גרף הוא עץ אם״ם הוא מקסימלי ללא מעגלים, כלומר הוא עץ וכל הוספת צלע יוצרת מעגל.*** '''חיפוש DFS:''' נרצה ליצור הילוך שעובר על כל קודקודי העץ. מתחילים באחד מהעלים. בכל צעד אם אנו נמצאים על קודקוד שעל כל ילדיו כבר נערך חיפוש, נפנה להורה שלו. אחרת נפנה לאחד מילדיו.*** '''עץ פורש''' הוא תת־גרף פורש קשיר ללא מעגלים.**** לכל גרף קשיר וסופי קיים עץ פורש.***** '''בעיית הסוכן הנוסע:''' נתו גרף קשיר וסופי ורוצים למצוא את ההילוך הקצר ביותר העובר דרך כל קודקודי הגרף. הפתרון הכי יעיל לא ידוע, אבל יש פתרון הנותן הילוך שאורכו לכל היותר פי 2 מהפתרון המינימלי: מוצאים עץ פורש לגרף ומבצעים עליו חיפוש DFS.** ביער מסדר <math>n\in\mathbb N</math> עם <math>k</math> רכיבי קשירות יש <math>n-k</math> צלעות.** גרף הוא יער אם״ם אין לו מינור שאיזומורפי ל־<math>K_3</math>.

** מספר רכיבי הקשירות בגרף <math>G</math> יסומן <math>K(G)</math>.** '''גרף קשיר''' הוא גרף שבו יש רכיב קשירות אחד.*** גרף הוא קשיר אם״ם הוא אינו איחוד זר של שני גרפים. 

** '''אוילריאן''' הוא גרף בו קיים מסלול אוילר סגור.** '''סמי־אוילריאן''' הוא גרף בו קיים מסלול אוילר.** '''משפט אוילר:''' גרף קשיר וסופי ללא לולאות הוא אוילריאן אם״ם דרגות כל הקודקודים זוגיות.*** גרף <math>G</math> קשיר וסופי ללא לולאות הוא סמי־אוילריאן שאינו אוילריאן אם״ם דרגות כל הקודקודים זוגיות פרט לשני קודקודים.

** '''מעגל המילטוניאני''' הוא מסילה המילטוניאנית סגורה.*** '''המילטוניאן''' הוא גרף בו קיים מעגל המילטוניאני.**** '''משפט דיראקהילוך אקראי:''' יהי <math>G</math> גרף פשוט מסדר לא מכוון וסופי. במצב ההתחלתי <math>np_0</math>. אם נמצאים על הקודקוד <math>v_0\deltain V(G)\ge\frac n2</math> אז בהסתברות 1, ובכל צעד פונים לשכן של הקודקוד הנוכחי כאשר לכל שכן הסתברות שווה. ההילוך שנוצר מקודקודים אלו נקרא הילוך אקראי.* '''הסתברות החזרה''' בזמן <math>t</math> היא ההסתברות שלאחר <math>t</math> צעדים נהיה על הקודקוד בו התחלנו, ומסומנת <math>P_G(v_0,t)</math> כאשר <math>v_0</math> הקודקוד ההתחלתי.* '''הסתברות החזרה הממוצעת''' בזמן <math>t</math> היא <math>P_G(t):=\frac1{|V(G)|}\sum_{v\in V(G)}P_G(v,t)</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</math> בו לכל <math>u,v\in V(G)</math> קיים אוטומורפיזם <math>\varphi:V(G)\to V(G)</math> כך ש־<math>\varphi(u)=v</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>e=(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>Gsetminus\cong H</math> אז הפרמטרים הבאים שווים:** סדר: <math>|V{e\}\cup\Big(G)|=|V(H)|</math>.** מידה: <math>|E(G)|=|E(H)|</math>.** מספר רכיבי הקשירות: <math>K(G)=K(H)</math>.** וקטור דרגות (וקטור דרגות של גרף הוא וקטור שרכיביו הם דרגות הקודקודים מסודרות בסדר יורד חלש).** קוטר: <math>\operatorname{diametere\}(G)=,\operatorname{diameter}(Hu,e),(v,e)</math>.* '''גרף מסומן''' הוא גרף שקודקודיו סומנו ע״י <math>\{v_i\}_{i=1}^n</math>. שני גרפים מסומנים הם זהים אם״ם קיים איזומורפיזם <math>\varphi</math> בינהם כך ש־<math>\forall i:\ \varphi(v_iBig)=v_i</math>.** '''משפט קיילי:חלוקה''' יש <math>n^{n-2}</math> עצים מסומנים מסדר <math>n</math>של גרף היא היא גרף המתקבל מסדרה של חלוקות אלמנטריות.

==== כיווץ ====* '''גרף טרנזיטיבי קודקודיםכיווץ''' הוא של גרף <math>G</math> בו לכל בצלע <math>e=(u,v\in V(G)</math> קיים אוטומורפיזם הוא <math>\varphiG/e:V(=G)\to Vsetminus\{u,v\}\cup\Big(G)</math> כך ש־<math>\varphi{e\},\{e\}\times(N_G(u)=\cup N_G(v))\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>K_4</math>), ההקסהדרון (קובייה, <math>K_2^{\times3}</math>), האוקטהדרון (<math>K_{2,4}</math>), הדודקהדרון והאיקוסהדרון.* הגרף של כל גוף אפלטוני הוא מישורי.

=== שידוכים שידוך ===

* אם <math>f:A\to B</math> שידוך אז <math>\{(u,f(u)):\ u\in A\}</math> קבוצה בלתי־תלויה.* '''שידוך מלא''' מ־<math>V^1</math> ל־<math>V^2</math> בגרף <math>G</math> דו־צדדי ש־<math>V^1,V^2</math> הם הצדדים שלו צדדיו הינו התאמה חח״ע (לאו דווקא על) <math>f:V^1\to V^2</math> כך ש־<math>\forall u\in V^1:\ (u,f(u))\in E(G)</math>.* '''משפט הול (Hall):''' לכל גרף דו־צדדי שצדדיו <math>V^1,V^2</math> קיים שידוך מלא מ־<math>V^1</math> ל־<math>V^2</math> אם״ם <math>\forall A\subseteq V^1:\ |N_G(A)|\ge|A|</math>.

** אם <math>r\mid n</math> אז <math>T(n,r)</math> הוא <math>\left(n-\frac nr\right)</math>־רגולרי ו־<math>\operatorname{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>t</math> ב־<math>G</math> הוא <math>\operatorname{tr}\!\left(A_G^t\right)</math> (כאשר שני הילוכים שמתחילים בנקודות שונות הם שונים גם אם הם עוברים על אותן נקודות).* נסמן <math>\operatorname{spec}(A_G)=\operatorname{spec}(G)</math> כרב־קבוצה של הע״ע של <math>A_G</math> (כאשר כל ע״ע מופיע בריבוי השווה לריבוי האלגברי שלו).

* הלפלסיאן של גרף לא מכוון היא הוא מטריצה סימטרית.