גרף שלם

גרף שלם

הגרף השלם ${\displaystyle K_{6}}$
מספר צמתים	${\displaystyle \textstyle n}$
מספר קשתות	${\displaystyle \textstyle {\frac {n(n-1)}{2}}}$
רדיוס	${\displaystyle \left.{\begin{aligned}{\begin{matrix}n\leq 1&,0\\n>1&,1\end{matrix}}\end{aligned}}\right\}}$
מותן	${\displaystyle \left.{\begin{aligned}{\begin{matrix}&n\leq 2&,\infty \\&n>2&,3\end{matrix}}\end{aligned}}\right\}}$
אוטומורפיזם	(Sn) ${\displaystyle n!}$
מספר צבעי צומת	n
תכונות	${\displaystyle (n-1)}$-רגולרי גרף רגולרי-חזק גרף סימטרי גרף טרנזיטיבי
סימון	${\displaystyle K_{n}}$

בתורת הגרפים, גרף שלם (או "גרף מלא") ${\displaystyle G=(V,E)}$ הוא גרף פשוט לא מכוון אשר כל שני צמתים ${\displaystyle n_{1},n_{2}\in V}$ בו מחוברים על ידי קשת. נהוג לסמן גרף שלם בעל ${\displaystyle n}$ צמתים ב-${\displaystyle K_{n}}$. גרף שלם מהווה דוגמה לקוגרף.

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

תכונות

בגרף שלם בעל ${\displaystyle n}$ צמתים ישנן ${\displaystyle {\frac {n(n-1)}{2}}}$ קשתות (ראו מספר משולשי: קומבינטוריקה) והוא גרף רגולרי מדרגה ${\displaystyle {n-1}}$. בגרף שלם רכיב הקשירות של הגרף הוא הגרף עצמו. בנוסף, הגרף המשלים של גרף שלם הוא גרף ריק.

אם כל אחד מקשתות הגרף תקבל כיוון, הגרף שיתקבל יקרא גרף תחרות.

ניתן לפרק גרף ${\displaystyle K_{n}}$ ל-${\displaystyle {n}}$ עצים, ${\displaystyle T_{1},\dots ,T_{n}}$, כאשר כל העץ ${\displaystyle T_{i}}$ כולל ${\displaystyle {i}}$ צמתים.^[1]

מספר המסלולים השונים בין שני צמתים מסוימים ב ${\displaystyle K_{n+2}}$ נתון על ידי ${\displaystyle w_{n+2}=n!e_{n}=\lfloor en!\rfloor }$ , כאשר ${\displaystyle e}$ הוא קבוע אוילר ו ${\displaystyle e_{n}=\sum _{k=0}^{n}{\frac {1}{k!}}}$ .

מספר הזיווגים בגרף שלם ${\displaystyle K_{n}}$, הידוע גם כ"מספרי טלפון"(אנ'), הוא ^[2] $${\displaystyle T(n)=\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n}{2k}}(2k-1)!!=\sum _{k=0}^{\lfloor n/2\rfloor }{\frac {n!}{2^{k}(n-2k)!k!}}.}$$

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

גאומטריה וטופולוגיה

גרף שלם עם ${\displaystyle {n}}$ צמתים מייצג את הקודקודים של סימפלקס ממימד ${\displaystyle {n-1}}$. מבחינה גאומטרית, ${\displaystyle K_{3}}$ יוצר את קבוצת הקודקודים של משולש, ${\displaystyle K_{4}}$ יוצר ארבעון וכו'.

הגרפים ${\displaystyle K_{1}}$ עד ${\displaystyle K_{4}}$ הם גרפים מישוריים, אבל הגרף השלם ${\displaystyle K_{5}}$ הוא אחד משני הגרפים היחידים שאינם מישוריים^[3]. הגרף השני הוא ${\displaystyle K_{3,3}}$ – הגרף הדו צדדי המלא בעל 3 צמתים בכל צד. משפט קורטובסקי קובע שגרף מישורי אם ורק אם אינו כולל תת-גרף שהוא חלוקה של ${\displaystyle K_{5}}$ או ${\displaystyle K_{3,3}}$.

דוגמאות

גרפים שלמים בעלי ${\displaystyle n}$ צמתים, עבור ${\displaystyle n}$ בין 1 ל-12, מוצגים להלן ביחד עם מספר הקשתות:

K1: 0	K2: 1	K3: 3	K4: 6
K5: 10	K6: 15	K7: 21	K8: 28
K9: 36	K10: 45	K11: 55	K12: 66

ראו גם

• קוד פרופר

קישורים חיצוניים

מדיה וקבצים בנושא גרף שלם בוויקישיתוף

• גרף שלם, באתר MathWorld (באנגלית)

הערות שוליים

1. Joos, Felix; Kim, Jaehoon; Kühn, Daniela; Osthus, Deryk (2019-08-05). "Optimal packings of bounded degree trees" (PDF). Journal of the European Mathematical Society (באנגלית). 21 (12): 3573–3647. doi:10.4171/JEMS/909. ISSN 1435-9855. S2CID 119315954. ארכיון (PDF) מ-2020-03-09. נבדק ב-2020-03-09.
2. Callan, David (2009), A combinatorial survey of identities for the double factorial, arXiv:0906.1317, Bibcode:2009arXiv0906.1317C.
3. כל גרף המכיל אותם גם הוא אינו מישורי, כמובן. ראה להלן.