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

גרסה מ־21:12, 11 בפברואר 2013

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

הגדרות

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

סוגים נפוצים

גרף ריק מסדר $n$ מסומן $N_n$ הוא הגרף שסדרו $n$ ומידתו 0.
גרף מלא/שלם מסדר () הוא הגרף שסדרו ובין כל שני קודקודים יש צלע אחת בדיוק.
- קליקה בגרף היא תת־גרף מלא.
- מספר הקליקה של גרף $G$ מסומן $\omega(G)$ ושווה לסדר המקסימלי של קליקה ב־ $G$ .
מסילה מסדר $n$ ( $P_n$ ) הוא הגרף שסדרו $n$ ושניתן לסדר את קודקודיו כ־ $v_1,\dots,v_n$ ואז $E=\{(v_i,v_{i+1}):\ 1\le i<n\}$ .
מעגל מסדר () הוא הגרף שסדרו ושניתן לסדר את קודקודיו כ־ ואז .
- אם $\delta(G)\ge 2$ אז יש ב־ $G$ מעגל.
- מותן (girth) של גרף הוא אורך המעגל הקטן ביותר בגרף, ומסומן . אם אין בגרף מעגלים (יער) אז .
  - $g(G)\le2$ אם״ם הגרף לא פשוט.
גרף d־רגולרי הוא גרף שבו דרגת כל קודקוד היא .
- גרף הוא ריק אם״ם הוא 0־רגולרי.
- גרף 1־רגולרי ופשוט הוא איחוד זר של צלעות.
- גרף 2־רגולרי ופשוט הוא איחוד זר של מעגלים.
- אם גרף סופי ופשוט הוא $d$ ־רגולרי כך ש־ $d$ אי־זוגי אזי הגרף מסדר זוגי.
- גרף d⁺־רגולרי הוא גרף מכוון שבו הדרגה היוצאת של כל קודקוד היא $d$ . באותו אופן מגדירים גרף $d^-$ ־רגולרי.
גרף דו־צדדי (דו״צ) הוא גרף פשוט שבו קיימת חלוקה כך שאם אז או .
- גרף דו־צדדי מלא $K_{m,n}$ הוא הגרף שקודקודיו הם $V\uplus U$ (כאשר $|V|=n,|U|=m$ ) וצלעותיו $\{(v,u):\ v\in V\ \and\ u\in U\}$ .
- גרף r־צדדי הוא גרף $G$ בו ישר חלוקה $V(G)=\biguplus_{i=1}^r V^i$ ל־ $r$ תתי־קבוצות כך שלכל $i$ , הקודקודים ב־ $V^i$ אינם שכנים.
- גרף r־צדדי מלא הוא גרף $r$ ־צדדי $G$ בו $\forall i\ne j:\ \forall u\in V^i\ \and\ v\in V^j:\ (u,v)\in E(G)$ , כלומר שני קודקודים הם שכנים אם״ם הם נמצאים בצדדים שונים.
- גרף r־צדדי סימטרי הוא גרף $r$ ־צדדי בו $\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\}$ .
- גרף טורן $T(n,r)$ הוא הגרף ה־ $r$ ־צדדי סימטרי מלא.

עצים

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

הילוכים

הילוך בגרף הוא סדרת קודקודים (חזרות מותרות) כך שכל קודקוד שכן של הסמוכים לו. כלומר, זו סדרה כך ש־.
- אורך ההילוך הוא – מספר הצלעות שבו, כלומר מספר הקודקודים פחות 1.
  - המרחב בין שני קודקודים הוא המרחק המינימלי של הילוך בינהם (אם יש כזה) ומסומן .
    - הקוטר של גרף הוא $\mbox{diameter}(G)=\max\{\mbox{dist}_G(u,v):\ u,v\in V(G)\}$ .
