גרף n-צביע

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

חסמים על מספר הצביעה[עריכת קוד מקור | עריכה]

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

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

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

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

הפולינום הכרומטי[עריכת קוד מקור | עריכה]

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

ראו גם[עריכת קוד מקור | עריכה]


קישורים חיצוניים[עריכת קוד מקור | עריכה]

ויקישיתוף מדיה וקבצים בנושא גרף n-צביע בוויקישיתוף
P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.