היכן השתמשנו בהוכחת אי שוויון המשולש בהוכחת נכונות יחס הקירוב של אלגוריתם הקירוב הקירוב של…

שאלת רב־ברירהq-2522db253df8

נוסח השאלה

היכן השתמשנו בהוכחת אי שוויון המשולש בהוכחת נכונות יחס הקירוב של אלגוריתם הקירוב הקירוב של TSP (Traveling Salesperson Problem) שראינו בהרצאה?

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

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

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.

Exam

נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 2.pdf

Question 10Page 5Visual reading

View source scan — page 5