גרף שלם

גרף שלם (גרף מלא) G=(V,E) הוא גרף פשוט לא מכוון שבו כל שני צמתים n1,n2 ∈ V מחוברים בקשת. נהוג לסמן גרף שלם בעל n צמתים ב-K_n. גרף שלם הוא גם דוגמה לקוגרף.

גרף שלם הוא ה=קליקה= של עצמו. קליקה היא תת‑קבוצה של צמתים שבה כל שני צמתים מחוברים בקשת.

בגרף שלם בעל n צמתים יש n(n-1)/2 קשתות. זהו גרף רגולרי מדרגה n-1, כלומר לכל צומת יש בדיוק n-1 שכנים. הגרף קשיר והגרף המשלים שלו הוא גרף ריק (אותן צמתים בלי קשתות). אם נותנים לכל קשת כיוון, מקבלים גרף תחרות (tournament) - גרף עם קשתות מכוונות.

ניתן לפרק את K_n ל-n עצים T_1,…,T_n כך שכל T_i כולל i צמתים. במספר מסלולים בין שני צמתים ב-K_{n+2} מופיע הביטוי w_{n+2} = n! e_n = ≬ en!, כאשר e הוא קבוע אוילר ו-e_n = \sum_{k=0}^n 1/k!. מספר הזיווגים (matchings) ב-K_n נתון על ידי
T(n)=\sum_{k=0}^{\lfloor n/2\rfloor} \frac{n!}{2^k (n-2k)! k!}.

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

הגרפים K_n מייצגים את קודקודי סימפלקס מממד n-1: K_3 הם קודקודי משולש, K_4 הם קודקודי ארבעון (טטרהדרון) וכו'. הגרפים K_1 עד K_4 הם מישוריים (ניתן לציירם בלי חציית קשתות). K_5 אינו מישורי, וכך גם K_{3,3}. משפט קורטובסקי אומר שגרף מישורי אם ורק אם הוא אינו מכיל תת-גרף שהוא חלוקה של K_5 או K_{3,3}.

ניתן להציב את K_n עבור n=1, 12 ולהראות את מספר הקשתות בכל אחד מהם.

גרף שלם (גרף מלא) הוא ציור של נקודות וקווים. נקודה = צומת. קו = קשת. בכל גרף כזה כל שתי נקודות מחוברות בקו. קוראים לגרף שלם עם n נקודות K_n.

אם יש n נקודות, יש n(n-1)/2 קווים. זה אומר שכל זוג נקודות מחובר בקו אחד. הגרף קשיר, כלומר אפשר להגיע מכל נקודה לכל נקודה בדרך של קווים. אם נותנים לכל קשת חץ, מקבלים גרף תחרות, כמו משחק שבו כל שני שחקנים נפגשים.

K_3 הם שלוש נקודות שיוצרות משולש. K_4 הם ארבע נקודות שמייצרות ארבעון קטן (טטרהדרון). אפשר לצייר K_1 עד K_4 בלי שהקווים יחצו זה את זה. K_5 כבר אי אפשר לצייר בלי חיתוכים. יש חוק (משפט קורטובסקי) שאומר שאם גרף מכיל K_5 או K_{3,3} בצורה מסוימת, אי אפשר לצייר אותו בלי חצייה.

K_1 עד K_4 פשוטים לציור. K_5 ו-K_{3,3} מראים מתי ציור בלי חצייה אינו אפשרי.