Complexity Atlas
HE
Source-backed question

נגדיר את בעיית האופטימיזציה הבאה, WMAXCUT. קלט: גרף G = (V, E) לא מכוון ופונקציה w : E ℝ+ המתאימה משקל חיובי ל…

1Exams0Assignments0Lessons1Source documents
שאלה פתוחהq-baff6a1f6272

נוסח השאלה

נגדיר את בעיית האופטימיזציה הבאה, WMAXCUT. קלט: גרף G = (V, E) לא מכוון ופונקציה w:E→R+w : E \to ℝ+ המתאימה משקל חיובי לכל קשת. מטרה : למצוא חתך מושרה בגרף שמשקלו מקסימלי. יהי G = (V, E), w קלט לבעיה, ונסמן ב W את סך כל המשקלים בגרף, כלומר,W=Σe∈Ew(e), W = Σ_{e\in E} w(e). מהו הערך הגדול ביותר α∈[0,1]α \in [0,1] עבורו ידוע שקיים חתך בגרף במשקל αWαW ? שימו לב כי עבור הערך שתבחרו יש להוכיח כי קיים חתך כדרוש, וגם לא ידוע שקיים חתך גדול יותר.

תמלול ראשון מתוך עמוד המקור ב־tools/summary/.work. צילום העמוד מצורף למטה כדי שאפשר יהיה לאמת סימון מתמטי וניסוח.

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

2025 C · moed A

shalon_131111_2025_s3_g06_moed1.pdf

Question 3Page 21Visual reading

Byte-identical aliases: נושא 131111 קבוצה 13111106 שנה 2025 סמסטר 3 מועד 1.pdf

View source scan — page 21Source page 21 from shalon_131111_2025_s3_g06_moed1.pdf Open full size
Further practice

These are topic and lesson matches, not identical appearances.

Assignmentנקרא לגרף צנוע אם הדרגה המקסימלית שלו היא לכל היותר 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. יהי G=(V,E) גרף מכוון, כאשר V=\1,2, ,n\. נסמןTopically related — not a duplicateAssignmentנגדיר אלגוריתם קירוב בשם Next-Fit לבעיית האופטימיזציה של Bin-Packing: קלט: a 1, ,a n , כאשר a 1, ,a n (0,1] ו-n N. לכל i=1, ,n: 1. אם a i יכול להיכנס…Topically related — not a duplicateAssignmentקליק בגרף לא מכוון הוא קבוצת קודקודים שכל שני קודקודים שונים בה מחוברים בקשת. גרף הוא איחוד זר של קליקים אם ניתן לחלק את קודקודיו לקבוצות שכל אחת מהן…Topically related — not a duplicate

Near variants — not duplicates