גרף שלם – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ בוט מוסיף: uk:Повний граф |
הוספת קליקה על פי אנגלית |
||
שורה 2:
[[תמונה:the graph K5.jpeg|שמאל|ממוזער|250px|הגרף השלם <big><math>K_5</math></big>]]
ב[[תורת הגרפים]], '''גרף שלם''' (או "גרף מלא") <math>\ G=(V,E)</math> הוא גרף אשר כל שני צמתים <math>\ n_1,n_2\in V</math> בו מחוברים על ידי קשת. נהוג לסמן גרף שלם בעל <math>\ n</math> צמתים ב-<math>\ K_n</math>.
גרף שלם הוא ה'''[[קליקה]]''' (clique) של עצמו. קליקה בגרף לא מכוון היא תת-קבוצה של הקודקודים שבה כל שני קודקודים מחוברים בקשת.
בתורת [[סיבוכיות|הסיבוכיות]] הוכח שבעיית מציאת תת-גרף שלם מקסימלי בגרף נתון נכללת בקטגוריה [[NP-קשה]], והצגתה כ[[בעיית הכרעה]] ("האם קיים תת-גרף שלם מסדר הגדול מ-k?") היא בקטגוריה [[NP-שלמה]].
| |||