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