גרף שלם

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Disambig RTL.svg המונח "קליקה" מפנה לכאן. לערך העוסק בתופעה חברתית, ראו קליקה (חברה).
הגרף השלם K_6

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

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

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

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

ראו גם[עריכת קוד מקור | עריכה]

P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.