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

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

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

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

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

בשורה

גרסה מ־21:32, 5 ביולי 2015

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

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

מבחינה פורמלית, זהו גרף $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)$ וכן מתקיים כי $d(a,b)=d(b,a)$ עבור כל שני קודקודים $a,b$ בגרף

גרסה מ־11:23, 26 במאי 2014 עריכה Matanyabot (שיחה \| תרומות) 475,756 עריכות מ בוט: החלפת טקסט אוטומטית (-{{נ}} +) → העריכה הקודמת		גרסה מ־21:32, 5 ביולי 2015 עריכה ביטול EranBot (שיחה \| תרומות) בדוקי עריכות אוטומטית, בוטים, מנטרים 307,620 עריכות מ בוט: החלפת טקסט אוטומטית (-{{תבנית: +{{) העריכה הבאה ←
שורה 7:		שורה 7:

	מקרה פרטי של גרף משוקלל הוא '''גרף מטרי''', שהוא גרף משוקלל [[גרף מלא\|מלא]] אשר פונקציית המשקל שלו משרה [[מרחב מטרי]], דהיינו - מתקיים [[אי שוויון המשולש]], כלומר לכל שלושה צמתים <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>d(a,b) = d(b,a)</math> עבור כל שני קודקודים <math>a,b</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>d(a,b) = d(b,a)</math> עבור כל שני קודקודים <math>a,b</math> בגרף
	{{~~תבנית:~~תורת הגרפים}}		{{תורת הגרפים}}

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