גרף n-צביע – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
|||
שורה 1:
ב[[תורת הגרפים]], '''גרף <math>\ n</math>-צביע'''
עבור גרף <math>\ G</math>, מסמנים ב-<math>\chi(G) = \min\{k \mid G \;is\; k \;\mbox{colorable}\}</math>
עבור <math>\ k>2</math>,
▲עבור גרף <math>\ G</math>, מסמנים ב-<math>\chi(G) = \min\{k \mid G \;is\; k \;\mbox{colorable}\}</math> - המספר הקטן ביותר של צבעים בעזרתם ניתן לצבוע את הגרף. מספר זה נקרא מספר הצביעה (המספר הכרומטי) של הגרף.
▲עבור <math>\ k>2</math> הבעיה של למצוא האם <math>\ \chi(G)=k</math> היא בעיה [[NP_(סיבוכיות)|NP שלמה]]. עבור <math>\ k=2</math> הבעיה היא האם הגרף הוא [[גרף דו צדדי|דו צדדי]] וניתנת לפתרון בזמן לינארי במספר הקשתות.
עבור
▲== חסמים למספר הצביעה ==
▲עבור כל גרף סופי לא ריק <math>\ G</math> עם <math>\ n</math> צמתים מקבלים טריוויאלית ש-<math>1 \leq \chi(G) \leq n</math>.
אם מסמנים ב <math>\triangle(G)</math> את הדרגה המקסימלית של צומת ב-<math>\ G</math> אז <math>\chi(G)\leq \triangle(G)+1</math>. תוצאה זאת ניתן לשפר בצורה הבאה: אם עבור <math>k\in \mathbb{N}</math> בכל תת-גרף מושרה <math>\ H</math> של <math>\ G</math> קיים צומת <math>v\in H</math> כך ש-<math>d_H (v)\leq k</math> אז <math>\chi(G)\leq k+1</math>. עבור <math>k=\triangle(G)</math> תנאי זה נכון ולכן האי-שוויון גורר את החסם הקודם. עבור [[גרף שלם]] על n צמתים <math>\triangle(G)=n-1</math> ו <math>\ \chi(G) = n</math> ועבור מעגל אי-זוגי <math>\triangle(G)=2</math> ו <math>\ \chi(G) = 3</math> ומכאן שאי אפשר לשפר את המשפט באופן כללי. אולם '''משפט ברוקס''' קובע כי לכל שאר הגרפים <math>\chi(G)\leq \triangle(G)</math>.
שורה 16 ⟵ 14:
נסמן ב-<math>\ \alpha(G)</math> את גודל תת-הקבוצה ה[[קבוצה בלתי תלויה (תורת הגרפים)|בלתי תלויה]] הגדולה ביותר, אז <math>\ \chi(G)\geq \frac{n}{\alpha(G)}</math>.
== הפולינום הכרומטי ==
מספר הדרכים לצבוע גרף נתון G ב-<math>\ \lambda</math> צבעים נתון על-ידי הצבה של <math>\ \lambda</math> בפולינום <math>\ \chi(G,\lambda)</math>, הקרוי [[הפולינום הכרומטי]] של הגרף. פולינום זה, שאותו גילה [[בירקהוף]] ב-[[1912]], מקיים את נוסחת הרקורסיה <math> \chi(G,\lambda) = \chi(G-e,\lambda) - \chi(G/e, \lambda)</math>, לכל קשת e בגרף, כאשר G-e הוא הגרף ללא הקשת האמורה, ו-G/e הוא הגרף המתקבל מכיווץ הקשת לנקודה.
==ראו גם==
| |||