טורניר הוא גרף מכוון שבו לכל שני קודקודים שונים u,v קיימת בדיוק אחת מן הקשתות (u,v) או (v,…

שאלה פתוחהq-6b3504fe85d2

נוסח השאלה

טורניר הוא גרף מכוון שבו לכל שני קודקודים שונים $u,v$ קיימת בדיוק אחת מן הקשתות $(u,v)$ או $(v,u)$ .

הוכיחו שאם בטורניר אין מעגל מכוון באורך $3$ , אז אין בו מעגל מכוון כלל.
בבעיית המינימיזציה נדרש להסיר מספר מינימלי של קודקודים מטורניר כך שהגרף הנותר יהיה חסר מעגלים. תנו אלגוריתם פולינומי בעל יחס קירוב $3$ והוכיחו את יחס הקירוב.

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

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

2025_03_תרגיל_3.md

Question 4Page 1Human reviewed