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