מרחק (תורת הגרפים)
מתוך ויקיפדיה, האנציקלופדיה החופשית
מרחק (או מרחק גאודזי) הוא מונח בתורת הגרפים, המציין את מספר הקשתות המינימלי שיש לעבור כדי להגיע מצומת מסוים לאחר. בגרף בלתי-מכוון, המרחק בין 
ל־
שווה למרחק בין ל־, ופונקציית המרחק היא מטריקה, בעוד שבגרף מכוון יכול להיות שהמרחקים הללו יהיו שונים.
מרחקו של צומת מעצמו מוגדר כ־0, ומרחקו של צומת מצומת שאין מסלול שמוביל אליו נחשב אינסופי.
[עריכה] מונחים קרובים
ישנם מספר מונחים בתורת הגרפים המבוססים על מושג המרחק:
- אקסצנטריות של צומת היא המרחק הגדול ביותר בין לצומת אחר. היא מסומנת כ־
. כלומר, האקסצנטריות של צומת מסומנת כ־
. - רדיוס של גרף הוא האקסצנטריות המינימלית בגרף.
- קוטר של גרף הוא האקסצנטריות המקסימלית בגרף. במילים אחרות, זהו המרחק הגדול ביותר בין שני צמתים בגרף.
[עריכה] דוגמאות
- בגרף הבלתי-מכוון שמשמאל:
- המרחק בין צומת 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 הוא אינסוף.
- הרדיוס של הגרף הוא 3, כי האקסצנטריות של צומת 1 היא 2, והיא הקטנה ביותר. האקסצנטריות של הצמתים האחרים היא אינסוף.
- הקוטר של הגרף הוא אינסוף, כי קיים לפחות צומת אחד שהאקסצנטריות שלו היא אינסוף. הדבר נובע מכך שצומת 1 הוא מקור, ואין שום דרך "להיכנס" אליו. במקרה כזה, תמיד יהיה צומת שהאקסצנטריות שלו אינסופית, וזה יהיה גם קוטר הגרף.
הרעיון של "שש דרגות של הפרדה", המבוסס בעקיפין על עבודתו של סטנלי מילגרם טוען שהקוטר של הרשת החברתית האנושית הוא 6. כלומר, ששישה קשרים הם המרחק המקסימלי בין כל שני אנשים בעולם.
