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

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

בשורה

גרסה מ־15:50, 6 באפריל 2007

גרף ממושקל הנו גרף עבורו לכל קשת בגרף משויך "משקל" - לרוב מספר ממשי. מבחינה פורמלית, זהו גרף $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)$ .

ראו גם

תורת הגרפים

תבנית:נבדק

גרסה מ־12:01, 21 בפברואר 2007 עריכה Cumulus (שיחה \| תרומות) בדוקי עריכות אוטומטית 9,661 עריכות מ בינויקי. אני מקוה שמותר לקשר לפסקאות בבינויקי. → העריכה הקודמת		גרסה מ־15:50, 6 באפריל 2007 עריכה ביטול המגיה הקטן (שיחה \| תרומות) 415 עריכות מ הגהה העריכה הבאה ←
שורה 1:		שורה 1:
	'''גרף ממושקל''' ~~הינו~~ [[תורת הגרפים\|גרף]] עבורו לכל קשת בגרף משויך "משקל" - לרוב [[מספר ממשי]]. מבחינה פורמלית, זהו גרף <math>G=\left(V, E\right)</math> ופונקציית משקל <math>w: E\to \mathbb{R}</math>.		'''גרף ממושקל''' הנו [[תורת הגרפים\|גרף]] עבורו לכל קשת בגרף משויך "משקל" - לרוב [[מספר ממשי]]. מבחינה פורמלית, זהו גרף <math>G=\left(V, E\right)</math> ופונקציית משקל <math>w: E\to \mathbb{R}</math>.

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