הדפסה
גרסת PDF
סילבוס לקורס: תורת הגרפים, 42022.1.1
שם המרצה: בלאק שרה
סוג הקורס : שיעור
שנת הלימודים: תשפ"א ,   הקורס נלמד בסמסטר ב
מספר השעות ונקודות זכות: 1.5 ש"ש, 3 נ.ז.
שנת הלימוד בתכנית: ב,ג,ד
דרישות קדם: אין
מטרות / תוצרי למידה: מטרות

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


תוצרי למידה:

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

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

הסטודנטית תהיה מסוגלת להוכיח מתמטית או להפריך טענות הקשורות לתורת הגרפים.
תיאור הקורס: הקורס עוסקת בתורת הגרפים ומורכב מהפרקים הבאים: מושגים ראשוניים בגרפים, משפחות מיוחדות של גרפים, תכונות של מטריקה בגרף, איפיון של גרפים זוגיים ויישומים שונים, גרפים אוילריים, גרפים המילטוניים ויישומיהם, עצים, מישוריות.
התוכן הניתן מידי שבוע, מטלות וחומרי קריאה:
מס'נושא, מטלות וחומר קריאה
1 גרף, מולטיגרף, גרף מכוון, ערכויות בגרף, ערכיות מינימלית, ערכיות מקסימלית, גרף רגולרי, איזומרפיזם בין גרפים
2 הגרף השלם, הגרף הדיסקרטי, המשלים של גרף, מסילה, מעגל, מרכיבי קשירות, תת גרף, גרף זוגי, גרף זוגי שלם
3 משפט לחיצת הידיים, מרחק בגרף, מרחק הוא מטריקה, קוטר
4 איפיון גרף זוגי על ידי אורכי המעגלים בו, איפיון גרף זוגי על ידי אורכי המעגלים בו, גרף קריטי, משפט טורן
5 השערת Ulam, גרף אוילרי, גרף אוילרי למחצה, גשר בגרף, האלגוריתם של Fleury
6 חידות שחמט, שרטוט גרף במספר מינמלי של משיכות קולמוס, גרף ממושקל
בעיית הדוור הסיני
7 גרף המילטוני, גרף המילטוני למחצה, זיהוי גרפים לא המילטוניים, גרפים זוגיים המילטוניים
8 משפט Schwenk, משפט Dirac, איזכור של בעיית הסוכן הנוסע,
המילטוניות בגרפים מכוונים.
9 הקובייה Q_n ,המילטוניות הקובייה Q_n , זיווג מושלם
10 מספר המעגלים ההמילטוניים הזרים בצלעות ב- K_n ,יער, עץ ותכונותיו
תת גרף פורש, עץ פורש, האלגוריתם של Kruskal
11 נוסחת קיילי, אקסנטריות של קודקוד, רדיוס של גרף,
12 מרכז של גרף, נגזרת של עץ
13 גרפים מישוריים, משפט אוילר, משפט Kuratowski , משפט ארבעת הצבעים
חובות הסטודנט בקורס: הכנת תרגילי בית שבועיים המתבססים על פרקי הלימוד, כאשר מרכיב הציון בתרגילים הוא חלק מהציון המשוקלל בקורס, בחינת סיכום.
אופן ההערכה - הרכב הציון
מרכיבאחוזציון מינימלי למרכיב
תרגילים 30%
מבחן 70% 55
רשימה ביבליוגרפית:
Wilson J., (1996) Introduction to Graph Theory, 4th Ed. Essex: Addison-Wesley Longman
Biggs N., Algebraic Graph Theory, 2nd Ed. (1996) Cambridge: Cambridge University Press.

ליניאל נ', פרנס מ', (2005) מתמטיקה בדידה,מהדורה שנייה, תל אביב: נ' בן צבי
תורגמן א', (1997) תורת הגרפים ירושלים: אקדמון