- ההילוך סגור אם $v_0=v_n$ .
מסלול הוא הילוך שבו אין צלעות חוזרות.
מסילה היא הילוך שבו אין קודקודים חוזרים, למעט אם הקודקוד הראשון שווה לקודקוד האחרון.
- כל מסילה היא מסלול.
קיים הילוך בין שני קודקודים אם״ם קיימת מסילה בינהם.
רכיב קשירות בגרף לא מכוון הוא מחלקת שקילות של יחס השקילות המקיים אם״ם יש מסילה בין .
- מספר רכיבי הקשירות בגרף $G$ יסומן $K(G)$ .
- גרף קשיר הוא גרף שבו יש רכיב קשירות אחד.
  - גרף הוא קשיר אם״ם הוא אינו איחוד זר של שני גרפים.

מסלול אוילר בגרף ללא לולאות הוא מסלול המכיל את כל צלעות הגרף.
- אוילריאן הוא גרף בו קיים מסלול אוילר סגור.
- סמי־אוילריאן הוא גרף בו קיים מסלול אוילר.
- משפט אוילר: גרף קשיר וסופי ללא לולאות הוא אוילריאן אם״ם דרגות כל הקודקודים זוגיות.
  - גרף $G$ קשיר וסופי ללא לולאות הוא סמי־אוילריאן שאינו אוילריאן אם״ם דרגות כל הקודקודים זוגיות פרט לשני קודקודים.
מסילה המילטוניאנית בגרף היא מסילה המכילה את כל קודקודיו.
- מעגל המילטוניאני הוא מסילה המילטוניאנית סגורה.
  - המילטוניאן הוא גרף בו קיים מעגל המילטוניאני.
    - משפט דיראק: יהי $G$ גרף פשוט מסדר $n$ . אם $\delta(G)\ge\frac n2$ אז $G$ המילטוניאן.

תתי גרפים

השמטת צלע $e\in E$ מגרף $G$ היא הפיכת הגרף ל־ $G\setminus\{e\}:=(V,E\setminus\{e\})$ .
השמטת קודקוד $v\in V$ מגרף $G$ היא הפיכת הגרף ל־ $G\setminus\{v\}:=(V\setminus\{v\},E\setminus\{(v,u):\ u\in V\})$ .
תת־גרף הוא הגרף המתקבל מסדרה של השמטות קודקודים ו/או צלעות.
- תת־גרף פורש הוא תת־גרף המתקבל מסדרה של השמטות צלעות בלבד.
- תת־גרף מושרה הוא תת־גרף המתקבל מסדרה של השמטות קודקודים בלבד.
  - אם $H$ תת־גרף מושרה של $G$ אזי $\forall u,v\in V(H):\ \Big((u,v)\in E(G)\iff(u,v)\in E(H)\Big)$ . כלומר, כל שני קודקודים שכנים ב־ $H$ הם שכנים ב־ $G$ .

איזומורפיזם

איזומורפיזם בין מגרף $G$ לגרף $H$ הוא פונקציה $\varphi:V(G)\to V(H)$ חח״ע ועל ששומרת צלעות, כלומר $(u,v)\in E(G)\iff(\varphi(u),\varphi(v))\in E(H)$ לכל $u,v\in V(G)$ . אם קיים איזומורפיזם בין $G,H$ אז נאמר שהם איזומורפיים ונסמן $G\cong H$ (זה יחס שקילות).
אם אז הפרמטרים הבאים שווים:
- סדר: $|V(G)|=|V(H)|$ .
- מידה: $|E(G)|=|E(H)|$ .
- מספר רכיבי הקשירות: $K(G)=K(H)$ .
- וקטור דרגות (וקטור דרגות של גרף הוא וקטור שרכיביו הם דרגות הקודקודים מסודרות בסדר יורד חלש).
- קוטר: $\mbox{diameter}(G)=\mbox{diameter}(H)$ .
גרף מסומן הוא גרף שקודקודיו סומנו ע״י . שני גרפים מסומנים הם זהים אם״ם קיים איזומורפיזם בינהם כך ש־.
- משפט קיילי: יש $n^{n-2}$ עצים מסומנים מסדר $n$ .

