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

תוכן שנמחק תוכן שנוסף

בשורה

גרסה מ־07:40, 6 ביולי 2005

גרף ממושקל הינו גרף עבורו לכל קשת בגרף משויך "משקל" - לרוב מספר ממשי. מבחינה פורמלית, זהו גרף $G=\left(V,E\right)$ ופונקציית משקל $w:E\to \mathbb {R}$ .

הצמדת משקל לקשתות בגרף מאפשרת למדל בעיות מעניינות רבות, ובכללן עץ פורש מינימלי, מציאת המרחק הקצר בגרף בין שני צמתים, מציאת כל המרחקים הקצרים ביותר בגרף, ועוד.

מקרה פרטי של גרף ממושקל הוא גרף מטרי, שהוא גרף ממושקל מלא אשר פונקציית המשקל שלו משרה מרחב מטרי, דהיינו - מתקיים אי שוויון המשולש, דהיינו בין כל שלוש נקודות $\ a,b,c$ מתקיים

$d\left(a,b\right)+d\left(b,c\right)\geq d\left(a,c\right)$ , כאשר $d\left(a,b\right)$ הוא המרחק בין a ל-b, או משקל הקשת $\left(a,b\right)$ .

ראה גם

תורת הגרפים

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