גרף n-צביע

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

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

עבור גרף \ G, מסמנים ב-\chi(G) = \min\{k \mid G \;is\; k \;\mbox{colorable}\} את המספר הקטן ביותר של צבעים הדרוש לצביעת הקודקודים שלו. מספר זה נקרא מספר הצביעה (או המספר הכרומטי) של הגרף.

עבור \ k>2, ההכרעה האם \ \chi(G)=k היא בעיה NP שלמה. לגרף יש מספר כרומטי 2 אם ורק אם הוא דו-צדדי, ותכונה זו ניתנת לזיהוי בזמן לינארי במספר הקשתות.

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

עבור גרף \ G עם \ n צמתים מקבלים טריוויאלית ש-1 \leq \chi(G) \leq n.

אם מסמנים ב \triangle(G) את הדרגה המקסימלית של צומת ב-\ G אז \chi(G)\leq \triangle(G)+1. תוצאה זאת ניתן לשפר בצורה הבאה: אם עבור k\in \mathbb{N} בכל תת-גרף מושרה \ H של \ G קיים צומת v\in H כך ש-d_H (v)\leq k אז \chi(G)\leq k+1. עבור k=\triangle(G) תנאי זה נכון ולכן האי-שוויון גורר את החסם הקודם. עבור גרף שלם על n צמתים \triangle(G)=n-1 ו \ \chi(G) = n ועבור מעגל אי-זוגי \triangle(G)=2 ו \ \chi(G) = 3 ומכאן שאי אפשר לשפר את המשפט באופן כללי. אולם משפט ברוקס קובע כי לכל שאר הגרפים \chi(G)\leq \triangle(G).

נסמן ב-\ \omega(G) את גודל הקליקה המקסימלית ב-\ G אז \ \chi(G)\geq \omega(G). אם אי-שוויון זה הדוק עבור הגרף ועבור כל אחד מתתי הגרפים המושרים שלו, אז הגרף נקרא גרף מושלם.

נסמן ב-\ \alpha(G) את גודל תת-הקבוצה הבלתי תלויה הגדולה ביותר, אז \ \chi(G)\geq \frac{n}{\alpha(G)}.

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

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

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

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