גרף n-צביע – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
RimerMoshe (שיחה | תרומות) הקולג' האוניברסיטאי של לונדון ==> יוניברסיטי קולג' לונדון |
הוספת קישור למאמר שעל סיבוכיות זמן תגיות: עריכה ממכשיר נייד עריכה מיישום נייד עריכה מאפליקציית iOS |
||
שורה 3:
עבור גרף <math>\ G</math>, מסמנים ב-<math>\chi(G)</math> את המספר הקטן ביותר של צבעים הדרוש לצביעת הקודקודים שלו. מספר זה נקרא '''מספר הצביעה''' (או '''המספר הכרומטי''') של הגרף.
עבור <math>\ k>2</math>, ההכרעה האם <math>\ \chi(G)=k</math> היא בעיה [[NP_(סיבוכיות)|NP שלמה]]. לגרף יש מספר כרומטי 2 אם ורק אם הוא [[גרף דו-צדדי|דו-צדדי]], ותכונה זו ניתנת לזיהוי [[סיבוכיות זמן|בזמן ליניארי]] במספר הקשתות.
== היסטוריה ==
| |||