גרף ממושקל הוא גרף עבורו לכל קשת בגרף משויך "משקל" - לרוב מספר ממשי .
דוגמה לגרף ממושקל. המספר הצמוד לכל קשת (כלומר, לכל חיבור בין שתי נקודות) מסמן את משקלה מבחינה פורמלית, זהו גרף
G
=
(
V
,
E
)
{\displaystyle G=\left(V,E\right)}
w
:
E
→
R
{\displaystyle w:E\to \mathbb {R} }
הצמדת משקל לקשתות בגרף מאפשרת למדל בעיות מעניינות רבות, ובכללן עץ פורש מינימלי , מציאת המרחק הקצר בגרף בין שני צמתים , מציאת כל המרחקים הקצרים ביותר בגרף, ועוד.
מקרה פרטי של גרף ממושקל הוא גרף מטרי , שהוא גרף ממושקל מלא אשר פונקציית המשקל שלו משרה מרחב מטרי , דהיינו – מתקיים אי-שוויון המשולש , כלומר לכל שלושה צמתים
a
,
b
,
c
{\displaystyle a,b,c}
d
(
a
,
b
)
+
d
(
b
,
c
)
≥
d
(
a
,
c
)
{\displaystyle d\left(a,b\right)+d\left(b,c\right)\geq d\left(a,c\right)}
d
(
a
,
b
)
{\displaystyle d\left(a,b\right)}
a
{\displaystyle a}
b
{\displaystyle b}
(
a
,
b
)
{\displaystyle \left(a,b\right)}
d
(
a
,
b
)
=
d
(
b
,
a
)
{\displaystyle d(a,b)=d(b,a)}
a
,
b
{\displaystyle a,b}
קישורים חיצוניים
עריכה
