גרף שלם

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

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

בגרף שלם בעל $n$ קודקודים ישנן ${\frac {n(n-1)}{2}}$ קשתות (ראו מספר משולשי: קומבינטוריקה).

הגרף השלם $K_{5}$ הוא אחד משני הגרפים היחידים שאינם מישוריים. הגרף השני הוא $K_{3,3}$ - הגרף הדו צדדי המלא בעל 3 צמתים בכל צד.

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

ראו גם

• קוד פרופר

קישורים חיצוניים

ראו מדיה וקבצים בנושא זה בוויקישיתוף.

• גרף שלם, באתר MathWorld (באנגלית)   

הערות שוליים

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0