Bài giảng Đồ thị euler và đồ thị hamilton

Có thể coi năm 1736 là năm khai sinh lý thuyết đồ thị, với việc công bố lời giải

“bài toán về các cầu ở Konigsberg” của nhà toán học lỗi lạc Euler (1707-1783). Thành

phố Konigsberg thuộc Phổ (nay gọi là Kaliningrad thuộc Nga) được chia thành bốn

vùng bằng các nhánh sông Pregel, các vùng này gồm hai vùng bên bờ sông, đảo

Kneiphof và một miền nằm giữa hai nhánh của sông Pregel. Vào thế kỷ 18, người ta xây

bảy chiếc cầu nối các vùng này với nhau