מציאת מסלול ארוך ביותר של קשתות

[סוקרטס האמיתי]

מציאת מסלול ארוך ביותר של קשתות

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

 

[גיל14]

זה לחלוטין תלוי בתנאי.

 

[עדין ר]

שאלת תם

למה שלא תסיר את הקשתות שלא מקיימות את התנאי?

 

[סוקרטס האמיתי]

עשיתי את זה ../images/Emo13.gif

 

[סוקרטס האמיתי]

אוקיי, הסתדרתי

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