לדלג לתוכן

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

תוכן הדף אינו נתמך בשפות אחרות.
הוספת נושא
מתוך ויקיפדיה, האנציקלופדיה החופשית
תגובה אחרונה: לפני 13 שנים מאת דרך בנושא משהו לא נכון

משהו לא ברור

[עריכת קוד מקור]

לא ברור איך מודדים מרחק של צומת מעצמו. בדוגמה 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)תגובה