מרחק (תורת הגרפים)

בתורת הגרפים, מרחק (או מרחק גאודזי) מציין את מספר הקשתות במסלול הקצר ביותר מצומת כלשהו לצומת אחר. בגרף בלתי מכוון, המרחק בין ${\displaystyle \ u}$ ל־${\displaystyle \ v}$ שווה למרחק בין ${\displaystyle \ v}$ ל־${\displaystyle \ u}$, ופונקציית המרחק היא מטריקה, בעוד שבגרף מכוון יכול להיות שהמרחקים הללו יהיו שונים.

מרחקו של צומת מעצמו מוגדר כ־0, ומרחקו של צומת מצומת שאין מסלול שמוביל אליו נחשב אינסופי.

בגרף ממושקל, בו לכל קשת יש ערך ("משקל") ואורך מסלול הוא סכום משקלי הקשתות, המרחק הוא מספר הקשתות במסלול הקצר ביותר מבחינת ה"משקל" שלו. במקרה שיש שני מסלולים כאלו, אז המרחק שווה למספר הקשתות המינימלי מבין שני המסלולים.

מונחים קרובים

גרף בלתי-מכוון בעל 6 צמתים ו־7 קשתות

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

• אקסצנטריות של צומת ${\displaystyle \ v}$ היא המרחק הגדול ביותר בין ${\displaystyle \ v}$ לצומת אחר. היא מסומנת כ־${\displaystyle \ \epsilon }$. כלומר, האקסצנטריות של צומת ${\displaystyle \ v}$ מסומנת כ־${\displaystyle \ \epsilon (v)}$.
• רדיוס של גרף הוא האקסצנטריות המינימלית בגרף.
• קוטר של גרף הוא האקסצנטריות המקסימלית בגרף. במילים אחרות, זהו המרחק הגדול ביותר בין שני צמתים בגרף.

דוגמאות

גרף מכוון בעל 4 צמתים ו־5 קשתות

• בגרף הבלתי-מכוון שמשמאל:
  • המרחק בין צומת 1 לצומת 4 הוא 2. המסלול הקצר ביותר הוא המסלול 1->5->4 (זאת למרות שקיים מסלול ארוך יותר 1->2->3->4).
  • האקסצנטריות של הצומת 2 היא 3, כי המרחק עד הצומת המרוחק ביותר ממנו, צומת 6, היא 3.
  • הרדיוס של הגרף הוא 2, כי האקסצנטריות של הצמתים 3,4,5 היא 2, ואין צומת בעל אקסצנטריות נמוכה יותר.
  • הקוטר של הגרף הוא 3, כי האקסצנטריות של הצמתים 1,2,6 היא 3, ואין צמתים בעלי אקסצנטריות גדולה יותר.

• בגרף המכוון שמשמאל:
  • המרחק בין צומת 1 לצומת 4 הוא 2. המסלול הקצר ביותר הוא המסלול 1->3->4, בעוד שהמרחק מצומת 4 לצומת 1 הוא אינסופי, כי אין מסלול שמוביל מ־4 ל־1.
  • האקסצנטריות של צומת 3 היא אינסוף, כי המרחק ממנו לצומת 1 הוא אינסוף.
  • הרדיוס של הגרף הוא 2, כי האקסצנטריות של צומת 1 היא 2, והיא הקטנה ביותר. האקסצנטריות של הצמתים האחרים היא אינסוף.
  • הקוטר של הגרף הוא אינסוף, כי קיים לפחות צומת אחד שהאקסצנטריות שלו היא אינסוף. הדבר נובע מכך שצומת 1 הוא מקור, ואין שום דרך "להיכנס" אליו. במקרה כזה, תמיד יהיה צומת שהאקסצנטריות שלו אינסופית, וזה יהיה גם קוטר הגרף.

• הרעיון של "שש דרגות של הפרדה", המבוסס בעקיפין על עבודתו של סטנלי מילגרם, טוען שהקוטר של הרשת החברתית האנושית הוא 6. כלומר, ששישה קשרים הם המרחק המקסימלי בין כל שני אנשים בעולם.

קישורים חיצוניים

• מרחק, באתר MathWorld (באנגלית)