Maximum / Minimum weight branching

[GPXer]

Maximum / Minimum weight branching

שלום. מישהו אולי יכול להסביר לי מה ההגדרה של שני אלה? בעקרון, לפי מה שהבנתי, בגרסת המקסימום, מדובר על יער שמשקל הקשתות בו הוא הגבוה ביותר, כך שאין מעגלים ודרגת הכניסה של כל צומת היא מקסימום 1. אבל לפי ההגדרה הזו, בגרסת המינימום התוצאה היא בעצם גרף חסר קשתות (במקרה שמשקל הקשתות חיובי תמיד).. שזה לא מסתדר לי. מישהו יודע?

 

[johnny d]

השמות קצת מבלבלים

אתה מתאר את בעיית ה maxumum weight branching, במתייחסת ל brancing כאוסף של עצים. בעיית ה minimum weight branching לעומת זאת, היא למצוא עץ מכוון מושרש בעל עלות מינימלית, וזה שקול למציאת עץ המסלולים הקצרים ביותר כאשר מדובר על גרפים לא מכוונים. כמובן שהבעיה הנ"ל פתירה פולינומיאלית...