מרחק (תורת הגרפים) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
לדוגמה |
מ תיקונים קטנים |
||
שורה 1:
[[תמונה:6n-graf.svg|ממוזער|שמאל|250px|גרף בלתי-מכוון בעל 6 צמתים ו־7 קשתות]]
[[תמונה:Directed graph.svg|ממוזער|שמאל|250px|גרף מכוון בעל 4 צמתים ו־5 קשתות]]
'''מרחק''' (או '''מרחק גאודזי''') הוא מונח ב[[תורת הגרפים]], שמציין דרך כמה קשתות לכל הפחות יש לעבור כדי מצומת מסויים לאחר. בגרף בלתי-מכוון, המרחק בין <math>\ u</math> ל־<math>\ v</math> שווה למרחק בין <math>\ v</math> ל־<math>\ u</math>, ופונקציית המרחק היא [[מטריקה]], בעוד שבגרף מכוון יכול להיות שהמרחקים הללו יהיו שונים.
ישנם מספר מונחים בתורת הגרפים המבוססים על מושג המרחק:
*'''אקסצנטריות''' של צומת <math>\ v</math> היא המרחק הגדול ביותר בין <math>\ v</math> לצומת אחר. היא מסומנת כ־<math>\ \epsilon</math>. כלומר, האקסצנטריות של צומת <math>\ v</math> מסומנת כ־<math>\ \epsilon(v)</math>
*'''רדיוס''' של גרף הוא האקסצנטריות המינימלית בגרף.
*'''קוטר''' של גרף הוא האקסצנטריות המקסימלית בגרף. במילים אחרות, זהו המרחק הגדול ביותר בין שני צמתים בגרף.
שורה 15:
**הרדיוס של הגרף הוא 2, כי האקסצנטריות של הצמתים 3,4,5 היא 2, ואין צומת בעל אקסצנטריות נמוכה יותר.
**הקוטר של הגרף היא 3, כי האקסצנטריות של הצמתים 1,2,6 היא 3, ואין צמתים בעלי אקסצנטריות גדולה יותר.
*בגרף
**המרחק בין צומת 1 לצומת 4 הוא 2. המסלול הקצר ביותר הוא המסלול 1->3->4, בעוד שהמרחק מצומת 4 לצומת 1 הוא אינסופי, כי אין מסלול שמוביל מ־4 ל־1.
**האקסצנטריות של צומת 3 היא אינסוף, כי המרחק ממנו לצומת 1 הוא אינסוף.
| |||