1
TOÁN R I R C Ờ Ạ
NG D NG TRONG TIN H CỨ Ụ Ọ
CÁC BÀI TOÁN V Đ NG ĐIỀ ƯỜ
Ch ng 2. Các bài toán v đ ng điươ ề ườ 2
Chu trình và đ ng đi Eulerườ
Bài toán
Có th xu t phát t i m t ể ấ ạ ộ
đi m nào đó trong thành ể
ph , đi qua t t c 7 cây ố ấ ả
c u, m i cây m t l n, r i ầ ỗ ộ ầ ồ
tr v đi m xu t phát ở ề ể ấ
đ c không?ượ
Leonhard Euler đã tìm ra
l i gi i cho bài toán vào ờ ả
năm 1736
Ch ng 2. Các bài toán v đ ng điươ ề ườ 3
Leonhard Euler
1707 - 1783
Leonhard Euler (15/04/1707 – 18/9/1783) là
m t nhà toán h c và nhà v t lý h c Th y Sĩ. ộ ọ ậ ọ ụ
Ông (cùng v i Archimedes và Newton) đ c ớ ượ
xem là m t trong nh ng nhà toán h c l ng ộ ữ ọ ừ
l y nh t. Ông là ng i đ u tiên s d ng t ẫ ấ ườ ầ ử ụ ừ
"hàm s " (đ c Gottfried Leibniz đ nh nghĩa ố ượ ị
trong năm 1694) đ miêu t m t bi u th c có ể ả ộ ể ứ
ch a các đ i s , nh y = F(x). Ông cũng ứ ố ố ư
đ c xem là ng i đ u tiên dùng vi tích phân ượ ườ ầ
trong môn v t lý.ậ
Ch ng 2. Các bài toán v đ ng điươ ề ườ 4
Leonhard Euler
1707 - 1783
Ông sinh và l n lên t i Basel, và đ c xem là th n ớ ạ ượ ầ
đ ng toán h c t nh . Ông làm giáo s toán h c t i ồ ọ ừ ỏ ư ọ ạ
Sankt-Peterburg, sau đó t i Berlin, r i tr l i Sankt-ạ ồ ở ạ
Peterburg. Ông là nhà toán h c vi t nhi u nh t: t t ọ ế ề ấ ấ
c các tài li u ông vi t ch a đ y 75 t p. Ông là nhà ả ệ ế ứ ầ ậ
toán h c quan tr ng nh t trong th k 18 và đã suy ọ ọ ấ ế ỷ
ra nhi u k t qu cho môn vi tích phân m i đ c ề ế ả ớ ượ
thành l p. Ông b mù hoàn toàn trong 17 năm cu i ậ ị ố
cu c đ i, nh ng kho ng th i gian đó là lúc ông cho ộ ờ ư ả ờ
ra h n n a s bài ông vi t.ơ ử ố ế
Tên c a ông đã đ c đ t cho m t mi ng núi l a ủ ượ ặ ộ ệ ử
trên M t Trăng và cho ti u hành tinh 2002.ặ ể
Ch ng 2. Các bài toán v đ ng điươ ề ườ 5
Chu trình và đ ng đi Eulerườ
Bài toán
Mô hình hóa bài toán
Xây d ng đ th Gự ồ ị
Đ nh: Các vùng đ t trong ỉ ấ
s đơ ồ
C nh: các cây c u n i ạ ầ ố
gi a hai vùng đ tữ ấ
Yêu c uầ
T n t i hay không m t ồ ạ ộ
chu trình đ n trong đa ơ
đ th G = (V, E) có ch a ồ ị ứ
t t c các c nh c a đ ấ ả ạ ủ ồ
th ?ị