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

נוספו 6 בתים ,  לפני 16 שנים
מ
פורס => פורש
מאין תקציר עריכה
מ (פורס => פורש)
'''גרף ממושקל''' הינו [[תורת הגרפים|גרף]] עבורו לכל קשת בגרף משויך "משקל" - לרוב [[מספר ממשי]]. מבחינה פורמלית, זהו גרף <math>G=\left(V, E\right)</math> ופונקציית משקל <math>w: E\to \mathbb{R}</math>.
 
הצמדת משקל לקשתות בגרף מאפשרת למדל בעיות מעניינות רבות, ובכללן [[עץ פורספורש מינימלי]], [[מציאת המרחק הקצר בגרף]] בין שני צמתים, [[מציאת כל המרחקים הקצרים ביותר בגרף]], ועוד.
 
מקרה פרטי של גרף ממושקל הוא '''גרף מטרי''', שהוא גרף ממושקל מלא אשר פונקציית המשקל שלו משרה [[מרחב מטרי]], דהיינו - מתקיים [[אי שוויון המשולש]], דהיינו בין כל שלוש נקודות <math>\ a, b, c</math> מתקיים
[[en:Glossary_of_graph_theory#Weighted_graph]]
 
[[categoryקטגוריה:תורת הגרפים]]