מטריצת שכנות – הבדלי גרסאות

'''מטריצת שכנוּ‏ת''' (גם '''מטריצת סמיכויות''' או מטריצת שכנויות) היא שיטה לייצוג [[גרף מכוון]] בעל <math>n</math> צמתים בעזרת [[מטריצה ריבועית]] בגודל <math>n \times n</math>, שערכי תאיה הם 0 או 1.

תא (i,j) בגרף מתאר את קיומה (או העדרה) של הקשת המכוונת מקודקוד i לקודקוד j בגרף. אם אין קשת כזו, הערך בתא במטריצה יהיה 0. אם יש קודקוד כזה, אזי הערך יהיה 1. פעמים רבות דנים בתורת הגרפים [[גרף פשוט|בגרפים פשוטים]];

 

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

מטריצת השכנויות של [[גרף חסר קשתות]] תהיה [[מטריצת האפס]].

 

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

# הוספה/מחיקת קשת מתבצעת בגישה מיידית, ב[[סיבוכיות זמן]] של <math>\ O(1)</math>{{כ}}.

<!-- מכיוון שגרפים יכולים לייצג יחסים, ניתן גם באמצעות מטריצות שכנות לייצג יחסים. -->

 

ב[[גרף פשוט]] תיתכן קשת יחידה מקודקוד i לקודקוד j.

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