גרף שלם

מתוך ויקיפדיה, האנציקלופדיה החופשית
גרף שלם
הגרף השלם '"`UNIQ--postMath-00000002-QINU`"'
הגרף השלם
מספר צמתים
מספר קשתות
רדיוס
מותן
אוטומורפיזם (Sn)
מספר צבעי צומת n
תכונות

-רגולרי
גרף רגולרי-חזק
גרף סימטרי

גרף טרנזיטיבי
סימון

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

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

תכונות[עריכת קוד מקור | עריכה]

בגרף שלם בעל צמתים ישנן קשתות (ראו מספר משולשי: קומבינטוריקה) והוא גרף רגולרי מדרגה. בגרף שלם, רכיב הקשירות של הגרף הוא הגרף עצמו. בנוסף, הגרף המשלים של גרף שלם הוא גרף ריק.

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

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

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

גיאומטריה וטופולוגיה[עריכת קוד מקור | עריכה]

גרף שלם עם צמתים מייצג את הקודקודים של סימפלקס ממימד . מבחינה גיאומטרית, יוצר את קבוצת הקודקודים של משולש, יוצר ארבעון וכו'.

הגרפים עד הם גרפים מישוריים, אבל הגרף השלם הוא אחד משני הגרפים היחידים שאינם מישוריים[1]. הגרף השני הוא - הגרף הדו צדדי המלא בעל 3 צמתים בכל צד. משפט קורטובסקי קובע שגרף מישורי אם ורק אם אינו כולל תת-גרף שהוא חלוקה של או .

דוגמאות[עריכת קוד מקור | עריכה]

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

K1: 0 K2: 1 K3: 3 K4: 6
Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg 3-simplex graph.svg
K5: 10 K6: 15 K7: 21 K8: 28
4-simplex graph.svg 5-simplex graph.svg 6-simplex graph.svg 7-simplex graph.svg
K9: 36 K10: 45 K11: 55 K12: 66
8-simplex graph.svg 9-simplex graph.svg 10-simplex graph.svg 11-simplex graph.svg


ראו גם[עריכת קוד מקור | עריכה]


קישורים חיצוניים[עריכת קוד מקור | עריכה]

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

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ כל גרף המכיל אותם גם הוא אינו מישורי, כמובן. ראה להלן.
P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.