גרף שלם

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

הגרף השלם $K_5$

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

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

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

ראו גם

• קוד פרופר

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