Bài toán b y chi c c u ả ế ầ ở Konigsberg
Lê-ô-na -le(Léonard Euler) sinh t i Th y Sĩ năm 1707. Năm 20 tu i, ông đ c m i đ n Pê-Ơ ạ ụ ổ ượ ớ ế
tec-bua(Nga) gi ng d y và 6 năm sau, ông tr thành Vi n sĩ Vi n hàn lâm khoa h c Pê-tec-ả ạ ở ệ ệ ọ
bua.
Ngoài đ ng th ng -le, tên c a -le còn g n v i m t bài toán thú v : bài toán b y chi cườ ẳ Ơ ủ Ơ ắ ớ ộ ị ả ế
c u. Hãy b t đ u b ng bài toán v hình chi c phong bì b ng m t nét, m t bài toán mà m iầ ắ ầ ằ ẽ ế ằ ộ ộ ỗ
ng i chúng ta lúc nh t ng làm ít nh t m t l n. Không khó khăn gì đ tìm đ c cách v ,ườ ỏ ừ ấ ộ ầ ể ượ ẽ
nh ng cũng không ph i c đ t bút t b t kì đi m nào trên hình cũng v đ c. Dân chúngư ả ứ ặ ừ ấ ể ẽ ượ
thành ph K -nic-xbec(sau này đ i là Ka-li-nin-grat) gi a TK XVIII cũng đã t ng sôi n i vố ơ ổ ữ ừ ổ ề
m t bài toán nh th . Hai hòn đ o c a thành ph n i v i nhau và n i v i các ph n c a thànhộ ư ế ả ủ ố ố ớ ố ớ ầ ủ
ph n m hai bên b sông Prê-ghen b ng b y chi c c u c a thành ph đ u nh n th y r ngố ằ ờ ằ ả ế ầ ủ ố ề ậ ấ ằ
bao gi h cũgn ph i đi qua m t chi c c u nào đó h n m t l n. Có cách nào đi qua c b yờ ọ ả ộ ế ầ ơ ộ ầ ả ả
chi c c u mà ch đi qua m i chi c đúng m t l n ko?ế ầ ỉ ỗ ế ộ ầ
Ông làm vi c ko bi t m t m i v i m t năng su t phi th ng. Năm 28 tu i, -le nh n làmệ ế ệ ỏ ớ ộ ấ ườ ổ Ơ ậ
trong ba ngày nh ng tính toán thiên văn đ l p b n đ , m t công vi c mà các vi n sĩ cho r ngữ ể ậ ả ồ ộ ệ ệ ằ
ph i làm trong vài tháng. Và ông đã ảlàm xong trong có m t ngày đêm! Vào cu i đ i mình, -ộ ố ờ Ơ
le thông báo cho Vi n hàn lâm r ng ônệ ằ g s đ l i s bài báo đ đăng trên t p chí khoa h cẽ ể ạ ố ủ ạ ọ
c a Vi n trong 20 năm. Sau khi ông m t, các công trình ch a công b c a ông còn nhi u đ nủ ệ ấ ư ố ủ ề ế
m c t p chí c a vi n đăng trong 47 năm m i h t(theo t p chí Kvant sô11-1983).ứ ạ ủ ệ ớ ế ạ
cách gi i c a -le. Tr c h t ta g i 1 đ nh là đ nh l n u t đ nh đó xu t phát m t s lả ủ Ơ ướ ế ọ ỉ ỉ ẻ ế ừ ỉ ấ ộ ố ẻ
đo n, là đ nh ch n n u t đ nh đó xu t phát m t s ch n đo n. -le đã ch ng minh r ng m tạ ỉ ẵ ế ừ ỉ ấ ộ ố ẵ ạ Ơ ứ ằ ộ
hình liên thông (hình mà t m t đi m b t kì c a hình có th đi t i t t c các đi m khác c aừ ộ ể ấ ủ ể ớ ấ ả ể ủ
hình) có các tính ch t sau: 1. Hình ko có đ nh l thì bao gi cũng v đ c b ng m t nét khépấ ỉ ẻ ờ ẽ ượ ằ ộ
kín( ki m đ u và đi m cu i c a nét v trùng nhau). 2. Hình ch có hai đ nh l thì bao gi cũgnể ầ ể ố ủ ẽ ỉ ỉ ẻ ờ
v đ c b ng m t nét (ph i v xu t phát t m t đ nh và k t thúc đ nh l kia). 3. Hình có 2nẽ ợ ằ ộ ả ẽ ấ ừ ộ ỉ ế ở ỉ ẻ
đ nh l (hình nào cũng ch có m t s ch ng các đ nh l ) thì ko th v đ c v i ít h n n nét.ỉ ẻ ỉ ộ ố ẵ ỉ ẻ ể ẽ ượ ớ ơ
Tr l i bài toán b y chi c c u. Vì ta ch quan tâm đ n vi c qua c u nên ta có th kí hi u cácở ạ ả ế ầ ỉ ế ệ ầ ể ệ
khu v c A,B,C,D c a thành ph b các đi m A,B,C,D, còn b y chi c c u đ c bi u th b yự ủ ố ở ể ả ế ầ ợ ể ị ả
đ ng n i hai trong các đi m y. Hình có b n đ nh l , nên ko th v đ c b ng m t nét.ườ ố ể ấ ố ỉ ẻ ể ẽ ượ ằ ộ
Nh v y, ko th đi qua c b y chi c c u mà ch đi qua m i chi c đúng m t l n( sau nàyư ậ ể ả ả ế ầ ỉ ỗ ế ộ ầ
ng i dân Ka-li-nin-grat đã xây thêm chi c c u th tám). Trong tr ng h p đ c bi t, n uườ ế ầ ứ ườ ợ ặ ệ ế
b y chi c c u có v trí nh trên hình thì có th đi qua m i chi c đúng m t l n vì hình v chả ế ầ ị ư ể ỗ ế ộ ầ ẽ ỉ
có hai đ nh l A và Bỉ ẻ : hành trình có th xu t phát t Avà k t thúc B, l n l t qua các c uể ấ ừ ế ở ầ ượ ầ
ghi s t 1 đ n 7.ố ừ ế