גרף ממושקל – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מאין תקציר עריכה |
מאין תקציר עריכה |
||
שורה 3:
הצמדת משקל לקשתות בגרף מאפשרת למדל בעיות מעניינות רבות, ובכללן [[עץ פורש מינימלי]], [[מציאת המרחק הקצר בגרף]] בין שני צמתים, [[מציאת כל המרחקים הקצרים ביותר בגרף]], ועוד.
מקרה פרטי של גרף ממושקל הוא '''גרף מטרי''', שהוא גרף ממושקל [[גרף מלא|מלא]] אשר פונקציית המשקל שלו משרה [[מרחב מטרי]], דהיינו - מתקיים [[אי שוויון המשולש]],
<math> d\left(a, b\right) + d\left(b, c\right) \ge d\left(a, c\right)</math>, כאשר <math>d\left(a, b\right)</math> הוא המרחק בין a ל-b, או משקל הקשת <math>\left(a, b\right)</math>.
|