משלים של גרף

תרשים לדוגמה של משלים של גרף

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

אם מטריצת השכנות של הגרף הנתון היא A, אז המטריצה של הגרף המשלים היא J-A-Ι, כאשר J היא מטריצה שכל רכיביה 1 ו - Ι מטריצת יחידה.

הגדרה

יהי גרף G(V, E).תהי K קבוצת הקשתות של הגרף המלא $K_{n}$. הגרף המשלים $}{\overline {G}$ הוא עם קבוצת הצמתים V וקבוצת הקשתות K\E.

כלומר, הגרף המשלים הוא עם הקשתות ב- K ללא הקשתות ב-E.

שימושים

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

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

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

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

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

| last=Newman | first=Michael William
| title=The Laplacian Spectrum of Graphs
| year=2000
| publisher=The University of Manitoba
| isbn=0-612-57564-0
| url=http://www.seas.upenn.edu/~jadbabai/ESE680/Laplacian_Thesis.pdf

}}, page 17.