1. יהי G=(V,E) גרף מכוון, כאשר V=\1,2, ,n\. נסמן

שאלה פתוחהq-8fa3f771ac3a

נוסח השאלה

יהי $G=(V,E)$ גרף מכוון, כאשר $V=\{1,2,\ldots,n\}$ . נסמן
$E_1=\{(i,j)\in E\mid i<j\}, \qquad E_2=\{(i,j)\in E\mid i>j\},$
וכן $G_1=(V,E_1)$ ו- $G_2=(V,E_2)$ . הראו כי $G_1,G_2$ חסרי מעגלים מכוונים.
נגדיר את בעיית האופטימיזציה:

קלט: גרף מכוון $G=(V,E)$ .
מטרה: למצוא $E'\subseteq E$ גדולה ככל האפשר כך ש- $G'=(V,E')$ חסר מעגלים.

הציעו אלגוריתם פולינומי בעל יחס קירוב $1/2$ , בעזרת הסעיף הקודם.

נוסח מטלה שנבדק אנושית.

Exact provenance

Each card is a genuinely distinct file. Printed versions inside one PDF stay in that card and do not inflate the sitting count.

Assignment

2026ב_03_תרגיל_בית_3.md

Question 3Page 1Human reviewed