צביעת מפות (תורת הגרפים)

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