מטריצת שכנות

מטריצת שכנוּת (גם מטריצת סמיכויות או מטריצת שכנויות) היא שיטה לייצוג גרף מכוון בעל $n$ צמתים בעזרת מטריצה ריבועית בגודל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \times n} , שערכי תאיה הם 0 או 1. תא (i,j) בגרף מתאר את קיומה (או העדרה) של הקשת המכוונת מקודקוד i לקודקוד j בגרף. אם אין קשת כזו, הערך בתא במטריצה יהיה 0. אם יש קודקוד כזה, אזי הערך יהיה 1. פעמים רבות דנים בתורת הגרפים בגרפים פשוטים;

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

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

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

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

תכונות

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

הוספה/מחיקת קשת מתבצעת בגישה מיידית, בסיבוכיות זמן של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(1)} ‏.
ניתן לחשב את הגרף המשלים בקלות על ידי חיסור של מטריצת השכנות ממטריצת שכנות של גרף שלם. כך, בכל מקום שהיה בו קשת, כלומר ערך 1, יהיה 0 ובכל מקום שהיה בו 0, יהיה 1.
סיבוכיות מקום קטנה יחסית לשמירת המטריצה בזיכרון, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \Theta(|V|^2)} סיביות.

יחד עם זאת, אלגוריתמים בסיסיים רבים (כמו DFS, BFS, מיון טופולוגי וכו') רצים בזמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(|V|+|E|)} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ |V|} מסמן את מספר הקודקודים ו- $\ |E|$ את מספר הקשתות. בשימוש במטריצת שכנות, הסיבוכיות היא לכל הפחות כגודל המטריצה, כלומר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(|V|^2)} .