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

עיון אינטראקטיבי בהיסטוריה

→ העריכה הקודמת העריכה הבאה ←

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

חזותיקוד ויקי

בשורה

גרסה מ־01:14, 13 בינואר 2011

דוגמה לגרף משוקלל. המספר הצמוד לכל צלע מסמן את משקלה

בתורת הגרפים, גרף משוקלל הנו גרף עבורו לכל קשת בגרף משויך "משקל" - לרוב מספר ממשי.

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

נושאים בתורת הגרפים
הגדרות	צומת • קשת • דרגה • מסלול • מרחק
מבנים	גרף • גרף ממושקל • מעגל • גרף מקרי • היפרגרף • מולטיגרף • עץ • קומפלקס
בניות וטיפוסים	גרף משלים • גרף קיילי • גרף שלם • גרף תחרות • עץ פורש • רשת זרימה • שידוך
תכונות	גרף n-צביע • גרף דו-צדדי • גרף מישורי • גרף מרחיב • גרף רגולרי • גרף קשיר • עץ בינומי • עץ פורש מינימלי