ברוכים הבאים לשיעור בנושא "צביעת גרפים ומישוריות", יחידה מרכזית בקורס "מתמטיקה בדידה". יחידה זו עוסקת בשני תחומים יסודיים בתורת הגרפים: צביעת קודקודים (או קשתות/פאות) של גרפים, ובחינת היכולת של גרפים להיטמע במישור ללא חיתוכי קשתות. נלמד את המושגים המרכזיים, משפטים חשובים, וכלים מעשיים לפתרון בעיות, תוך שימת דגש על נקודות קריטיות לבחינה.
צביעת גרפים: יסודות ומושגים מרכזיים
צביעת גרפים היא דרך להקצות "צבעים" לאלמנטים בגרף (לרוב קודקודים) תחת אילוצים מסוימים. המטרה הנפוצה ביותר היא למצוא את המספר המינימלי של צבעים הדרוש.
צביעת קודקודים: הקצאת צבע לכל קודקוד בגרף כך שלשני קודקודים סמוכים (המחוברים בקשת) יהיו צבעים שונים.
מספר כרומטי (χ(G)): המספר המינימלי של צבעים הדרוש לצביעת קודקודי גרף G.
אלגוריתמים ומשפטים חשובים
- צביעה חמדנית: אלגוריתם פשוט שבו עוברים על הקודקודים בסדר כלשהו ומקצים לכל קודקוד את הצבע הנמוך ביותר האפשרי שאינו בשימוש על ידי שכניו שכבר נצבעו. חשוב לזכור שצביעה חמדנית אינה מבטיחה תמיד את המספר הכרומטי המינימלי, שכן סדר הקודקודים משפיע על התוצאה.
- גרפים דו-צדדיים: גרף הוא דו-צדדי אם ורק אם הוא 2-צביע (כלומר, המספר הכרומטי שלו הוא 1 או 2). ניתן לחלק את קודקודיו לשתי קבוצות, A ו-B, כך שכל קשת מחברת קודקוד מ-A לקודקוד מ-B.
- משפט ארבעת הצבעים: כל גרף מישורי ניתן לצבוע בארבעה צבעים לכל היותר. זהו משפט בעל חשיבות היסטורית ותיאורטית רבה, וחשוב לזכור את ניסוחו והשלכותיו.
מישוריות גרפים: הגדרה, תכונות וזיהוי
מישוריות עוסקת בשאלה האם ניתן לצייר גרף במישור דו-ממדי ללא חיתוכי קשתות.
גרף מישורי: גרף שניתן לצייר במישור כך שאף שתי קשתות לא יחתכו זו את זו, למעט בקודקודים משותפים.
הטלה מישורית: דרך ספציפית לצייר גרף מישורי במישור ללא חיתוכי קשתות. הטלה כזו מחלקת את המישור לאזורים הנקראים פאות.
תכונות וכלים לזיהוי
- פאות: האזורים המוגבלים (או הלא מוגבלים) במישור הנוצרים על ידי הטלה מישורית של גרף.
- נוסחת אוילר: עבור גרף קשיר מישורי G עם v קודקודים, e קשתות ו-f פאות, מתקיים: v - e + f = 2. נוסחה זו היא כלי חיוני להוכחת אי-מישוריות של גרפים, שכן היא מציבה מגבלות על מספר הקשתות האפשרי. למשל, עבור גרף מישורי פשוט וקשיר עם v ≥ 3, מתקיים e ≤ 3v - 6.
K_5
הגרף השלם עם 5 קודקודים. כל זוג קודקודים מחובר בקשת. K_5 אינו מישורי והוא אחד משני הגרפים ה"אסורים" המינימליים.
K_{3,3}
הגרף הדו-צדדי השלם עם 3 קודקודים בכל צד. כל קודקוד מצד אחד מחובר לכל קודקוד מצד שני. K_{3,3} אינו מישורי והוא הגרף ה"אסור" המינימלי השני.
משפט קורטובסקי: הכלי האולטימטיבי לזיהוי אי-מישוריות
משפט קורטובסקי מספק אפיון מלא לגרפים מישוריים, ומאפשר להוכיח שגרף אינו מישורי על ידי מציאת תת-גרף מסוים.
חלוקה (Subdivision): גרף המתקבל מגרף אחר על ידי הוספת קודקודים בתוך קשתות (כלומר, החלפת קשת בדרך המורכבת מקודקודים חדשים וקשתות חדשות).
משפט קורטובסקי: גרף הוא מישורי אם ורק אם הוא אינו מכיל תת-גרף שהוא חלוקה של K_5 או חלוקה של K_{3,3}.
משפט קורטובסקי: זהו כלי קריטי ונושא אהוב במבחנים. הבנה עמוקה של המשפט ויכולת לזהות חלוקות של K_5 או K_{3,3} בגרף נתון היא חיונית להוכחת אי-מישוריות. תרגול זיהוי תת-גרפים אלו הוא מפתח להצלחה.
שאלות לדיון
- הסבר מדוע גרף דו-צדדי הוא תמיד 2-צביע, והאם ההפך נכון. נמק.
- נתון גרף G קשיר עם 8 קודקודים ו-20 קשתות. האם G יכול להיות מישורי? נמק באמצעות נוסחת אוילר.
- תאר את משפט קורטובסקי והסבר כיצד הוא מאפשר להוכיח שגרף נתון אינו מישורי. תן דוגמה קצרה לזיהוי חלוקה של K_5.
- כיצד צביעה חמדנית עובדת, ומדוע היא לא מבטיחה תמיד את המספר הכרומטי המינימלי?
נקודות לתשובת מודל
- גרף דו-צדדי ו-2-צביעות: גרף דו-צדדי ניתן לחלוקה לשתי קבוצות קודקודים A ו-B כך שכל קשת מחברת קודקוד מ-A לקודקוד מ-B. ניתן לצבוע את כל הקודקודים ב-A בצבע 1 ואת כל הקודקודים ב-B בצבע 2. מכיוון שאין קשתות בתוך A או בתוך B, אין קודקודים סמוכים עם אותו צבע. לכן, הוא 2-צביע. ההפך נכון: אם גרף הוא 2-צביע, ניתן לחלק את קודקודיו לשתי קבוצות לפי צבעיהם, ואין קשתות בתוך קבוצת צבעים אחת, ולכן הוא דו-צדדי.
- מישוריות ונוסחת אוילר: עבור גרף מישורי פשוט וקשיר עם v ≥ 3 קודקודים ו-e קשתות, מתקיים e ≤ 3v - 6. בגרף הנתון: v=8, e=20. נבדוק: 20 ≤ 3*8 - 6 = 24 - 6 = 18. מכיוון ש-20 > 18, הגרף אינו יכול להיות מישורי.
- משפט קורטובסקי: גרף הוא מישורי אם ורק אם הוא אינו מכיל תת-גרף שהוא חלוקה של K_5 או חלוקה של K_{3,3}. כדי להוכיח שגרף אינו מישורי, יש למצוא בתוכו תת-גרף שניתן לכווץ (על ידי הסרת קודקודים מדרגה 2) ל-K_5 או ל-K_{3,3}. דוגמה לזיהוי חלוקה של K_5: אם יש בגרף 5 קודקודים (נקרא להם "קודקודי ליבה") שכל זוג מהם מחובר על ידי דרך (שקודקומי הביניים שלה אינם קודקודי ליבה אחרים), אזי הגרף מכיל חלוקה של K_5.
- צביעה חמדנית: האלגוריתם עובד על ידי מעבר על הקודקודים בסדר כלשהו והקצאת הצבע הנמוך ביותר האפשרי (לרוב מספר שלם חיובי) לכל קודקוד, בהתחשב בצבעים של שכניו שכבר נצבעו. היא לא מבטיחה את המספר הכרומטי המינימלי כי בחירת הצבע לקודקוד מסוים עלולה "לתפוס" צבע שיכול היה להיות אופטימלי יותר עבור קודקודים עתידיים, וזאת ללא ראייה גלובלית של הגרף. סדר הקודקודים משפיע באופן דרמטי על מספר הצבעים הסופי.
מצאתם טעות או שחסר משהו?