גרף משלים

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

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

שימושים

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

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

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

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

• {{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.