מטריצת שכנות

דוגמה למטריצת שכנות של גרף לא מכוון

מטריצת שכנוּ‏ת (גם מטריצת סמיכויות או מטריצת שכנויות) היא שיטה לייצוג גרף מכוון בעל $n$ צמתים בעזרת מטריצה ריבועית בגודל $n\times n$, שערכי תאיה הם 0 או 1. תא (i,j) בגרף מתאר את קיומה (או העדרה) של הקשת המכוונת מקודקוד i לקודקוד j בגרף. אם אין קשת כזו, הערך בתא במטריצה יהיה 0. אם יש קודקוד כזה, אזי הערך יהיה 1. פעמים רבות דנים בתורת הגרפים בגרפים פשוטים;

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

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

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

בגרפים שאינם פשוטים, ייתכנו מספר קשתות מקבילות בין אותו זוג צמתים. במקרה זה, ניתן לבנות מטריצת שכנויות שערך התא במטריצה יהיה מספר הקשתות מ-i ל-j.

תכונות

לייצוג גרף בשיטה זו יש יתרונות רבים:

1. הוספה/מחיקת קשת מתבצעת בגישה מיידית, בסיבוכיות זמן של $\ O(1)$‏.
2. ניתן לחשב את הגרף המשלים בקלות על ידי חיסור של מטריצת השכנות ממטריצת שכנות של גרף שלם. כך, בכל מקום שהיה בו קשת, כלומר ערך 1, יהיה 0 ובכל מקום שהיה בו 0, יהיה 1.
3. סיבוכיות מקום קטנה יחסית לשמירת המטרציה בזיכרון, $\ \Theta (|V|^{2})$ סיביות.

יחד עם זאת, אלגוריתמים בסיסיים רבים (כמו DFS, BFS, מיון טופולוגי וכו') רצים בזמן $\ O(|V|+|E|)$ כאשר $\ |V|$ מסמן את מספר הקודקודים ו-$\ |E|$ את מספר הקשתות. בשימוש במטריצת שכנות, הסיבוכיות היא לכל הפחות כגודל המטריצה, כלומר $\ O(|V|^{2})$.