תבנית:הידעת? 11 באוגוסט 2012
►► | הידעת? רענון העמוד הראשי |
◄◄ | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
![מפת קנינסברג, הנהר והגשרים מודגשים](http://up.wiki.x.io/wikipedia/commons/thumb/5/5d/Konigsberg_bridges.png/150px-Konigsberg_bridges.png)
העיר קניגסברג שבפרוסיה המזרחית (כיום קלינינגרד שברוסיה) הייתה מחולקת לארבעה חלקים על ידי הנהר פרגוליה. שבעה גשרים חיברו בין ארבעת חלקי העיר. בין תושבי העיר התפתחה מסורת לפיה לא ניתן לחצות את כל שבעת הגשרים ולחזור לנקודת ההתחלה מבלי לעבור על אותו גשר יותר מפעם אחת. תושבי העיר ניסו להוכיח או להפריך השערה זו, אולם ללא הצלחה. הבעיה התפרסמה בשם בעיית הגשרים של קניגסברג. המתמטיקאי לאונרד אוילר הצליח לפתור את הבעיה, והציג את פתרונו לאקדמיה הפטרבורגית למדעים ב-26 באוגוסט 1735. בהוכחתו הוא תיאר את הבעיה באופן סכמטי. כל נקודה ייצגה חלק של העיר, וכל קו ייצג גשר. הוא הראה שכיוון שמכל נקודה יוצא מספר אי-זוגי של קווים, לא קיים מסלול סגור שעובר דרך כל הקווים. זו אחת הבעיות הראשונות שנפתרו בתורת הגרפים.