גרף ממושקל – הבדלי גרסאות

אין שינוי בגודל ,  לפני 11 שנים
Weighted = משוקלל. לא ממושקל. אין כזו מילה בעברית. אתם מוזמנים לבחון את מאגר המונחים של האקדמיה העברית בטרם המצאת מילים חדשות.
מ (גרף ממושקל הועבר לגרף משוקלל: Weighted = משוקלל. לא ממושקל. אין כזו מילה בעברית. אתם מוזמנים לבחון את מאגר המונחים של האקדמיה העברית בטרם ה...)
(Weighted = משוקלל. לא ממושקל. אין כזו מילה בעברית. אתם מוזמנים לבחון את מאגר המונחים של האקדמיה העברית בטרם המצאת מילים חדשות.)
[[קובץ:Weighted graph.jpeg|שמאל|ממוזער|250px|דוגמה לגרף ממושקלמשוקלל. המספר הצמוד לכל צלע מסמן את משקלה]]
ב[[תורת הגרפים]], '''גרף ממושקלמשוקלל''' הנו [[גרף (תורת הגרפים)|גרף]] עבורו לכל קשת בגרף משויך "משקל" - לרוב [[מספר ממשי]].
 
מבחינה פורמלית, זהו גרף <math>G=\left(V, E\right)</math> ופונקציית משקל <math>w: E\to \mathbb{R}</math>.
הצמדת משקל לקשתות בגרף מאפשרת למדל בעיות מעניינות רבות, ובכללן [[עץ פורש מינימלי]], [[מציאת המרחק הקצר בגרף]] בין שני [[צומת (תורת הגרפים)|צמתים]], [[מציאת כל המרחקים הקצרים ביותר בגרף]], ועוד.
 
מקרה פרטי של גרף ממושקלמשוקלל הוא '''גרף מטרי''', שהוא גרף ממושקלמשוקלל [[גרף מלא|מלא]] אשר פונקציית המשקל שלו משרה [[מרחב מטרי]], דהיינו - מתקיים [[אי שוויון המשולש]], כלומר לכל שלושה צמתים <math>\ a, b, c</math> בגרף מתקיים <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> הוא המרחק בין <math>\ a</math> ל-<math>\ b</math>, או משקל הקשת <math>\left(a, b\right)</math>.
{{תבנית:תורת הגרפים}}
{{נ}}
224

עריכות