שאלה פתוחהq-2efc74f82f91
נוסח השאלה
בגרף לא מכוון, שלושה קודקודים שונים מהווים משולש אם כל שניים מהם מחוברים בקשת. אוסף משולשים בגרף ייקרא זר בקשתות אם כל קשת של הגרף נמצאת על לכל היותר משולש אחד מהאוסף (קודקוד עשוי להופיע על יותר ממשולש אחד באוסף). נגדיר בעיית מקסימיזציה כלהלן. קלט : גרף לא מכוון G. מטרה : למצוא בגרף G אוסף משולשים זר בקשתות גדול ככל האפשר. 1/3 הוכיחו כי קיים לבעיה זו אלגוריתם (דטרמיניסטי) עם זמן ריצה פולינומיאלי אשר משיג יחס קירוב 3
תמלול ראשון מתוך עמוד המקור ב־tools/summary/.work. צילום העמוד מצורף למטה כדי שאפשר יהיה לאמת סימון מתמטי וניסוח.
ייחוס מדויק
מופעים לפי מסמך מקור
כל כרטיס הוא קובץ שונה באמת. גרסאות או שאלונים כפולים באותו PDF מוצגים בתוך אותו כרטיס ואינם מגדילים את מספר המועדים.
בחינה
2024 ב׳ · מועד א׳
נושא 131111 קבוצה 13111102 שנה 2024 סמסטר 2 מועד 1.pdf
שאלה 2עמוד 5קריאה חזותית
עותקים זהים של אותו מסמך: נושא 131111 קבוצה 13111103 שנה 2024 סמסטר 2 מועד 1.pdf · נושא 131111 קבוצה 13111104 שנה 2024 סמסטר 2 מועד 1.pdf · נושא 131111 קבוצה 13111105 שנה 2024 סמסטר 2 מועד 1.pdf
הצגת צילום המקור — עמוד 5
פתיחה בגודל מלא