מטריצת שכנות – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
ויקיפדיה:Check Wikipedia |
הפיכת פסקה קטנה לחלק מהמבוא |
||
שורה 9:
מטריצת השכנויות של [[גרף שלם]] תהיה המטריצה בה כל התאים בעלי הערך 1, פרט לאלכסון הראשי.{{ש}}
מטריצת השכנויות של [[גרף חסר קשתות]] תהיה [[מטריצת האפס]].
בגרפים שאינם פשוטים
ניתן לבנות מטריצת שכנויות שערך התא במטריצה יהיה מספר הקשתות מ-i ל-j.▼
== תכונות ==
שורה 17 ⟵ 20:
יחד עם זאת, אלגוריתמים בסיסיים רבים (כמו [[DFS]], [[BFS]], מיון טופולוגי וכו') רצים בזמן <math>\ O(|V|+|E|)</math> כאשר <math>\ |V|</math> מסמן את מספר הקודקודים ו-<math>\ |E|</math> את מספר הקשתות. בשימוש במטריצת שכנות, הסיבוכיות היא לכל הפחות כגודל המטריצה, כלומר <math>\ O(|V|^2)</math>.
▲בגרפים שאינם פשוטים, לעומת זאת, ייתכנו מספר [[קשת מקבילה|קשתות מקבילות]] בין אותו זוג צמתים. במקרה זה,
▲ניתן לבנות מטריצת שכנויות שערך התא במטריצה יהיה מספר הקשתות מ-i ל-j.
[[קטגוריה:מטריצות]]
| |||