גרף שלם – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ Cat-a-lot: העברה מקטגוריה:ערכים בהם תבנית בריטניקה אינה מתאימה ל קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה שימוש בCat-a-lot |
נאמן מנחלי געש (שיחה | תרומות) הרחבה על בסיס המקור האנגלי |
||
שורה 13:
גרף רגולרי-חזק <br/>
גרף סימטרי
גרף טרנזיטיבי
| סימון = <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>K_5</math> הוא אחד משני הגרפים היחידים שאינם [[גרף מישורי|מישוריים]]{{הערה|כל גרף המכיל אותם גם הוא אינו מישורי, כמובן}}. הגרף השני הוא <math>K_{3,3}</math> - הגרף הדו צדדי המלא בעל 3 צמתים בכל צד.▼
ניתן לחלק גרף <math>\ K_n</math>ל-<math>{n} </math> עצים <math>\ T_i</math>כאשר כל <math>\ T_i</math>הוא הצומת <math>{i} </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}}
|-
| [[Image:Complete graph K1.svg|140px]]
| [[Image:Complete graph K2.svg|140px]]
| [[Image:Complete graph K3.svg|140px]]
| [[Image: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}}
|-
| [[Image:4-simplex graph.svg|140px]]
| [[Image:5-simplex graph.svg|140px]]
| [[Image:6-simplex graph.svg|140px]]
| [[Image: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}}
|-
| [[Image:8-simplex graph.svg|140px]]
| [[Image:9-simplex graph.svg|140px]]
| [[Image:10-simplex graph.svg|140px]]
| [[Image:11-simplex graph.svg|140px]]
|}
▲ב[[תורת הסיבוכיות]] הוכח שבעיית מציאת תת-גרף שלם הגדול ביותר בגרף נתון נכללת בקטגוריה [[NP-קשה]], והצגתה כ[[בעיית הכרעה]] ("האם קיים תת-גרף שלם מסדר הגדול מ-k?") היא בקטגוריה [[NP-שלמה]]. חיפוש של קליקה שקול לחיפוש של [[קבוצה בלתי תלויה (תורת הגרפים)|קבוצה בלתי תלויה]] (קבוצת צמתים אשר אין זוג מהם המחוברים בקשת) בגרף המשלים (שקבוצת הקשתות שלו [[משלים (מתמטיקה)|משלימה]] את קבוצת הקשתות של הגרף הנתון). לכן האלגוריתמים הידועים לשתי הבעיות הם בעלי סיבוכיות זהה וכן תוצאות הקושי לקירוב.
== ראו גם ==
| |||