פא"ר > החטיבה למתמטיקה > תורת הגרפים
שלום אורח  הרשם לפא"ר
תורת הגרפים - 20295
מרכז/ת ההוראה: ד"ר עופר הדס

4 נקודות זכות ברמה רגילה

שיוך: מדעים / מתמטיקה

ידע קודם דרוש: הקורס אלגברה לינארית 1 דרושה בשלות מתמטית הנקנית על-ידי צבירה של לפחות 24 נקודות זכות במתמטיקה. דרושה יכולת קריאה של טקסטים מדעיים באנגלית. מומלץ ידע בסיסי בקומבינטוריקה שאפשר לרכוש מתוך הקורס מתמטיקה דיסקרטית: תורת הקבוצות, קומבינטוריקה ולוגיקה1 או מתוך אחד מהקורסים מבוא לסטטיסטיקה ולהסתברות לתלמידי מדעים, הסתברות לתלמידי מדעי המחשב, תורת ההסתברות.

פיתוח הקורס: פרופ' אברהם גינזבורג, ד"ר נור ארד, טלי עילם-צורף, ד"ר אירית הרטמן

תורת הגרפים היא תחום מתמטי בעל שימושים רבים בענפים שונים של המתמטיקה ושל מדעי המחשב. המושגים של תורה זו קלים להבנה אפילו למי שהשכלתו המתמטית מצומצמת; עם זאת, לימוד תורת הגרפים מצריך בשלות מתמטית ומידה לא מבוטלת של תחכום מתמטי.

הקורס מיועד בעיקר לסטודנטים למתמטיקה ולמדעי המחשב, אך יוכלו ליהנות ממנו גם סטודנטים מתאימים ממקצועות אחרים.

ספר הקורס (באנגלית)

J.A. Bondy & U.S.R. Murty, Graph Theory with Applications (North Holland, 1976).

הסטודנטים ילמדו את 11 הפרקים הראשונים של הספר, בעזרת מדריך למידה מפורט (בעברית).

הדגש בספר הוא על התאוריה המתמטית של תורת הגרפים, אך לצד המשפטים וההוכחות מוצגים בו גם יישומים מגוונים ואלגוריתמים שימושיים לעוסקים במדעי המחשב.

מדריך הלמידה מלווה את סעיפי הספר באופן צמוד. הוא מכיל תרגומים והסברים של רבים מהמושגים, המשפטים וההוכחות, וכן פתרונות לרוב השאלות (הרבות) שבספר הקורס.

פרקי הלימוד

פרק 1

גרפים ותת-גרפים

פרק 2

עצים

פרק 3

קשירות

פרק 4

מעגלי אוילר ומעגלי המילטון

פרק 5

זיווגים

פרק 6

צביעת קשתות

פרק 7

קבוצות בלתי תלויות וקליקות

פרק 8

צביעת קדקדים

פרק 9

גרפים מישוריים

פרק 10

גרפים מכוונים

פרק 11

רשתות

1 או הקורס מתמטיקה בדידה: תורת הקבוצות, קומבינטוריקה ותורת הגרפים (20476), שיילמד החל מסמסטר ב2011. או הקורס מתמטיקה בדידה: תורת הקבוצות, קומבינטוריקה ותורת הגרפים (20476), שיילמד החל מסמסטר ב2011.