לאיגור
לאיגור, תודה על ההתייחסות לחידה. אשמח אם תעזור לי או שתתן לי כיוןן של מחשבה לגבי הבעיות ברדוקציה הנ"ל (תודה על כל העזרה) 1. יש לסדר N....1 במעגל כך שסכום כל שני מספרים סמוכים לא יהיה כפולה של 3,5,7. דרך אחת להסתכלות על הבעיה הנתונה היא באמצעות רדוקציה שלה לבעיה בתורת הגרפים. *יש למצוא בעיה מתאימה אליה כדאי לבצע רדוקציה ולתאר את הרדוקציה. *יש לפתור את הבעיה המקורית תוך שימוש ברדוקציה, עבור 9=N. 2. יש לבצע רדוקציה מבעיה א' לבעיה ב' בעיה א'- נתון גרף מלא בן N צמתים, כך שלכל קשת משקל חיובי כלשהו (המציין מרחק בין הצמתים אותם היא מחברת). האם קיים מסלול מעגלי באורך N (קשתות) "המבקר" בכל צמתי הגרף ומשקלו איננו עולה על גודל נתון K? בעיה ב'- נתון גרף כלשהו בן N צמתים. האם קיים מסלול מעגלי באורך N (קשתות) "המבקר" בכל צמתי הגרף? 3. יש לבצע רדוקציה מבעיה א' לבעיה ב' בעיה א'- נתון גרף כלשהו בן N צמתים. האם קיימת קבוצת צמתים בגודל K , אשר עבור כל קשת בגרף- לפחות אחד מקצותיה נמצא בקבוצה? בעיה ב'- נתונות S קבוצות של פריטים , כך שכל קבוצה מכילה אחד או יותר פריטים ממכלול הפריטים N...1 . האם קיימת תת קבוצה של K פריטים מן המכלול אשר לה לפחות נציג אחד בכל אחת מן הקבוצות?