תורת גרפים

ד"ר יורם לוזון
שעות לימוד:סמסטר ב: 3
סמסטר ב,יום א: 13:00 - 16:00, בניין מ.ישראל502- חדר 28

מבוסס על הקורס של נוגה אלון ועל הספר של Bondy וMurty

 

Chap1.pdf

Graphs and subgraphs, degrees and applications including Sperner's Lemma and Brouwer's fixed point theorem.

5.3.2006

I

Chap2.pdf

Trees, bridges, cut-vertices, Kirchoff's Theorem.

12.3.2006

II

chap3.pdf

Chirk.pdf

Some algorithms from Class I and II and Connectivity and edge connectivity, blocks, Whitney's Theorem, Eulerian Graphs.

19.3.2006

III

chap4.pdf

Hamiltonian graphs, Dirac's Theorem and its extensions, Ore's Theorem.

26.3.2006

IV

 

Continuation from previous weeks.

3.4.2006

V

chap6.pdf,

Edge coloring

23.4.2006

VI

, chap7.pdf

chap5.pdf

Matchings, Coverings and Cliques

30.4.2006

VII

chap8.pdf

Vertex coloring

7.5.2006

VIII

chap9.pdf

Planar Graphs

14.5.2006

IX

chap10.pdf

Directed Graphs

21.5.2006

X

 

 

28.5.2006

XI

 

 

 

XII

List of exercises

1.2.9  1.2.10  1.3.1  1.5.1  1.5.4   1.6.8   1.6.14   1.7.6

2.1.5  2.1.7  2.2.6  2.3.2

3.1.1 3.2.1

4.2.1 4.2.15

5.1.4 5.2.5

6.1.1 6.1.6

7.1.1 7.1.2 7.1.3

8.1.8  8.1.7  8.1.10

9.1.2  9.2.1   9.3.2

 

List of theorems

 

1.      גרף הוא דו-חלקי אם ורק אם כל המעגלים שלו הם מאורך זוגי

2.      ספנסר: קיים מספר אי זוגי של משולשי 0,1,2

3.      בעץ, כל שני צמתים מחוברים במסילה אחת ויחידה

4.      הורדה של קשת אחת בעץ מעלה את מס' רכיבי הקשירות לכל היותר ב-1.

5.      קשת היא קשת חותכת אם ורק אם היא לא מוכלת בשום מעגל

6.      כל גרף קשיר מכיל עץ פורש

7.      אם T הוא עץ פורש של G ו- e קשת בעץ, אזי הגרף T+e מכיל מעגל אחד ויחיד

8.      V הוא קודקוד חותך בעץ אם ורק אם d(v)>1

9.      אם G קשיר, מספר הקודקודים גדול שווה ל-3, וקיימת לו קשת חותכת, אזי קיים לו קודקוד חותך

10. 

11.  נוסחת קיילי: 

12.  האלגוריתם של Kruskal

13. 

14.  לגרף עם לפחות 3 קודקודים, יש קישוריות של 2 או יותר אם ורק אם כל 2 קודקודים בגרף מחוברים ע"י 2 מסלולים נפרדים (כל 2 קודקודים הם חלק מאותו מעגל)

15.  מעגל הוא אוילריאן אם ורק אם הדרגה של כל הקודקודים זוגית.

16.  במעגל, הורדת X קודקודים יוצרת לכל היותר X רכיבי קשירות

17.  אם G המילטוניאן,  אזי לכל   - 

18.  אם G פשוט, , וכן  אזי G הוא המילטוניאן

19.  האלגוריתם של Fleury יוצר מעגל אוילר

20.  אם אין שום ערך  שמקיים: ,    אזי G המילטוני

21.  אם G הוא גרף קשיר שאינו מעגל אי-זוגי, אזי קיימת צביעה עם 2 צבעים בה בכל קודקוד עם דרגה לפחות 2 - מיוצגים 2 הצבעים

22.  אם G הוא גרף דו-צדדי, אזי

23.  משפט Vising: אם G גרף פשוט, אזי:  או  - משפט בלתי אפשרי !

24.  שידוך הוא מקסימלי ב-G אם ורק אם לא קיים ל-M מסלול מוסיף

25.  משפט Hall: אם G הוא גרף דו-חלקי, קיים ל-x שידוך שבו כל הקודקודים של  x  רווים אם ורק אם  לכל

26.  אם G גרף דו-חלקי והדרגה של כל קודקוד היא K, קיים שידוך בו כל הקודקודים רוויים.

27.  בגרף דו חלקי -

28.  S הוא סט בלתי תלוי אם ורק אם  V\S הוא כיסוי קודקודים.

29.  גודל הסט הבלתי תלוי הגדול ביותר + גודל הכיסוי הקטן ביותר = מספר הקודקודים

30.  אם , אזי

31.  בגרף דו חלקי, אם , אזי גודל השידוך המקסימלי שווה לגודל כיסוי הקודקודים המינימלי.

32.  משפט Ramsey:  עבור  מתקיים: 

33.  בגרף קריטי: 

34.  אם גרף הוא  k-קריטי אזי 

35.  בגרף קריטי - אז חיתוך קודקודים הוא לא קליקה

36.  משפט DIRAC (גרף קריטי המכיל זוג קודקודים חותכים)

37.  אם G קשיר, פשוט, לא מעגל אי-זוגי, לא גרף שלם, אזי

38.  משפט DIRAC - הוכחת השערת HAJOS עבור k=4.

39.   הוא לא גרף מישורי

40.  משפט אוילר:  בגרף קשיר: 

41.  משפט 5 הצבעים:  ניתן לצבוע כל גרף מישורי ב-5 צבעים