Complexity Atlas
HE
Source-backed question

עבור k 3 נגדיר את בעיית האופטימיזציה הבאה, kMaxCut. קלט: גרף לא מכוון G=(V,E). מטרה: למצוא פירוק של V ל-k קבוצ…

1Exams0Assignments0Lessons1Source documents
שאלת רב־ברירהq-14d61dac8387

נוסח השאלה

עבור k≥3k\ge3 נגדיר את בעיית האופטימיזציה הבאה, kMaxCutkMaxCut.

קלט: גרף לא מכוון G=(V,E)G=(V,E).

מטרה: למצוא פירוק של VV ל-kk קבוצות זרות V1,…,VkV_1,\ldots,V_k כך שמספר הקשתות שכל אחד מהקצוות שלהן בקבוצה אחרת מקסימלי.

נסמן ב-mm את מספר הקשתות בגרף. מהו הערך הגדול ביותר של ℓ\ell עבורו ידוע כי קיים פירוק של VV ל-kk קבוצות זרות V1,…,VkV_1,\ldots,V_k כך שמספר הקשתות שכל אחד מהקצוות שלהן בקבוצה אחרת הוא לפחות ℓ\ell?

  1. א

    ℓ=kmk+1\ell=\frac{km}{k+1}

  2. ב

    ℓ=3m4\ell=\frac{3m}{4}

  3. ג

    ℓ=m2k\ell=\frac{m}{2^k}

  4. ד

    ℓ=(2k−1)m2k\ell=\frac{(2^k-1)m}{2^k}

  5. ה

    ℓ=(k−1)mk\ell=\frac{(k-1)m}{k}

  6. ו

    ℓ=m2\ell=\frac{m}{2}

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

Exact provenance

Appearances by source document

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

Exam

2026 B · moed A

מ-2026 סמסטר ב מועד א (טופס נבחן)

Question 7Page 1Human reviewed

This question has no source scan. The only surviving copy is a marked personal exam script — it carries an identity number on every page, over a student's answers and a grader's red corrections. Only the printed question text was taken from it; the handwriting, the marks and the grades are not part of the question and are not shown.

Further practice

These are topic and lesson matches, not identical appearances.

Assignmentקלט: קבוצה U, אוסף \F 1, ,F m\ של m תתי-קבוצות של U, שכל אחת מהן בגודל 3, ומספר טבעי k. שאלה: האם קיימת קבוצה S U, בגודל |S|=k, המקיימתTopically related — not a duplicateAssignmentנקרא לגרף צנוע אם הדרגה המקסימלית שלו היא לכל היותר 1. 1. הוכיחו כי בעיית ההכרעה הבאה היא NP-שלמה: קלט: גרף פשוט לא מכוון G=(V,E) ומספר טבעי k. שאלה:…Topically related — not a duplicateAssignmentנתאר את בעיית האופטימיזציה הבאה: קלט: גרף פשוט מכוון G=(V,E). פלט: קבוצת קשתות E' E גדולה ככל האפשר, כך שהגרף G'=(V,E') חסר מעגלים. 1. נתבונן בקבוצות…Topically related — not a duplicateAssignmentיהא קלט עבור בעיית העץ של שטיינר הכללית, ללא הדרישה שהקלט מקיים את אי-שוויון המשולש: גרף שלם G=(V,E), חלוקה V=R S ופונקציית משקל w:E R + על הקשתות. נג…Topically related — not a duplicateAssignment1. נגדיר אלגוריתם לבעיית BinPacking כלהלן: בהינתן קלט a 1, ,a n, האלגוריתם עובר על כל מספר ברשימה לפי הסדר הנתון; במידת האפשר הוא מכניס אותו לתא האחרו…Topically related — not a duplicateAssignment1. יהי G=(V,E) גרף מכוון, כאשר V=\1,2, ,n\. נסמןTopically related — not a duplicate