שאלת רב־ברירהq-4ac79c657bd3
נוסח השאלה
נעדכן את אלגוריתם הקירוב הקירוב שהראינו בשיעור לבעיית הכיסוי בצמתים באופן הבא. בכל איטרציה של הלולאה המרכזית באלגוריתם, כאשר האלגוריתם בוחר קשת {x,y} הוא מכניס את x לכיסוי (באלגוריתם המקורי האלגוריתם הכניס גם את x וגם את y לכיסוי), ומוחק את הקשת, ואת כל הקשתות המחוברות ל-x. נסמן ב n את מספר הקודקודים בגרף. מהו יחס הקירוב הטוב ביותר שהאלגוריתם משיג?
תמלול ראשון מתוך עמוד המקור ב־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 8Page 11Visual reading
View source scan — page 11
Open full size