|
|
עמוד:246
א . מצאו את המסלולים הקצרים ביותר מן הקדקוד A לכל אחד מן הקדקודיס האחריס ברשת הנתונה . תארו את המסלולים האלה בצורת עץ . ב . כל קשת בגרף G צבועה בכחול או באדום . ce X הם קדקודים בגרף xs Y ) . ( Y e IM כתבו אלגוריתם מילולי , קצר ויעיל , בעברית מבנית , למציאת אורך המסלול הקצר ביותר ג' -מ ל-ץ , כאשר חלקו הראשון של המסלול יהיה מורכב מקשתות אדומות בלבד , וחלקו השני יהיה מורכב מקשתות כחולות בלבד . שימו לב : כל אחד משני החלקים יכול להיות ריק . שאלה 5 . 13 נתון הגרף , G ( V , E ) G כאשר V מבטא קבוצת קדקודים בגרף £ -ו מבטא קבוצת קשתות בגרף . פונקציית המשקל W : E - > R + קובעת משקל ( מספר ) לכל קשת בגרף . G לפניכם רשת י א . מצאו את כל המסלולים הקצרים ביותר מן הקדקוד A לקדקוד H ברשת הנתונה . תארו כל מסלול כזה בנפרד באופן סכמתי , בצורת רשימה ליניארית מקושרת . לדוגמה . A ^ C ^ F ^ H . ב . Z , r , X הם קדקודים בגרף . ( Z eY , YeV , XeV )
|
|