Chương
Chương 4:
4:
LÝ THUY
LÝ THUYẾ
ẾT Đ
T ĐỒ
ỒTH
THỊ
Ị
Chương
Chương 4
4
4.3 ĐỒTHỊEULER
4.4 ĐỒTHỊHAMILTON
CÂY
4.6
BÀI TOÁN TÌM ĐƯỜNG ĐI
NGẮN NHẤT
4.5
MỞ ĐẦU
4.1
CÁC KHÁI NIỆM CƠ BẢN
4.2
4.I MỞ ĐẦU
Bài toán về những cây cầu ở Konigsber
Năm 1736 Euler, cha đẻ của lý thuyết đồ thị, đã giải
được bài toán hóc búa nổi tiếng thời đó về những cây
cầu ở Konigberg.
Thành phố Konigberg có hai hòn đảo nối với nhau và
với 2 bờ sông bằng 7 chiếc cầu như hình vẽ.
Tìm đường đi qua tất cả 7 cây cầu, mỗi cây cầu chỉ
được đi qua một lần, sau đó quay về nơi xuất phát
4.2 CÁC KHÁI NIỆM CƠ BẢN
4.2.1 Đồthị, đỉnh, cạnh, cung:
Đ
Đồ
ồth
thị
ịvô
vô hư
hướ
ớng
ng G = (V, E) gồm tập V các đ
đỉ
ỉnh
nh
và tập E các c
cạ
ạnh
nh.
vew
V
Ví
íd
dụ
ụ:
: