גרף שלם
![]() | |
הגרף השלם | |
מספר צמתים | |
---|---|
מספר קשתות | |
רדיוס | |
אוטומורפיזם | (Sn) |
תכונות |
-רגולרי |
בתורת הגרפים, גרף שלם (או "גרף מלא") הוא גרף אשר כל שני צמתים בו מחוברים על ידי קשת. נהוג לסמן גרף שלם בעל צמתים ב-. גרף שלם מהווה דוגמה לקוגרף.
גרף שלם הוא הקליקה (clique) של עצמו. קליקה בגרף לא מכוון היא תת-קבוצה של הקודקודים שבה כל שני קודקודים מחוברים בקשת.
בגרף שלם בעל קודקודים ישנן קשתות (ראו מספר משולשי: קומבינטוריקה).
הגרף השלם הוא אחד משני הגרפים היחידים שאינם מישוריים[1]. הגרף השני הוא - הגרף הדו צדדי המלא בעל 3 צמתים בכל צד.
בתורת הסיבוכיות הוכח שבעיית מציאת תת-גרף שלם הגדול ביותר בגרף נתון נכללת בקטגוריה NP-קשה, והצגתה כבעיית הכרעה ("האם קיים תת-גרף שלם מסדר הגדול מ-k?") היא בקטגוריה NP-שלמה. חיפוש של קליקה שקול לחיפוש של קבוצה בלתי תלויה (קבוצת צמתים אשר אין זוג מהם המחוברים בקשת) בגרף המשלים (שקבוצת הקשתות שלו משלימה את קבוצת הקשתות של הגרף הנתון). לכן האלגוריתמים הידועים לשתי הבעיות הם בעלי סיבוכיות זהה וכן תוצאות הקושי לקירוב.
ראו גם
נושאים בתורת הגרפים | ||
---|---|---|
הגדרות | צומת • קשת • דרגה • מסלול • מרחק | |
מבנים | גרף • גרף ממושקל • מעגל • גרף מקרי • היפרגרף • מולטיגרף • עץ • קומפלקס | |
בניות וטיפוסים | גרף משלים • גרף קיילי • גרף שלם • גרף תחרות • גרף תשתית • עץ פורש • רשת זרימה • שידוך | |
תכונות | גרף n-צביע • גרף דו-צדדי • גרף מישורי • גרף מרחיב • גרף רגולרי • גרף קשיר • עץ בינומי • עץ פורש מינימלי |
קישורים חיצוניים
הערות שוליים
- ^ כל גרף המכיל אותם גם הוא אינו מישורי, כמובן