הגשרים של קניגסברג – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ שוחזר מעריכות של 93.173.244.131 (שיחה) לעריכה האחרונה של זאב קטן |
|||
שורה 18:
</span>
בעיית הגשרים של קניגסברג היא למעשה השאלה האם ניתן למצוא מסלול רציף המתחיל מצומת כלשהו ועובר דרך כל שבע הקשתות פעם אחת בדיוק. כדי להיווכח בכך שהתשובה היא '
נבחר את אחד הצמתים ונניח שהמסלול לא מתחיל ולא נגמר בו. בכל פעם שמגיעים לצומת הזה חייבים להגיע לצומת דרך קשת אחת ולצאת מהצומת דרך קשת אחרת. כלומר בכל ביקור בצומת שתי קשתות נפסלות לשימוש עתידי (כי אסור לעבור על אותה קשת פעמיים). מכיוון שהמסלול לא מתחיל או נגמר בצומת הנתון מובטח שלכל כניסה לצומת אכן תתאים יציאה מהצומת ובסך הכל לצומת חייב להיות מספר זוגי של קשתות המחוברות אליו (אם לצומת יהיה מספר אי-זוגי של קשתות המחוברות אליו אז המסלול ייכנס לצומת בלא אפשרות לצאת).
שורה 33:
==ראו גם==
* [[בעיית הסוכן הנוסע]]
* [[בעיית הדוור הסיני]]
* [[חידת חמשת החדרים]]
| |||