גרף שלם

הגרף השלם $K_6$

בתורת הגרפים, גרף שלם (או "גרף מלא") $G=(V,E)$ הוא גרף אשר כל שני צמתים $n_1,n_2\in V$ בו מחוברים על ידי קשת. נהוג לסמן גרף שלם בעל $n$ צמתים ב-$K_n$.

גרף שלם הוא הקליקה (clique) של עצמו. קליקה בגרף לא מכוון היא תת-קבוצה של הקודקודים שבה כל שני קודקודים מחוברים בקשת.

בגרף שלם בעל n קודקודים ישנן n(n − 1)/2 קשתות (ראו מספר משולשי: קומבינטוריקה).

בתורת הסיבוכיות הוכח שבעיית מציאת תת-גרף שלם הגדול ביותר בגרף נתון נכללת בקטגוריה NP-קשה, והצגתה כבעיית הכרעה ("האם קיים תת-גרף שלם מסדר הגדול מ-k?") היא בקטגוריה NP-שלמה. חיפוש של קליקה שקול לחיפוש של קבוצה בלתי תלויה (קבוצת צמתים אשר אין זוג מהם המחוברים בקשת) בגרף המשלים (שקבוצת הקשתות שלו משלימה את קבוצת הקשתות של הגרף הנתון). לכן האלגוריתמים הידועים לשתי הבעיות הם בעלי סיבוכיות זהה וכן תוצאות הקושי לקירוב.

ראו גם

• קוד פרופר

ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום למכלול ולהרחיב אותו.