הצגת המקור של הדף "מטריצת שכנות"

[[קובץ:AdjacencyMatrix.png|250px|שמאל|ממוזער|דוגמה למטריצת שכנות של גרף לא מכוון]]
'''מטריצת שכנוּת''' (גם: '''מטריצת סמיכויות''' או '''מטריצת שכנויות''') היא שיטה לייצוג [[גרף מכוון]] בעל <math>n</math> צמתים בעזרת [[מטריצה ריבועית]] בגודל <math>n \times n</math>. לפי שיטה זו, תא (i,j) שווה 1 אם ורק אם בגרף קיימת קשת מקודקוד i לקודקוד j . אם אין קשת כזו, הערך בתא במטריצה יהיה 0. 

פעמים רבות דנים בתורת הגרפים [[גרף פשוט|בגרפים פשוטים]]{{דרושה הבהרה|למה התכוון המשורר?}}.

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

עבור גרף שבו אין [[תורת הגרפים|לולאות עצמיות]] (כלומר, קשת מקודקוד כלשהו לעצמו), [[אלכסון ראשי|האלכסון הראשי]] של מטריצת השכנויות המתאימה יהיה 0. <!-- לכן עבור כל תא מהצורה (i,i), ערך המספר בתא הוא 0. -->

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

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

== תכונות ==
לייצוג גרף בשיטה זו יש יתרונות רבים:
# הוספה/מחיקת קשת מתבצעת בגישה מיידית, ב[[סיבוכיות זמן]] של <math>\ O(1)</math>{{כ}}.
#ניתן לחשב את ה[[גרף משלים|גרף המשלים]] בקלות על ידי [[חיסור]] של מטריצת השכנות ממטריצת שכנות של גרף שלם. כך, בכל מקום שהיה בו קשת, כלומר ערך 1, יהיה 0 ובכל מקום שהיה בו 0, יהיה 1.
#[[סיבוכיות מקום]] קטנה יחסית לשמירת המטריצה בזיכרון, <math>\ \Theta(|V|^2)</math> סיביות.

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

==ראו גם==
*[[מטריצת לפלסיאן]]
==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* {{MathWorld}}

{{בקרת זהויות}}

[[קטגוריה:מטריצות]]
[[קטגוריה:תורת הגרפים]]