גרף משלים

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

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

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