לדלג לתוכן
שינוי מצב סרגל צד
Math-Wiki
חיפוש
יצירת חשבון
כלים אישיים
יצירת חשבון
כניסה לחשבון
דפים לעורכים שלא נכנסו לחשבון
מידע נוסף
שיחה
תרומות
ניווט
עמוד ראשי
שינויים אחרונים
העלאת קובץ
כלים
דפים המקושרים לכאן
שינויים בדפים המקושרים
דפים מיוחדים
מידע על הדף
עריכת הדף "
תקציר תורת הגרפים, סמסטר א תשע״ג
" (פסקה)
דף
שיחה
עברית
קריאה
עריכה
גרסאות קודמות
עוד
קריאה
עריכה
גרסאות קודמות
אזהרה:
אינכם מחוברים לחשבון. כתובת ה־IP שלכם תוצג בפומבי אם תבצעו עריכות כלשהן. אם
תיכנסו לחשבון
או
תיצרו חשבון
, העריכות שלכם תיוחסנה לשם המשתמש שלכם ותקבלו גם יתרונות אחרים.
בדיקת אנטי־ספאם.
אין
למלא שדה זה!
== משפטים == * <math>\sum_{v\in V}d_G(v)=2|E(G)|</math>. * <math>\sum_{v\in V}d_G^+(v)=\sum_{v\in V}d_G^-(v)=|E(G)|</math>. * אם <math>\delta(G)\ge 2</math> אז יש ב־<math>G</math> מעגל. * <math>g(G)\le2</math> אם״ם הגרף לא פשוט. * גרף הוא ריק אם״ם הוא 0־רגולרי. * גרף 1־רגולרי ופשוט הוא איחוד זר של צלעות. * גרף 2־רגולרי ופשוט הוא איחוד זר של מעגלים. * אם גרף סופי ופשוט הוא <math>d</math>־רגולרי כך ש־<math>d</math> אי־זוגי אזי הגרף מסדר זוגי. * גרף פשוט הוא עץ אם״ם בין כל שני קודקודים יש מסילה יחידה. * בכל עץ סופי מסדר גדול מ־1 יש עלה. * גרף הוא עץ אם״ם הוא קשיר מינימלי, כלומר הוא קשיר וכל השמטת צלע יוצרת תת־גרף לא קשיר. * גרף הוא עץ אם״ם הוא מקסימלי ללא מעגלים, כלומר הוא עץ וכל הוספת צלע יוצרת מעגל. * לכל גרף קשיר וסופי קיים עץ פורש. * '''משפט קיילי:''' יש <math>n^{n-2}</math> עצים מסומנים מסדר <math>n</math>. * '''משפט מטריצה–עץ/משפט עצים פורשים:''' כידוע, מינור <math>A[i,j]</math> של מטריצה <math>A</math> הוא המטריצה המתקבלת מהשמטת השורה ה־<math>i</math> והעמודה ה־<math>j</math>. נסמן <math>\hat A</math> כמינור המוחק את השורה והעמודה האחרונות. עתה יהי <math>G</math> גרף לא מכוון וסופי מסדר הגדול מ־1. מספר העצים הפורשים שלו שווה ל־<math>\det\!\left(\hat L_G\right)</math>. * '''בעיית הסוכן הנוסע:''' נתו גרף קשיר וסופי ורוצים למצוא את ההילוך הקצר ביותר העובר דרך כל קודקודי הגרף. הפתרון הכי יעיל לא ידוע, אבל יש פתרון הנותן הילוך שאורכו לכל היותר פי 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>G\cong H</math> אז הפרמטרים הבאים שווים: ** סדר: <math>|V(G)|=|V(H)|</math>. ** מידה: <math>|E(G)|=|E(H)|</math>. ** מספר רכיבי הקשירות: <math>K(G)=K(H)</math>. ** וקטור דרגות (וקטור דרגות של גרף הוא וקטור שרכיביו הם דרגות הקודקודים מסודרות בסדר יורד חלש). ** קוטר: <math>\operatorname{diameter}(G)=\operatorname{diameter}(H)</math>. * <math>G\cong H</math> אם״ם <math>\overline G\cong\overline H</math>. * <math>L(P_n)\cong P_{n-1},L(C_n)\cong C_n</math>. * הקובייה ה־<math>n</math> מימדית <math>K_2^{\times n}</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>\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>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>G</math> מתקיים <math>\delta(G)\le5</math>. * '''משפט קורטובסקי:''' גרף אינו מישורי אם״ם יש לו תת־גרף שאיזומורפי לחלוקה של <math>K_5</math> או של <math>K_{3,3}</math>. * גרף הוא חוץ־מישורי אם״ם אין לו מינור שאיזומורפי ל־<math>K_4</math> או ל־<math>K_{2,3}</math>. * '''השערת וגנר:''' כל תכונה היא מונוטונית אם״ם היא מוגדרת ע״י קבוצה סופית של מינורים אסורים, כלומר קיים מספר סופי של גרפים שאיזומורפים למינור כלשהו של <math>G</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_{N_n}(x)=x^n\ \and\ f_{K_n}(x)=(x)_n=\prod_{i=0}^{n-1}(x-i)\ \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>. * לכל גרף <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>f:A\to B</math> שידוך אז <math>\{(u,f(u)):\ u\in A\}</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>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>\operatorname{ex}(n,K_{n+1})=\frac{n^2}2\left(1-\frac1r\right)</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>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>\operatorname{tr}(A_G)</math> היא מספר הלולאות ב־<math>G</math>. * יהי <math>G</math> פשוט ולא מכוון. אזי <math>\operatorname{tr}\!\left(A_G^2\right)=2|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>\operatorname{tr}\!\left(A_G^t\right)</math> (כאשר שני הילוכים שמתחילים בנקודות שונות הם שונים גם אם הם עוברים על אותן נקודות). * אם <math>G,H</math> סופיים ולא מכוונים אז <math>\operatorname{spec}(G\times H)=\operatorname{spec}(G)+\operatorname{spec}(H)</math>. * אם <math>G</math> גרף <math>d</math>־רגולרי אז <math>d\in\operatorname{spec}(G)</math> וו״ע מתאימים הם <math>v_A=(I_A(v_i))_{i=1}^n</math> לכל רכיב קשירות <math>A\subseteq V(G)=\{v_i\}_{i=1}^n</math>. * יהא <math>G</math> סופי ולא מכוון. <math>G</math> דו־צדדי אם״ם מתקיים התנאי הבא: <math>\lambda</math> ע״ע של <math>A_G</math> מריבוי אלגברי <math>k</math> אם״ם <math>-\lambda</math> ע״ע מאותו ריבוי. * הלפלסיאנים של שני גרפים זהים אם״ם יש להם תתי־גרפים פורשים איזומורפיים. * הלפלסיאן של גרף לא מכוון הוא מטריצה סימטרית. * הלפלסיאן אינו מטריצה הפיכה. * אם <math>G</math> לא מכוון סופי אז <math>\operatorname{rank}(L_G)=|V(G)|-K(G)</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>\forall t\in\mathbb N_0:\ P_G(t)=\sum_{\lambda\in\operatorname{spec}(A_G)}\frac{\lambda^t}{d^tn}=\frac{\operatorname{tr}\!\left(A_G^t\right)}{d^tn}</math>.
תקציר:
לתשומת לבך: תורמים אחרים עשויים לערוך או אף להסיר את תרומתך ל־Math-Wiki. אם אינך רוצה שעבודתך תהיה זמינה לעריכה על־ידי אחרים, אין לפרסם אותה פה.
כמו־כן, שמירת העריכה משמעה הבטחה שכתבת את הטקסט הזה בעצמך, או העתקת אותו ממקור שאינו מוגן בזכויות יוצרים (אפשר לעיין בדף
Math-Wiki:זכויות יוצרים
לפרטים נוספים).
אין לעשות שימוש בחומר המוגן בזכויות יוצרים ללא רשות!
ביטול
עזרה בעריכה
(נפתח בחלון חדש)