תורת גרפים

ד"ר יורם לוזון
שעות לימוד:סמסטר ב: 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 צבעים