גרף שלם – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
אין תקציר עריכה |
||
שורה 5:
גרף שלם הוא ה'''קליקה''' (clique) של עצמו. קליקה בגרף לא מכוון היא תת-קבוצה של הקודקודים שבה כל שני קודקודים מחוברים בקשת.
בגרף שלם בעל n קודקודים ישנן n(n − 1)/2 קשתות (ראו [[מספר משולשי#הוכחה קומבינטורית|מספר משולשי: קומבינטוריקה]]).
ב[[תורת הסיבוכיות]] הוכח שבעיית מציאת תת-גרף שלם מקסימלי בגרף נתון נכללת בקטגוריה [[NP-קשה]], והצגתה כ[[בעיית הכרעה]] ("האם קיים תת-גרף שלם מסדר הגדול מ-k?") היא בקטגוריה [[NP-שלמה]].
| |||