שינויים
בתקציר זה, אלא אם צוין אחרת, נסמן <math>[n]:=\{1,2,\dots,n\}</math>. <math>(\cdot,\cdot)</math> הוא זוג לא סדור (אלא אם מדובר בגרפים לא מכוונים) ומכפלה קרטזית <math>A\times B</math> של קבוצות היא קבוצת הזוגות הלא סדורים של איברי <math>A,B</math>.
== הגדרות ==
* '''גרף''' הוא זוג <math>G=(V,E)</math> כך ש־<math>V</math> קבוצת קודקודים (נקראים גם "צמתים") ו־<math>E</math> רב קבוצה של זוגות לא סדורים של קודקודים (הזוגות נקראים "צלעות" או "קשתות").
* '''גרף מכוון''' הוא גרף בו הצלעות הן זוגות סדורים.
** '''אי־הכוונה''' של גרף מכוון היא הפיכתו לגרף לא מכוון ע״י הפיכת צלעותיו לזוגות לא סדורים.
** '''הכוונה''' של גרף לא מכוון היא הפיכתו לגרף מכוון. תיתכן יותר מהכוונה אפשרית אחת.
*** '''הכוונה מעגלית''' היא הכוונה שבה יש מעגל מכוון.
* '''גרף סופי''' הוא גרף בו <math>|V|,|E|<\infty</math>.
* '''סדר''' של גרף הוא מספר הקודקודים בו, כלומר <math>|V|</math>. לעתים מסומן <math>n(G)</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>A\subseteq V(G)</math> אז <math>N_G(A):=\bigcup_{v\in A}N_G(v)=\{u:\ \exists v\in A:\ (u,v)\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}G</math> הוא הגרף שקודקודיו הם מסומן <math>V\uplus U</math> omega(כאשר <math>|V|=n,|U|=mG)</math>) וצלעותיו ושווה לסדר המקסימלי של קליקה ב־<math>\{(v,u):\ v\in V\ \and\ u\in U\}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>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>d</math>־רגולרי כך ש־<math>d</math> אי־זוגי אזי הגרף מסדר זוגי.
** '''גרף {{ltr|''d<sup>+</sup>''}}־רגולרי''' הוא גרף מכוון שבו הדרגה היוצאת של כל קודקוד היא <math>d</math>. באותו אופן מגדירים גרף <math>d^-</math>־רגולרי.
* '''גרף דו־צדדי (דו״צ)''' הוא גרף פשוט <math>G</math> שבו קיימת חלוקה <math>V(G)=A\uplus B</math> כך שאם <math>(u,v)\in E(G)</math> אז <math>u\in A\ \and\ v\in B</math> או <math>v\in A\ \and\ u\in B</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>.
** '''גרף ''r''־צדדי''' הוא גרף <math>G</math> בו ישר חלוקה <math>V(G)=\biguplus_{i=1}^r V^i</math> ל־<math>r</math> תתי־קבוצות כך שלכל <math>i</math>, הקודקודים ב־<math>V^i</math> אינם שכנים.
** '''גרף ''r''־צדדי מלא''' הוא גרף <math>r</math>־צדדי <math>G</math> בו <math>\forall i\ne j:\ \forall u\in V^i\ \and\ v\in V^j:\ (u,v)\in E(G)</math>, כלומר שני קודקודים הם שכנים אם״ם הם נמצאים בצדדים שונים.
** '''גרף ''r''־צדדי סימטרי''' הוא גרף <math>r</math>־צדדי בו <math>\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>T(n,r)</math> הוא הגרף ה־<math>r</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</math> בו לכל <math>u,v\in V(G)</math> קיים אוטומורפיזם <math>\varphi:V(G)\to V(G)</math> כך ש־<math>\varphi(u)=v</math>.
=== גרף משלים ===
* '''גרף חוץ־מישורי''' הוא גרף שניתן לשכן באופן נאות במישור כך שקודקודיו על מעגל וצלעותיו קטעים ישרים.
* גרף הוא חוץ־מישורי אם״ם אין לו מינור שאיזומורפי ל־<math>K_4</math> או ל־<math>K_{2,3}</math>.
* לכל גרף מישורי פשוט סופי <math>G</math> מתקיים <math>\delta(G)\le5</math>.
=== חלוקות ====
* '''חלוקה אלמנטרית''' של צלע <math>e=(u,v)</math> בגרף <math>G</math> היא <math>G\setminus\{e\}\cup\Big(\{e\},\{(u,e),(v,e)\}\Big)</math>.
* '''חלוקה''' של גרף היא היא גרף המתקבל מסדרה של חלוקות אלמנטריות.
* '''משפט רוברטסון–סימור:''' השערת וגנר נכונה.
=== גופים אפלטוניים ===
<gallery widths="75" hights="75" perrow="5" style="float:left;">
תמונה:Tetrahedron.jpg|טטרהדרון
תמונה:Icosahedron.jpg|איקוסהדרון
</gallery>
* '''גוף אפלטוני''' הוא פאון תלת־מימדי שכל פאותיו מצולעים משוכללים חופפים.
* הגופים האפלטונים הם הטטרהדרון (<math>K_4</math>), ההקסהדרון (קובייה, <math>K_2^{\times3}</math>), האוקטהדרון (<math>K_{2,4}</math>), הדודקהדרון והאיקוסהדרון.
* '''פאון דואלי''' של גוף אפלטוני הוא הפאון המתקבל לאחר שלכל פאה בגוף האפלטוני שמים קודקוד במרכז ומחברים צלעות בין קודקודים של פאות להן צלע משותפת.
=== צביעת צביעה ===* '''''k''־צביעת קודקודים''' או '''''k''־צביעה''' בגרף <math>G</math> ללא לולאות היא פונקציה <math>f:V(G)\to[k]</math>.* '''''k''־צביעה כשרה''' היא <math>k</math>־צביעה <math>f</math> שבה לכל צלע <math>(u,v)</math> מתקיים <math>f(u)\ne f(v)</math>. כלומר, קודקודים שכנים צבועים בצבעים שונים.* '''מספר הצביעה''' או '''המספר הכרומטי''' של גרף <math>G</math> מסומן כ־<math>\chi(G)</math> ומוגדר כ־<math>k</math> המינימלי עבורו קיימת <math>k</math>־צביעה כשרה.* '''גרף ''k''־צביע''' הוא גרף שקיימת לו <math>k</math>־צביעה כשרה, כלומר <math>\chi\le k</math>.* לכל גרף <math>G</math> פשוט <math>1\le\chi(G)\le|V(G)|</math>. <math>\chi(G)=1</math> אם״ם <math>G</math> גרף ריק ו־<math>\chi(G)=|V(G)|</math> אם״ם הוא גרף מלא.* '''משפט ברוקס:''' לכל גרף <math>G</math> פשוט וסופי <math>\chi(G)\le\Delta(G)+1</math> ושוויון מתקיים אם״ם <math>\omega(G)=\Delta(G)+1</math> או אם <math>G</math> איחוד זר של מעגלים ומסילות ויש מעגל מסדר אי־זוגי.* יהא <math>G</math> פשוט וסופי. <math>\chi(G)\le2</math> אם״ם אין ב־<math>G</math> מעגלים מאורך אי־זוגי.* גרף הוא 2־צביע אם״ם הוא דו־צדדי.* '''בעיית 4 הצבעים:''' לכל גרף מישורי סופי פשוט <math>G</math> הוא 4־צביע.* '''פולינום הצביעה''' בגרף פשוט וסופי מסומן <math>f_G</math>. לכל <math>x</math> טבעי <math>f_G(x)</math> מוגדר כמספר ה־<math>x</math>־צביעות הכשרות. לשאר ה־<math>x</math>־ים <math>f_G(x)</math> הוא ההשלמה של <math>f_G</math> לפולינום.** <math>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>\forall x\in\mathbb N\ \and\ e\in E(G):\ f_G(x)=f_{G\setminus e}(x)-f_{G/e}(x)</math>.* <math>f_G</math> פולינום מתוקן ודרגתו <math>|V(G)|</math>.* <math>\chi(G)=\max\{x\in\mathbb N_0:\ f_G(x)=0\}+1</math>.* '''משפט סטנלי:''' מספר ההכוונות הלא מעגליות של <math>G</math> הוא <math>(-1)^n f_G(-1)</math>.* '''''k''־צביעת צלעות''' בגרף <math>G</math> היא פונקציה <math>f:E(G)\to[k]</math>.* '''''k''־צביעת צלעות כשרה''' היא <math>k</math>־צביעת צלעות בה אם לשתי צלעות יש קודקוד משותף אז הן צבועות בצבעים שונים.* '''אינדקס הצביעה''' <math>i(G)</math> של גרף <math>G</math> הוא ה־<math>k</math> המינימלי עבורו קיימת <math>k</math>־צביעת צלעות כשרה.* לכל גרף <math>G</math> סופי <math>\Delta(G)\le i(G)</math>. אם הוא לא ריק אז <math>i(G)\le2\Delta(G)-1</math>.* אם <math>G</math> דו־צדדי ו־<math>d</math>־רגולרי אז <math>i(G)=d</math>. === שידוכים ===* '''שידוך''' בגרף <math>G</math> הוא התאמה חח״ע ועל <math>f:A\to B</math> כאשר <math>A\uplus B\subseteq V(G)</math> ו־<math>\forall u\in A:\ (u,f(u))\in E(G)</math>.* '''שידוך מושלם''' <math>f:A\to B</math> הוא שידוך בו <math>A\uplus B=V(G)</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>G</math> היא תת־קבוצה של <math>E(G)</math> שבה אין שתי צלעות בעלות קודקוד משותף.* '''קבוצה בלתי תלויה של קודקודים''' בגרף <math>G</math> היא תת־קבוצה של <math>V(G)</math> שמשרה גרף ריק, כלומר שבה אין שני קודקודים שכנים.* <math>\alpha(G)</math> הוא הגודל המקסימלי של קבוצה בלתי־תלויה של קודקודים ב־<math>G</math>. === בעיות קיצון ======= בעיית טורן ====* '''בעיית טורן:''' בהנתן גרף <math>H</math> (או קבוצת גרפים <math>\mathbb H</math>) ומספר טבעי <math>n</math> יש למצוא את המידה המקסימלית האפשרית בגרף פשוט מסדר <math>n</math> שאין לו תת־גרף איזומורפי ל־<math>H</math> (או לאחד מהגרפים ב־<math>\mathbb H</math>). מספר זה מסומן כ־<math>\mbox{ex}(n,H)</math> או <math>\mbox{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>\mbox{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>.* '''למת לחיצות הידיים:''' עבור כל גרף פשוט מסדר 6 או ש־<math>G</math> מכיל משולש או ש־<math>\overline G</math> מכיל משולש. (למעשה, <math>R(3,3)=6</math>.)* <math>R(1,t)=1\ \and\ R(2,t)=t\ \and\ R(s,t)=R(t,s)</math> ואם <math>t,s\ge3</math> אז <math>R(s,t)\le R(s-1,t)+R(s,t-1)</math>.* <math>R(s,t)\le\binom{s+t-2}{s-1}</math>. === תורת הגרפים האלגברית ===* '''מטריצת השכנות''' של גרף סופי <math>G</math> (מכוון או לא) כך ש־<math>V=\{v_i\}_{i=1}^n</math> היא <math>A_G\in\mathbb N_0^{n\times n}</math> שבה <math>a_{ij}</math> הוא מספר הצלעות מ־<math>v_i</math> ל־<math>v_j</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>\mbox{tr}(A_G)</math> היא מספר הלולאות ב־<math>G</math>.* יהי <math>G</math> פשוט ולא מכוון. אזי <math>\mbox{tr}(A_G^2)=\frac12|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>\mbox{tr}(A_G^t)</math> (כאשר שני הילוכים שמתחילים בנקודות שונות הם שונים גם אם הם עוברים על אותן נקודות). === הילוכים אקראיים ===* '''הילוך אקראי:''' יהי <math>G</math> גרף לא מכוון וסופי. במצב ההתחלתי <math>p_0</math> נמצאים על הקודקוד <math>v_0\in V(G)</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>\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}^{n-1}\frac{\lambda_i^t}{d^tn}</math>.*
