גרף משלים
בתורת הגרפים, גרף משלים של גרף פשוט נתון הוא הגרף הבנוי על אותם קודקודים, עם היפוך הקשתות: במקום שבו הייתה קשת בגרף המקורי אין קשת בגרף המשלים, ובמקום שבו לא הייתה קשת, יש בגרף המשלים קשת. אפשר להגדיר את הגרף המשלים גם עבור גרף מכוון.
אם מטריצת השכנות של הגרף הנתון היא A, אז המטריצה של הגרף המשלים היא J-A-Ι, כאשר J היא מטריצה שכל רכיביה 1 ו - Ι מטריצת יחידה.
שימושים
גרף מתאר קשרים בין הקודקודים שיכולים לייצג דברים רבים. גרף יכול לייצג אנשים והקשרים החברתיים ביניהם; נקודות על מפה והדרכים ביניהם; את רשת האינטרנט ועוד. לדוגמה, גרף שקודקודיו הם אנשים ויש קשת ביניהם אם הם חברים. גרף זה מתאר את יחס החברות בין האנשים. הגרף המשלים המתאים לגרף זה, אם כן, יתאר את יחס אי-החברות. כלומר, תהיה קשת בין כל שניים שאינם חברים.
לגרפים משלימים חשיבות באלגוריתמים, ברדוקציות בתחום הסיבוכיות, בתורת הגרפים ועוד.
קישורים חיצוניים
- Newman, Michael William (2000), The Laplacian Spectrum of Graphs (PDF), The University of Manitoba, ISBN 0-612-57564-0, page 17.
| נושאים בתורת הגרפים | ||
|---|---|---|
| הגדרות | צומת • קשת • דרגה • מסלול • מרחק | |
| מבנים | גרף • גרף ממושקל • מעגל • גרף מקרי • היפרגרף • מולטיגרף • עץ • קומפלקס | |
| בניות וטיפוסים | גרף משלים • גרף קיילי • גרף שלם • גרף תחרות • עץ פורש • רשת זרימה • שידוך | |
| תכונות | גרף n-צביע • גרף דו-צדדי • גרף מישורי • גרף מרחיב • גרף רגולרי • גרף קשיר • עץ בינומי • עץ פורש מינימלי | |
17253327גרף משלים