Question

vertex_cover
matching

כיסוי בצמתים של גרף לא מכוון G=(V,E)G = (V,E) הוא קבוצת צמתים UVU \subseteq V כך שלכל קשת (a,b)U(a,b) \in U מתקיים ש-{a,b}U\{a,b\} \cap U \neq \emptyset. כיסוי בצמתים UU נקרא כיסוי מינימום אם מספר הצמתים בו אינו עולה על מספר הצמתים בכל כיסוי בצמתים.

הציעו אלגוריתם למציאת כיסוי מינימום בגרף דו צדדי.

1

Answers

Feedback