Sách Giáo trình toán dời rạc

ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON
4.1. ĐƯỜNG ĐI EULER VÀ ĐỒ THỊ EULER.

[TABLE="width: 100%"]
[TR]
[TD]A
[/TD]
[/TR]
[/TABLE]
[TABLE="width: 100%"]
[TR]
[TD]B
[/TD]
[/TR]
[/TABLE]
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.
[TABLE="width: 100%"]
[TR]
[TD]A

[/TD]
[/TR]
[/TABLE]
[TABLE="width: 100%"]
[TR]
[TD]D

[/TD]
[/TR]
[/TABLE]
[TABLE="width: 100%"]
[TR]
[TD]B

[/TD]
[/TR]
[/TABLE]
[TABLE="width: 100%"]
[TR]
[TD]C

[/TD]
[/TR]
[/TABLE]
[TABLE="width: 100%"]
[TR]
[TD]D
[/TD]
[/TR]
[/TABLE]
[TABLE="width: 100%"]
[TR]
[TD]C
[/TD]
[/TR]
[/TABLE]
[TABLE="align: left"]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD="align: left"][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD="align: left"][/TD]
[/TR]
[TR]
[TD][/TD]
[/TR]
[/TABLE]






G
Dân thành phố từng thắc mắc: “Có thể nào đi dạo qua tất cả bảy cầu, mỗi cầu chỉ một lần thôi không?”. Nếu ta coi mỗi khu vực A, B, C, D như một đỉnh và mỗi cầu qua lại hai khu vực là một cạnh nối hai đỉnh thì ta có sơ đồ của Konigsberg là một đa đồ thị G như hình trên.
Bài toán tìm đường đi qua tất cả các cầu, mỗi cầu chỉ qua một lần có thể được phát biểu lại bằng mô hình này như sau: Có tồn tại chu trình đơn trong đa đồ thị G chứa tất cả các cạnh?
4.1.1. Định nghĩa: Chu trình (t.ư. đường đi) đơn chứa tất cả các cạnh (hoặc cung) của đồ thị (vô hướng hoặc có hướng) G được gọi là chu trình (t.ư. đường đi) Euler. Một đồ thị liên thông (liên thông yếu đối với đồ thị có hướng) có chứa một chu trình (t.ư. đường đi) Euler được gọi là đồ thị Euler (t.ư. nửa Euler).
Thí dụ 1:







Giao trinh Toan roi rac