גרף n-צביע

מתוך המכלול, האנציקלופדיה היהודית
גרסה מ־01:09, 27 בפברואר 2017 מאת יוסף (שיחה | תרומות) (גרסה אחת יובאה)
קפיצה לניווט קפיצה לחיפוש

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

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

עבור , ההכרעה האם היא בעיה NP שלמה. לגרף יש מספר כרומטי 2 אם ורק אם הוא דו-צדדי, ותכונה זו ניתנת לזיהוי בזמן לינארי במספר הקשתות.

חסמים על מספר הצביעה

עבור גרף עם צמתים מקבלים טריוויאלית ש-.

אם מסמנים ב את הדרגה המקסימלית של צומת ב- אז . תוצאה זאת ניתן לשפר בצורה הבאה: אם עבור בכל תת-גרף מושרה של קיים צומת כך ש- אז . עבור תנאי זה נכון ולכן האי-שוויון גורר את החסם הקודם. עבור גרף שלם על n צמתים ו ועבור מעגל אי-זוגי ו ומכאן שאי אפשר לשפר את המשפט באופן כללי. אולם משפט ברוקס קובע כי לכל שאר הגרפים .

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

נסמן ב- את גודל תת-הקבוצה הבלתי תלויה הגדולה ביותר, אז .

הפולינום הכרומטי

מספר הדרכים לצבוע גרף נתון G ב- צבעים נתון על ידי הצבה של בפולינום , הקרוי הפולינום הכרומטי של הגרף. פולינום זה, שאותו גילה ג'ורג' בירקהוף ב-1912, מקיים את נוסחת הרקורסיה , לכל קשת e בגרף, כאשר G-e הוא הגרף ללא הקשת האמורה, ו-G/e הוא הגרף המתקבל מכיווץ הקשת לנקודה.

ראו גם


P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום למכלול ולהרחיב אותו.