גרף טרנזיטיבי קודקודים הוא גרף $G$ בו לכל $u,v\in V(G)$ קיים אוטומורפיזם $\varphi:V(G)\to V(G)$ כך ש־ $\varphi(u)=v$ .

גרף משלים

הגרף המשלים של גרף $G=(V,E)$ הוא $\overline G:=(V,V^2\setminus E)$ .
$G\cong H$ אם״ם $\overline G\cong\overline H$ .

גרף הקו

גרף הקו של גרף פשוט מסומן ומוגדר כגרף שקודקודיו הם וצלעותיו הם זוגות של צלעות שיש להן קודקוד משותף ב־, כלומר .
- $L(P_n)\cong P_{n-1}$ , $L(C_n)\cong C_n$ .

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

המכפלה הקרטזית של הגרפים $G,H$ היא גרף המסומן כ־ $G\times H$ . קודקודיו הם $V(G)\times V(H)$ וצלעותיו $\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\}$ .
קובייה n־מימדית היא $K_2^{\times n}:=\prod_{i=1}^n K_2$ . היא איזומורפית ל־ $B_n:=(\mathcal P([n]),\{(I,J):\ I\subset J\subseteq[n]\ \and\ |I|=|J|-1\})$ ול־ $H_n:=(\mathbb Z_2^n,\{(u,v):\ u,v\in\mathbb Z_2^n\ \and\ |u-v|=1\})$ .

שיכון

שיכון של גרף $G$ ב־ $\mathbb R^n$ הוא העתקה חח״ע $\varphi:V(G)\to\mathbb R^n$ . כל צלע $(u,v)\in E(G)$ מועתקת למסילה רציפה ופשוטה (כלומר, שאינה חותכת את עצמה) מ־ $\varphi(u)$ ל־ $\varphi(v)$ .
שיכון נאות הוא שיכון אם אין חיתוך צלעות לא טריוויאלי, כלומר התמונות של הצלעות ב־ $\mathbb R^n$ חותכות זו את זו רק בתמונות של קודקודי הגרף.
לכל גרף עם מספר בן מנייה של קודקודים קיים שיכון נאות ב־ $\mathbb R^3$ כך שהתמונות של הצלעות הן קטעים ישרים. אם הגרף הוא סופי ופשוט אז שיכון נאות מתאים הוא, לדוגמה, $\forall i:\ \varphi(v_i)=(i,i^2,i^3)$ כאשר $V=\{v_i\}_{i=1}^n$ .
גרף מישורי הוא גרף שניתן לשיכון נאות ב־ $\mathbb R^2$ .
פאה של שיכון נאות ב־ $\mathbb R^2$ היא רכיב קשירות ב־ $\mathbb R^2$ לאחר שהוציאו ממנו את התמונה של השיכון.
משפט הפאון של אוילר: לכל גרף מישורי סופי קשיר מסדר $n$ וממידה $m$ מספר הפאות $f$ לא תלוי בשיכון הנאות ומקיים $n-m+f=2$ .
יהי $G$ גרף פשוט וקשיר מסדר $n\ge3$ . אם $G$ מישורי אז $|E(G)|\le3n-6$ .
יהי $G$ פשוט וקשיר מסדר $n$ ומותן $g<\infty$ . אם $G$ מישורי אז $|E(G)|\le g\frac{n-2}{g-2}$ .
משפט קורטובסקי: גרף אינו מישורי אם״ם יש לו תת־גרף שאיזומורפי לחלוקה של $K_5$ או של $K_{3,3}$ .
משפט וגנר: גרף אינו מישורי אם״ם יש לו מינור שאיזומורפי ל־ $K_5$ או ל־ $K_{3,3}$ .
גרף חוץ־מישורי הוא גרף שניתן לשכן באופן נאות במישור כך שקודקודיו על מעגל וצלעותיו קטעים ישרים.
גרף הוא חוץ־מישורי אם״ם אין לו מינור שאיזומורפי ל־ $K_4$ או ל־ $K_{2,3}$ .
לכל גרף מישורי פשוט סופי $G$ מתקיים $\delta(G)\le5$ .

