לעבור על כל גשר פעם אחת: למה אין מסלול כזה בקניגסברג, הכלל של אוילר על צמתים אי־זוגיים, איפה מסלול חייב להתחיל, ומתי הוא חוזר להתחלה.
שלב 1 מתוך 6 · החידה
שלב 1 מתוך 6
החידה
תושבי קניגסברג נהגו לטייל בעיר ביום ראשון, ושאלו: האם אפשר לצאת לטיול שעובר על כל אחד משבעת הגשרים בדיוק פעם אחת? אף אחד לא מצא מסלול כזה, אבל אף אחד גם לא הוכיח שאין. בגרף, השאלה היא אם יש מסלול שעובר על כל קשת פעם אחת, בלי להרים את העיפרון. מסלול כזה נקרא היום מסלול אוילר. נבאו.
שלב 2 מתוך 6
המסלול הטוב ביותר
הטיעון של אוילר פשוט. בכל פעם שמסלול עובר דרך צומת, הוא נכנס בקשת אחת ויוצא באחרת, ולכן משתמש בקשתות של הצומת בזוגות. צומת שאינו ההתחלה או הסוף חייב להיות בעל דרגה זוגית. בקניגסברג כל ארבעת הצמתים אי־זוגיים. כשאין מסלול שלם, ההולך בסצנה עובר על הכי הרבה גשרים שאפשר, והשאר נשארים אדומים.
שלב 3 מתוך 6
לתקן את העיר
גשר אחד יותר או אחד פחות משנה את הזוגיות של שני הקצוות שלו. שנו את מספר הגשרים וחפשו מצב שבו ההולך עובר על כולם.
שלב 4 מתוך 6
איפה להתחיל
כשיש בדיוק שני צמתים אי־זוגיים, יש מסלול, אבל לא מכל מקום. חשבו על צומת אי־זוגי: הקשתות שלו מתחלקות לזוגות של כניסה ויציאה, ותמיד נשארת אחת בלי זוג.
שלב 5 מתוך 6
מעגל
אם המסלול מסתיים בדיוק במקום שבו התחיל, הוא מעגל אוילר. אז גם ההתחלה והסוף משתמשים בקשתות בזוגות.
שלב 6 מתוך 6
הכלל של אוילר
אוילר הראה ששני התנאים, הזוגיות והקשירות, גם מספיקים: אם הגרף קשיר והתנאי על הצמתים האי־זוגיים מתקיים, תמיד יש מסלול. זו נחשבת לתוצאה הראשונה של תורת הגרפים, והיא שימושית עד היום, למשל לתכנון מסלול של משאית זבל או של מכונת ניקוי רחובות שעוברת בכל רחוב פעם אחת.
הגרסה האינטראקטיבית נטענת…
הגרסה האינטראקטיבית נטענת…
כל שלב מכין לכם את הסצנה, ובקר שמסומן „קבוע” נשאר במקומו בשלב הזה.
תרגול · נבאו, ואז הסתכלו
תושבי קניגסברג שאלו: האם אפשר לטייל בעיר ולעבור על כל אחד משבעת הגשרים בדיוק פעם אחת? נבאו.
תרגול · נבאו, ואז הסתכלו
תושבי קניגסברג שאלו: האם אפשר לטייל בעיר ולעבור על כל אחד משבעת הגשרים בדיוק פעם אחת? נבאו.
תרגול · חשבו
בלי לעבור על אף גשר פעמיים, על כמה גשרים לכל היותר אפשר לעבור בקניגסברג של 1736?
תרגול · חשבו
בלי לעבור על אף גשר פעמיים, על כמה גשרים לכל היותר אפשר לעבור בקניגסברג של 1736?
תרגול · הגיעו למטרה
הוסיפו או הסירו גשרים עד שיש מסלול שעובר על כל גשר בדיוק פעם אחת, ולחצו על בדיקה.
תרגול · הגיעו למטרה
הוסיפו או הסירו גשרים עד שיש מסלול שעובר על כל גשר בדיוק פעם אחת, ולחצו על בדיקה.
תרגול · בחרו
ב־8 גשרים הדרגות הן A , B , C , D , ויש מסלול שעובר על כולם. איפה הוא חייב להתחיל?
תרגול · בחרו
ב־8 גשרים הדרגות הן A , B , C , D , ויש מסלול שעובר על כולם. איפה הוא חייב להתחיל?
תרגול · הגיעו למטרה
מעגל אוילר הוא מסלול שעובר על כל קשת פעם אחת וחוזר לנקודת ההתחלה. שנו את הגשרים עד שיש כזה, ולחצו על בדיקה.
תרגול · הגיעו למטרה
מעגל אוילר הוא מסלול שעובר על כל קשת פעם אחת וחוזר לנקודת ההתחלה. שנו את הגשרים עד שיש כזה, ולחצו על בדיקה.
תרגול · בחרו
גרף קשיר. מתי יש בו מסלול שעובר על כל קשת בדיוק פעם אחת?
תרגול · בחרו
גרף קשיר. מתי יש בו מסלול שעובר על כל קשת בדיוק פעם אחת?
השיעור הושלם. עניתם על כל שאלות התרגול בו.