מטריצת שכנות

מתוך ויקיפדיה, האנציקלופדיה החופשית
דוגמה למטריצת שכנות של גרף לא מכוון

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

פעמים רבות דנים בתורת הגרפים בגרפים פשוטים[דרושה הבהרה].

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

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

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

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

תכונות[עריכת קוד מקור | עריכה]

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

  1. הוספה/מחיקת קשת מתבצעת בגישה מיידית, בסיבוכיות זמן של ‏.
  2. ניתן לחשב את הגרף המשלים בקלות על ידי חיסור של מטריצת השכנות ממטריצת שכנות של גרף שלם. כך, בכל מקום שהיה בו קשת, כלומר ערך 1, יהיה 0 ובכל מקום שהיה בו 0, יהיה 1.
  3. סיבוכיות מקום קטנה יחסית לשמירת המטריצה בזיכרון, סיביות.

יחד עם זאת, אלגוריתמים בסיסיים רבים (כמו DFS, BFS, מיון טופולוגי וכו') רצים בזמן כאשר מסמן את מספר הקודקודים ו- את מספר הקשתות. בשימוש במטריצת שכנות, הסיבוכיות היא לכל הפחות כגודל המטריצה, כלומר .

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

ויקישיתוף מדיה וקבצים בנושא מטריצת שכנות בוויקישיתוף