חלוקות

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

כיווץ

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

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

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

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

צביעה

k־צביעת קודקודים או k־צביעה בגרף $G$ ללא לולאות היא פונקציה $f:V(G)\to[k]$ .
k־צביעה כשרה היא $k$ ־צביעה $f$ שבה לכל צלע $(u,v)$ מתקיים $f(u)\ne f(v)$ . כלומר, קודקודים שכנים צבועים בצבעים שונים.
מספר הצביעה או המספר הכרומטי של גרף $G$ מסומן כ־ $\chi(G)$ ומוגדר כ־ $k$ המינימלי עבורו קיימת $k$ ־צביעה כשרה.
גרף k־צביע הוא גרף שקיימת לו $k$ ־צביעה כשרה, כלומר $\chi\le k$ .
לכל גרף $G$ פשוט $1\le\chi(G)\le|V(G)|$ . $\chi(G)=1$ אם״ם $G$ גרף ריק ו־ $\chi(G)=|V(G)|$ אם״ם הוא גרף מלא.
משפט ברוקס: לכל גרף $G$ פשוט וסופי $\chi(G)\le\Delta(G)+1$ ושוויון מתקיים אם״ם $\omega(G)=\Delta(G)+1$ או אם $G$ איחוד זר של מעגלים ומסילות ויש מעגל מסדר אי־זוגי.
יהא $G$ פשוט וסופי. $\chi(G)\le2$ אם״ם אין ב־ $G$ מעגלים מאורך אי־זוגי.
גרף הוא 2־צביע אם״ם הוא דו־צדדי.
בעיית 4 הצבעים: לכל גרף מישורי סופי פשוט $G$ הוא 4־צביע.
פולינום הצביעה בגרף פשוט וסופי מסומן . לכל טבעי מוגדר כמספר ה־־צביעות הכשרות. לשאר ה־־ים הוא ההשלמה של לפולינום.
- $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}$ .
$\forall x\in\mathbb N\ \and\ e\in E(G):\ f_G(x)=f_{G\setminus e}(x)-f_{G/e}(x)$ .
$f_G$ פולינום מתוקן ודרגתו $|V(G)|$ .
$\chi(G)=\max\{x\in\mathbb N_0:\ f_G(x)=0\}+1$ .
משפט סטנלי: מספר ההכוונות הלא מעגליות של $G$ הוא $(-1)^n f_G(-1)$ .
k־צביעת צלעות בגרף $G$ היא פונקציה $f:E(G)\to[k]$ .
k־צביעת צלעות כשרה היא $k$ ־צביעת צלעות בה אם לשתי צלעות יש קודקוד משותף אז הן צבועות בצבעים שונים.
אינדקס הצביעה $i(G)$ של גרף $G$ הוא ה־ $k$ המינימלי עבורו קיימת $k$ ־צביעת צלעות כשרה.
לכל גרף $G$ סופי $\Delta(G)\le i(G)$ . אם הוא לא ריק אז $i(G)\le2\Delta(G)-1$ .
אם $G$ דו־צדדי ו־ $d$ ־רגולרי אז $i(G)=d$ .

שידוכים

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

אי־תלות

קבוצה בלתי־תלויה של צלעות בגרף $G$ היא תת־קבוצה של $E(G)$ שבה אין שתי צלעות בעלות קודקוד משותף.
קבוצה בלתי תלויה של קודקודים בגרף $G$ היא תת־קבוצה של $V(G)$ שמשרה גרף ריק, כלומר שבה אין שני קודקודים שכנים.
$\alpha(G)$ הוא הגודל המקסימלי של קבוצה בלתי־תלויה של קודקודים ב־ $G$ .

בעיות קיצון

בעיית טורן

