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$ , בעזרת הסעיף הקודם.

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

ייחוס מדויק

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

מטלה

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

שאלה 3עמוד 1נבדק אנושית

תרגול המשך

אלו התאמות לפי נושא ושיעור — לא מופעים זהים של אותה שאלה.