Question

dag

יהא G=(V,E)G = (V, E) גרף מכוון. הציעו אלגוריתם המחלק את קשתות הגרף לשתי קבוצות זרות E=E1E2E = E_1 \cup E_2, כך שהגרפים (V,E1)(V, E_1) ו-(V,E2)(V, E_2) הם חסרי מעגלים מכוונים. על האלגוריתם לרוץ בזמן O(V+E)O(|V| + |E|).

1

Answers

נקבע סדר כלשהו על צמתי הגרף v1,,vnv_1, \ldots, v_n. נגדיר E1={(vi,vj)E:i<j}E_1 = \{(v_i, v_j) \in E : i < j\} ו-E2={(vi,vj)E:i>j}E_2 = \{(v_i, v_j) \in E : i > j\}.

נכונות: מיידית מההגדרה של הגרפים.

סיבוכיות: קובעים סדר על הצמתים ועושים מעבר יחיד על הקשתות - O(V+E)O(|V| + |E|).

1
Feedback