בעיית טורן: בהנתן גרף $H$ (או קבוצת גרפים $\mathbb H$ ) ומספר טבעי $n$ יש למצוא את המידה המקסימלית האפשרית בגרף פשוט מסדר $n$ שאין לו תת־גרף איזומורפי ל־ $H$ (או לאחד מהגרפים ב־ $\mathbb H$ ). מספר זה מסומן כ־ $\mbox{ex}(n,H)$ או $\mbox{ex}(n,\mathbb H)$ וגרף כזה נקרא גרף מרבי נמנע $H$ (או $\mathbb H$ ).
משפט טורן: הגרף המרבי נמנע היחיד מסדר הוא .
- אם $r\mid n$ אז $T(n,r)$ הוא $\left(n-\frac nr\right)$ ־רגולרי ו־ $\mbox{ex}(n,K_{n+1})=\frac{n^2}2\left(1-\frac1r\right)$ .

תורת רמזי

מספר רמזי $R(s,t)$ הוא הסדר המינימלי כך שאם $G$ גרף מסדר זה אז $K_s$ תת־גרף של $G$ או ש־ $K_t$ תת־גרף של $\overline G$ .
למת לחיצות הידיים: עבור כל גרף פשוט מסדר 6 או ש־ $G$ מכיל משולש או ש־ $\overline G$ מכיל משולש. (למעשה, $R(3,3)=6$ .)
$R(1,t)=1\ \and\ R(2,t)=t\ \and\ R(s,t)=R(t,s)$ ואם $t,s\ge3$ אז $R(s,t)\le R(s-1,t)+R(s,t-1)$ .
$R(s,t)\le\binom{s+t-2}{s-1}$ .

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

מטריצת השכנות של גרף סופי $G$ (מכוון או לא) כך ש־ $V=\{v_i\}_{i=1}^n$ היא $A_G\in\mathbb N_0^{n\times n}$ שבה $a_{ij}$ הוא מספר הצלעות מ־ $v_i$ ל־ $v_j$ .
אם $G$ לא מכוון אז $A_G$ סימטרית.
לכל גרף סופי מתקיים $\sum_{i=1}^n a_{ij}=d_G^-(v_j)\ \and\ \sum_{j=1}^n a_{ij}=d_G^+(v_i)$ .
העקבה $\mbox{tr}(A_G)$ היא מספר הלולאות ב־ $G$ .
יהי $G$ פשוט ולא מכוון. אזי $\mbox{tr}(A_G^2)=\frac12|E(G)|$ .
יהי $G$ לא מכוון. אזי $|E(G)|=\sum_{i\le j}a_{ij}$ .
מספר ההילוכים מ־ ל־ מאורך הוא .
- מספר ההילוכים הסגורים מאורך $t$ ב־ $G$ הוא $\mbox{tr}(A_G^t)$ (כאשר שני הילוכים שמתחילים בנקודות שונות הם שונים גם אם הם עוברים על אותן נקודות).

הילוכים אקראיים

הילוך אקראי: יהי $G$ גרף לא מכוון וסופי. במצב ההתחלתי $p_0$ נמצאים על הקודקוד $v_0\in V(G)$ בהסתברות 1, ובכל צעד פונים לשכן של הקודקוד הנוכחי כאשר לכל שכן הסתברות שווה. ההילוך שנוצר מקודקודים אלו נקרא הילוך אקראי.
הסתברות החזרה בזמן $t$ היא ההסתברות שלאחר $t$ צעדים נהיה על הקודקוד בו התחלנו, ומסומנת $P_G(v_0,t)$ כאשר $v_0$ הקודקוד ההתחלתי.
הסתברות החזרה הממוצעת בזמן $t$ היא $P_G(t):=\frac1{|V(G)|}\sum_{v\in V(G)}P_G(v,t)$ .
בגרף טרנזיטיבי קודקודים $\forall v\in V(G):\ P_G(v,t)=P_G(t)$ .
יהא $G$ לא מכוון, סופי ו־ $d$ ־רגולרי מסדר $n$ . נסמן $\mbox{spec}(A_G)$ כרב־קבוצה של הע״ע (כאשר כל ע״ע מופיע בריבוי השווה לריבוי האלגברי שלו). הע״ע ממשיים ולכן ניתן לסדר אותם בסדר יורד חלש $\lambda_0\ge\lambda_1\ge\dots\ge\lambda_{n-1}$ . אזי $\forall t\in\mathbb N_0:\ P_G(t)=\sum_{i=0}^{n-1}\frac{\lambda_i^t}{d^tn}$ .

