גרף שלם – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ הסרת תבנית:בריטניקה בערכים כאשר היא רק דף הפניה. ראו שיחת תבנית:בריטניקה (תג) |
בנציון יעבץ (שיחה | תרומות) אין תקציר עריכה |
||
שורה 20:
בגרף שלם בעל <math>n</math> קודקודים ישנן <math>\frac{n(n-1)}{2} </math> קשתות (ראו [[מספר משולשי#הוכחה קומבינטורית|מספר משולשי: קומבינטוריקה]]).
הגרף השלם <math>K_5</math> הוא אחד משני הגרפים היחידים שאינם [[גרף מישורי|מישוריים]]{{הערה|כל גרף המכיל אותם גם הוא אינו מישורי, כמובן}}. הגרף השני הוא <math>K_{3,3}</math> - הגרף הדו צדדי המלא בעל 3 צמתים בכל צד.
ב[[תורת הסיבוכיות]] הוכח שבעיית מציאת תת-גרף שלם הגדול ביותר בגרף נתון נכללת בקטגוריה [[NP-קשה]], והצגתה כ[[בעיית הכרעה]] ("האם קיים תת-גרף שלם מסדר הגדול מ-k?") היא בקטגוריה [[NP-שלמה]]. חיפוש של קליקה שקול לחיפוש של [[קבוצה בלתי תלויה (תורת הגרפים)|קבוצה בלתי תלויה]] (קבוצת צמתים אשר אין זוג מהם המחוברים בקשת) בגרף המשלים (שקבוצת הקשתות שלו [[משלים (מתמטיקה)|משלימה]] את קבוצת הקשתות של הגרף הנתון). לכן האלגוריתמים הידועים לשתי הבעיות הם בעלי סיבוכיות זהה וכן תוצאות הקושי לקירוב.
| |||