מרחק (תורת הגרפים) – הבדלי גרסאות

'''מרחק''' (או '''מרחק גאודזי''') הוא מונח ב[[תורת הגרפים]], שמציין דרך כמה קשתות לכל הפחות יש לעבור כדי מצומת מסויים לאחר. בגרף בלתי-מכוון, המרחק בין <math>\ u</math> ל־<math>\ v</math> שווה למרחק בין <math>\ v</math> ל־<math>\ u</math>, ופונקציית המרחק היא [[מטריקה]], בעוד שבגרף מכוון יכול להיות שהמרחקים הללו יהיו שונים.

 

ישנם מספר מונחים בתורת הגרפים המבוססים על מושג המרחק:

 

*'''קוטר''' של גרף הוא האקסצנטריות המקסימלית בגרף. במילים אחרות, זהו המרחק הגדול ביותר בין שני צמתים בגרף.

 

*בגרף הבלתי-מכוון שמשמאל:

**המרחק בין צומת 1 לצומת 4 הוא 2. המסלול הקצר ביותר הוא המסלול 1->5->4 (זאת למרות שקיים מסלול ארוך יותר 1->2->3->4).

**הרדיוס של הגרף הוא 3, כי האקסצנטריות של צומת 1 היא 2, והיא הקטנה ביותר. האקסצנטריות של הצמתים האחרים היא אינסוף.

**הקוטר של הגרף הוא אינסוף, כי קיים לפחות צומת אחד שהאקסצנטריות שלו היא אינסוף. הדבר נובע מכך שצומת 1 הוא [[דרגה (תורת הגרפים)#ערכי דרגה מיוחדים|מקור]], ואין שום דרך "להיכנס" אליו. במקרה כזה, תמיד יהיה צומת שהאקסצנטריות שלו אינסופית, וזה יהיה גם קוטר הגרף.