@@ שורה 1: / שורה 1: @@
+בתקציר זה, אלא אם צוין אחרת, נסמן <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> רב קבוצה של זוגות לא סדורים של קודקודים (הזוגות נקראים "צלעות" או "קשתות").
@@ שורה 5: / שורה 6: @@
 * '''גרף מכוון''' הוא גרף בו הצלעות הן זוגות סדורים.
 ** '''אי־הכוונה''' של גרף מכוון היא הפיכתו לגרף לא מכוון ע״י הפיכת צלעותיו לזוגות לא סדורים.
+** '''הכוונה''' של גרף לא מכוון היא הפיכתו לגרף מכוון. תיתכן יותר מהכוונה אפשרית אחת.
+*** '''הכוונה מעגלית''' היא הכוונה שבה יש מעגל מכוון.
 * '''גרף סופי''' הוא גרף בו <math>|V|,|E|<\infty</math>.
 * '''סדר''' של גרף הוא מספר הקודקודים בו, כלומר <math>|V|</math>. לעתים מסומן <math>n(G)</math>.
@@ שורה 15: / שורה 18: @@
 *** מתקיים <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>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}</math> הוא הגרף שקודקודיו הם <math>V\uplus U</math> (כאשר <math>|V|=n,|U|=m</math>) וצלעותיו <math>\{(v,u):\ v\in V\ \and\ u\in U\}</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>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>.
@@ שורה 32: / שורה 36: @@
 ** אם גרף סופי ופשוט הוא <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>־צדדי סימטרי מלא.
 ==== עצים ====
@@ שורה 91: / שורה 101: @@
 * '''גרף מסומן''' הוא גרף שקודקודיו סומנו ע״י <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>.
 === גרף משלים ===
@@ שורה 117: / שורה 129: @@
 * '''גרף חוץ־מישורי''' הוא גרף שניתן לשכן באופן נאות במישור כך שקודקודיו על מעגל וצלעותיו קטעים ישרים.
 * גרף הוא חוץ־מישורי אם״ם אין לו מינור שאיזומורפי ל־<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>.
 * '''חלוקה''' של גרף היא היא גרף המתקבל מסדרה של חלוקות אלמנטריות.
@@ שורה 129: / שורה 142: @@
 * '''משפט רוברטסון–סימור:''' השערת וגנר נכונה.
+=== גופים אפלטוניים ===
 <gallery widths="75" hights="75" perrow="5" style="float:left;">
 תמונה:Tetrahedron.jpg|טטרהדרון
@@ שורה 136: / שורה 150: @@
 תמונה:Icosahedron.jpg|איקוסהדרון
 </gallery>
-=== גופים אפלטוניים ===
 * '''גוף אפלטוני''' הוא פאון תלת־מימדי שכל פאותיו מצולעים משוכללים חופפים.
 * הגופים האפלטונים הם הטטרהדרון (<math>K_4</math>), ההקסהדרון (קובייה, <math>K_2^{\times3}</math>), האוקטהדרון (<math>K_{2,4}</math>), הדודקהדרון והאיקוסהדרון.
@@ שורה 142: / שורה 155: @@
 * '''פאון דואלי''' של גוף אפלטוני הוא הפאון המתקבל לאחר שלכל פאה בגוף האפלטוני שמים קודקוד במרכז ומחברים צלעות בין קודקודים של פאות להן צלע משותפת.
-=== צביעת קודקודים ===
+=== צביעה ===
+* '''''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>.
+*