פורטל:מדעי המחשב/הידעת?/19

מפת קנינסברג, הנהר והגשרים מודגשים בצבע

העיר קניגסברג שבפרוסיה המזרחית (כיום קלינינגרד שברוסיה) הייתה מחולקת לארבעה חלקים על ידי הנהר פרגוליה. שבעה גשרים חיברו בין ארבעת חלקי העיר. בין תושבי העיר התפתחה מסורת לפיה לא ניתן לחצות את כל שבעת הגשרים ולחזור לנקודת ההתחלה מבלי לעבור על אותו גשר יותר מפעם אחת. תושבי העיר ניסו להוכיח או להפריך השערה זו, אולם ללא הצלחה. הבעיה התפרסמה בשם בעיית הגשרים של קניגסברג. המתמטיקאי לאונרד אוילר הצליח לפתור את הבעיה, והציג את פתרונו לאקדמיית סנקט פטרבורג ב-26 באוגוסט 1735. בהוכחתו הוא תיאר את הבעיה באופן סכמטי: כל נקודה ייצגה חלק של העיר, וכל קו ייצג גשר. הוא הראה שמכיוון שמכל נקודה יוצא מספר אי-זוגי של קווים, לא קיים מסלול סגור שעובר דרך כל הקווים. הייתה זו אחת הבעיות הראשונות בתורת הגרפים שנפתרו.