Question

dynamic_programming
matching

נתון עץ לא מכוון T=(V,E)T = (V,E) ופונקציית משקלים אי-שלילית על הקשתות w:ER0w:E \to \mathbb{R}_{\geq 0}. שידוך בגרף הוא קבוצת קשתות MEM \subseteq E כך שכל צומת בגרף הוא קצה של קשת אחת לכל היותר בשידוך. משקל השידוך הוא סכום משקלי הקשתות בו.

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

1

Answers

Feedback