גרף שלם

המונח "קליקה" מפנה לכאן. לערך העוסק בתופעה חברתית, ראו קליקה (חברה).

הגרף השלם $K_6$

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

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

בגרף שלם בעל n קודקודים ישנן n(n − 1)/2 קשתות.

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

ראו גם

• קוד פרופר

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