הצגת המקור של הדף "גרף שלם"

{{נתוני גרף
| שם = גרף שלם
| מספר צמתים = <math>\textstyle n</math>
| תמונה = 5-simplex graph.svg
| כיתוב = הגרף השלם <math>K_6</math>
| מספר קשתות = <math>\textstyle\frac{n (n-1)}{2}</math>
| רדיוס = <math>\left.\begin{aligned}
\begin{matrix} n \leq 1 & ,0 \\ n > 1 & ,1 \end{matrix}
\end{aligned}\right\}
</math>
| אוטומורפיזם = ([[החבורה הסימטרית|''S'']]<sub>''n''</sub>) <math>n!</math>
| תכונות = [[גרף רגולרי|<math>(n-1)</math>-רגולרי]]{{ש}}
גרף רגולרי-חזק{{ש}}
גרף סימטרי{{ש}}
גרף טרנזיטיבי
| סימון = <math>K_n</math>
| מותן = <math>\left.\begin{aligned}
\begin{matrix} & n \le 2 & ,\infty\\ & n > 2 & ,3\end{matrix}
\end{aligned}\right\}
</math>
| מספר צבעי צומת = {{mvar|n}}
}}
ב[[תורת הגרפים]], '''גרף שלם''' (או "גרף מלא") <math>G=(V,E)</math> הוא גרף פשוט לא מכוון אשר כל שני צמתים <math>n_1,n_2\in V</math> בו מחוברים על ידי קשת. נהוג לסמן גרף שלם בעל <math>n</math> צמתים ב-<math>K_n</math>. גרף שלם מהווה דוגמה ל[[קוגרף]].

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

== תכונות ==
בגרף שלם בעל <math>n</math> צמתים ישנן <math>\frac{n(n-1)}{2} </math> קשתות (ראו [[מספר משולשי#הוכחה קומבינטורית|מספר משולשי: קומבינטוריקה]]) והוא [[גרף רגולרי]] מדרגה <math>{n-1} </math>. בגרף שלם [[גרף קשיר|רכיב הקשירות]] של הגרף הוא הגרף עצמו. בנוסף, הגרף המשלים של גרף שלם הוא גרף ריק.

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

ניתן לפרק גרף <math>K_n</math> ל-<math>{n}</math> עצים, <math>T_1,\dots,T_n</math>, כאשר כל העץ <math>T_i</math> כולל <math>{i} </math> צמתים.<ref>{{Cite journal|last1=Joos|first1=Felix|last2=Kim|first2=Jaehoon|last3=Kühn|first3=Daniela|last4=Osthus|first4=Deryk|date=2019-08-05|title=Optimal packings of bounded degree trees|journal=[[Journal of the European Mathematical Society]]|language=en|volume=21|issue=12|pages=3573–3647|doi=10.4171/JEMS/909|s2cid=119315954|issn=1435-9855|url=http://pure-oai.bham.ac.uk/ws/files/46469651/quasi_random_tree_packing_revised.pdf|access-date=2020-03-09|archive-date=2020-03-09|archive-url=https://web.archive.org/web/20200309181052/http://pure-oai.bham.ac.uk/ws/files/46469651/quasi_random_tree_packing_revised.pdf|url-status=live}}</ref>

מספר ה[[מסלול (תורת הגרפים)|מסלולים]] השונים בין שני צמתים מסוימים ב <math>K_{n+2}</math> נתון על ידי 
<math> w_{n+2} = n! e_n = \lfloor en!\rfloor</math> ,
כאשר <math>e</math> הוא [[e (קבוע מתמטי)|קבוע אוילר]] ו 
<math>e_n = \sum_{k=0}^n\frac{1}{k!}</math> .

מספר ה[[שידוך (תורת הגרפים)|זיווגים]] בגרף שלם <math>K_n</math>, הידוע גם כ"מספרי טלפון"{{אנ|Telephone number (mathematics)}}, הוא <ref>{{citation|title=A combinatorial survey of identities for the double factorial|first=David|last=Callan|arxiv=0906.1317|year=2009|bibcode=2009arXiv0906.1317C}}.</ref>
<math display=block>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!}.</math>

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

== גאומטריה וטופולוגיה ==
גרף שלם עם <math>{n}</math> צמתים מייצג את הקודקודים של [[סימפלקס]] ממימד <math>{n-1}</math>. מבחינה גאומטרית, <math>K_3</math> יוצר את קבוצת הקודקודים של [[משולש]], <math>K_4</math> יוצר [[ארבעון]] וכו'.

הגרפים <math>K_1</math> עד <math>K_4</math> הם [[גרף מישורי|גרפים מישוריים]], אבל הגרף השלם <math>K_5</math> הוא אחד משני הגרפים היחידים שאינם [[גרף מישורי|מישוריים]]{{הערה|כל גרף המכיל אותם גם הוא אינו מישורי, כמובן. ראה להלן.}}. הגרף השני הוא <math>K_{3,3}</math> – הגרף הדו צדדי המלא בעל 3 צמתים בכל צד. [[משפט קורטובסקי]] קובע שגרף מישורי [[אם ורק אם]] אינו כולל תת-גרף שהוא חלוקה של <math>K_5</math> או <math>K_{3,3}</math>.

==דוגמאות==
גרפים שלמים בעלי <math>n</math> צמתים, עבור <math>n</math> בין 1 ל-12, מוצגים להלן ביחד עם מספר הקשתות:
{|class="wikitable"
! {{math|''K''<sub>1</sub>: 0}}
! {{math|''K''<sub>2</sub>: 1}}
! {{math|''K''<sub>3</sub>: 3}}
! {{math|''K''<sub>4</sub>: 6}}
|-
| [[קובץ:Complete graph K1.svg|140px]]
| [[קובץ:Complete graph K2.svg|140px]]
| [[קובץ:Complete graph K3.svg|140px]]
| [[קובץ:3-simplex graph.svg|140px]]
|-
! {{math|''K''<sub>5</sub>: 10}}
! {{math|''K''<sub>6</sub>: 15}}
! {{math|''K''<sub>7</sub>: 21}}
! {{math|''K''<sub>8</sub>: 28}}
|-
| [[קובץ:4-simplex graph.svg|140px]]
| [[קובץ:5-simplex graph.svg|140px]]
| [[קובץ:6-simplex graph.svg|140px]]
| [[קובץ:7-simplex graph.svg|140px]]
|-
! {{math|''K''<sub>9</sub>: 36}}
! {{math|''K''<sub>10</sub>: 45}}
! {{math|''K''<sub>11</sub>: 55}}
! {{math|''K''<sub>12</sub>: 66}}
|-
| [[קובץ:8-simplex graph.svg|140px]]
| [[קובץ:9-simplex graph.svg|140px]]
| [[קובץ:10-simplex graph.svg|140px]]
| [[קובץ:11-simplex graph.svg|140px]]
|}

== ראו גם ==
* [[קוד פרופר]]

{{תורת הגרפים}}
==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* {{MathWorld}}

==הערות שוליים==
{{הערות שוליים}}

{{בקרת זהויות}}