נזכיר את בעיית הסוכן הנוסע. קלט: גרף לא מכוון שלם G = (V,E) עם משקלות w: E ℕ ומספר k ℕ. שא…

שאלה פתוחהq-d316853324f1

נוסח השאלה

נזכיר את בעיית הסוכן הנוסע. קלט: גרף לא מכוון שלם G = (V,E) עם משקלות $w: E \to ℕ$ ומספר $k \in ℕ$ . שאלה: האם קיים מעגל פשוט ב G העובר דרך כל הקודקודים ומשקלו לכל היותר k. א. הוכיחו כי בעיית הסוכן הנוסע היא NP קשה. ב. נסחו את בעיית האופטימיזציה המתאימה לבעיית הסוכן הנוסע, והוכיחו כי אם קיים אלגוריתם קירוב לבעיה עבור גרפים עם משקלים כלליים עם יחס קירוב 2 אז P = NP.

תמלול ראשון מתוך עמוד המקור ב־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

2026 B · moed B

מ-נושא 131111 סיבוכיות מועד 2.pdf

Question 1Page 15, 19Visual reading

View source scan — page 15

Source page 15 from מ-נושא 131111 סיבוכיות מועד 2.pdf

Open full size

View source scan — page 19

Source page 19 from מ-נושא 131111 סיבוכיות מועד 2.pdf

Open full size

נוסח השאלה

Appearances by source document

2026 B · moed B

Related questions from another source type