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