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

משהו לא ברור

לא ברור איך מודדים מרחק של צומת מעצמו. בדוגמה 2 זה קריטי - זה מה שמכריע אם המרחק מהצומת 1 לעצמו הוא 0, אינסוף או שכלל לא מתחשבים בו. אם לא מתחשבים בו, האקסצנטריות של הגרף לא צריכה להיות אינסוף כי אפשר להגיע מ-1 לכל שאר הצמתים. גדי אלכסנדרוביץ' 12:22, 21 באוגוסט 2006 (IDT)

אתה כנראה מבין בנושא הרבה יותר ממני, ונדמה לי שהמרחק של צומת מעצמו הוא אפס, ולא משתמשים בשום קשת, ולא 1 לדוגמה, ואז צריך לולאה. אתה צודק, והרדיוס של הגרף הוא 2. כנראה לא הייתי מרוכז ולא שמתי לב שמצומת 1 אפשר להגיע לכל האחרים. המתעתק • שיחה 12:29, 21 באוגוסט 2006 (IDT)

האמת היא שכתבתי שטות למעלה, כי האקסצנטריות הוגדרה במפורש כמרחק מצומת אחר. פשוט ניסיתי להבין למה האקסצנטריות של הגרף הייתה אינסוף ולכן שיערתי שזה נובע מחוסר בחוגים עצמיים... בכל מקרה, כדאי להעיר משהו על כך שהמרחק מצומת לעצמו מוגדר להיות 0. גדי אלכסנדרוביץ' 12:38, 21 באוגוסט 2006 (IDT)

משהו לא נכון

בערך כתוב שמרחק "מציין את מספר הקשתות המינימלי שיש לעבור כדי להגיע מצומת מסוים לאחר"

זה לא נכון! המרחק הוא מספר הקשתות שעוברים במסלול הקצר ביותר מצומת כלשהו לצומת אחר. אם יש שני מסלולים כאלו, אז זהו מספר הקשתות המינימאלי מבין שני המסלולים. ראו גם בגירסה האנגלית: "the distance between two vertices in a graph is the number of edges in a shortest path connecting them". קובי זטלאוי 21:46, 13 בנובמבר 2010 (IDT)

לא ברורה לי הבעיה שאתה מציג. דרך - שיחה 21:59, 13 בנובמבר 2010 (IST)

פשוט מאוד - הערך מדבר סתם על "מספר הקשתות" ולא מתייחס בשום צורה למסלול הקצר היותר. מהניסוח אפשר להבין שמדובר על מספר הקשתות המינימאלי בין i ל-j ואילו המונח מרחק מדבר על מספר הקשתות המרכיבות את המסלול הקצר ביותר. דוגמה טריוויאלית: נניח יש שני מסלולים בין i ל-j - האחד בעל שתי קשתות שאורך כל אחת מהן 1 והשני בעל קשת אחת שאורכה 3 (אין קשתות נוספות בין i ל-j). המרחק בין i ל j הוא 2 (מס' הקשתות במסלול הקצר ביותר) ולא 1 (מס' הקשתות המינימאלי בין i ל-j) קובי זטלאוי 22:18, 13 בנובמבר 2010 (IDT)

כוונתך לגרף ממושקל? דרך - שיחה 22:51, 13 בנובמבר 2010 (IST)

אכן כן. קובי זטלאוי| 02:20, 14 בנובמבר 2010 (IDT)

כדי להקל על הקוראים הייתי מציע להשאיר את הניסוח כמו שהוא ולהוסיף משפט שיבהיר את צורת החישוב בגרף שכזה.
בגרף ממושקל, בו לכל קשת יש ערך ("משקל"), המרחק הוא מספר הקשתות במסלול הקצר ביותר מבחינת ה"משקל" שלו מצומת כלשהו לצומת אחר. אם יש שני מסלולים כאלו, אז זהו מספר הקשתות המינימלי מבין שני המסלולים. דעתך? דרך - שיחה 02:27, 14 בנובמבר 2010 (IST)