גרף ממושקל – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
אין תקציר עריכה |
||
שורה 1: | שורה 1: | ||
[[קובץ:Weighted graph.jpeg|שמאל|ממוזער|250px|דוגמה לגרף ממושקל. המספר הצמוד לכל צלע מסמן את משקלה]] |
[[קובץ: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>. |
מקרה פרטי של גרף ממושקל הוא '''גרף מטרי''', שהוא גרף ממושקל [[גרף מלא|מלא]] אשר פונקציית המשקל שלו משרה [[מרחב מטרי]], דהיינו - מתקיים [[אי שוויון המשולש]], כלומר לכל שלושה צמתים <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>. |
גרסה מ־10:35, 31 באוקטובר 2010
בתורת הגרפים, גרף ממושקל הנו גרף עבורו לכל קשת בגרף משויך "משקל" - לרוב מספר ממשי.
מבחינה פורמלית, זהו גרף ופונקציית משקל .
הצמדת משקל לקשתות בגרף מאפשרת למדל בעיות מעניינות רבות, ובכללן עץ פורש מינימלי, מציאת המרחק הקצר בגרף בין שני צמתים, מציאת כל המרחקים הקצרים ביותר בגרף, ועוד.
מקרה פרטי של גרף ממושקל הוא גרף מטרי, שהוא גרף ממושקל מלא אשר פונקציית המשקל שלו משרה מרחב מטרי, דהיינו - מתקיים אי שוויון המשולש, כלומר לכל שלושה צמתים בגרף מתקיים - כאשר הוא המרחק בין ל-, או משקל הקשת .