גרף שלם

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש


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

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

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

הגרף השלם הוא אחד משני הגרפים היחידים שאינם מישוריים[1]. הגרף השני הוא - הגרף הדו צדדי המלא בעל 3 צמתים בכל צד.

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

ראו גם


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

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

  • גרף שלם, באתר MathWorld (באנגלית)   המזהה לא מולא ולא נמצא בוויקינתונים, נא למלא את הפרמטר.

הערות שוליים

  1. ^ כל גרף המכיל אותם גם הוא אינו מישורי, כמובן
P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום למכלול ולהרחיב אותו.
סמל המכלול גמרא 2.PNG
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0