ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
NGUYỄN NGỌC HẢI
LÝ THUYẾT ĐỒ THỊ
VÀ ỨNG DỤNG ĐỂ GIẢI TOÁN SƠ CẤP
LUẬN VĂN THẠC SĨ TOÁN HỌC
HÀ NỘI, NĂM 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
NGUYỄN NGỌC HẢI
LÝ THUYẾT ĐỒ THỊ VÀ
ỨNG DỤNG ĐỂ GIẢI TOÁN SƠ CẤP
LUẬN VĂN THẠC SĨ TOÁN HỌC
Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP
Mã số: 60 46 40
NGƯỜI HƯỚNG DẪN KHOA HỌC:
GS. TS. ĐẶNG HUY RUẬN
HÀ NỘI, NĂM 2014
Mục lục
Mở đầu .................................. 5
1 Các khái niệm và định lý cơ bản 7
1.1 Cácvídụvềđồthị......................... 7
1.2 Địnhnghĩađồthị.......................... 11
1.3 Biểu diễn đồ thị bằng hình học . . . . . . . . . . . . . . . . . . 12
1.4 Một số dạng đồ thị đặc biệt . . . . . . . . . . . . . . . . . . . . 13
1.5 Phươngphápđồthị......................... 14
2 Đồ thị và một số bài toán phổ thông 16
2.1 Bài toán liên quan đến bậc của đồ thị . . . . . . . . . . . . . . . 16
2.1.1 Bậccủađỉnh ........................ 16
2.1.2 Nửabậc ........................... 16
2.1.3 Một số tính chất . . . . . . . . . . . . . . . . . . . . . . 17
2.1.4 Ứngdụng .......................... 21
2.2 Bài toán liên quan đến chu trình . . . . . . . . . . . . . . . . . 28
2.2.1 Xích, Chu trình . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.2 Đường,Vòng ........................ 29
2.2.3 Một số tính chất . . . . . . . . . . . . . . . . . . . . . . 29
2.2.4 Ứngdụng .......................... 31
2.3 Bài toán liên quan đến tính liên thông . . . . . . . . . . . . . . 38
2.3.1 Địnhnghĩa ......................... 38
2.3.2 Một số tính chất . . . . . . . . . . . . . . . . . . . . . . 39
2.3.3 Ứngdụng .......................... 43
2.4 Đồ thị Euler - Đồ thị Hamilton . . . . . . . . . . . . . . . . . . 50
3
2.4.1 Đường đi Euler và đồ thị Euler . . . . . . . . . . . . . . 50
2.4.2 Đường đi Hamilton và đồ thị Hamilton . . . . . . . . . . 55
2.4.3 Ứngdụng .......................... 63
2.5 Bài toán liên quan đến đồ thị tô màu . . . . . . . . . . . . . . . 70
2.5.1 Địnhnghĩa ......................... 70
2.5.2 Tínhchất .......................... 71
2.5.3 Thuật toán tìm sắc số . . . . . . . . . . . . . . . . . . . 74
2.5.4 Lớp đồ thị có chu trình tam giác cùng màu . . . . . . . . 75
2.5.5 Ứngdụng .......................... 77
2.6 Bàitoánvềcây ........................... 84
2.6.1 Địnhnghĩa ......................... 85
2.6.2 Đặc điểm của cây và bụi . . . . . . . . . . . . . . . . . . 85
2.6.3 Ứngdụng .......................... 88
Lời kết .................................. 91
Tài liệu tham khảo ........................... 93
4
Mở đầu
Lý thuyết đồ thị (lý thuyết graph) là một ngành toán học hiện đại, một lĩnh
vực khá trẻ của toán học mặc dù những vấn đề của lý thuyết đồ thị đã có từ
vài trăm năm trước đây.
Những ý tưởng cơ bản về lý thuyết đồ thị được đưa ra vào năm 1736 bởi
nhà toán học Thụy Sĩ Leonhard Euler với bài toán nổi tiếng về 7 cây cầu ở
thành phố K¨onigsberg. Những công trình nghiên cứu về lý thuyết đồ thị gắn
liền với những tên tuổi các nhà toán học lớn như Euler, Hamilton,... Cuốn sách
giáo khoa đầu tiên về lý thuyết đồ thị được K¨onig viết và xuất bản tại Leipzig
năm 1936. Mãi 22 năm sau, cuốn sách giáo khoa thứ hai về đồ thị mới được ra
đời bởi nhà toán học Berge viết và in tại Paris.
Vả lại, do đặc trưng rất “gần gũi” với thực tế của mình, lý thuyết đồ thị
ngày càng khẳng định được vị trí quan trọng trong việc áp dụng để giải các
bài toán trong cuộc sống. Nó có nhiều ứng dụng quan trọng trong nhiều ngành
khoa học, kĩ thuật hiện đại: vật lý, hóa học, sinh học, tin học,... Ngày nay, lý
thuyết đồ thị đã trở thành một công cụ không thể thiếu được khi phải giải
quyết những vấn đề có tính chất phải xem xét cả tổng thể.
Được sự hướng dẫn tận tâm, sự chỉ bảo tận tình và những bài giảng tâm
huyết của NGND.GS.TS Đặng Huy Ruận. Tác giả xin đóng góp một phần nhỏ
tìm hiểu của bản thân về lý thuyết đồ thị qua luận văn: “Lý thuyết đồ thị và
ứng dụng để giải toán sơ cấp”.
Luận văn gồm phần mở đầu, kết luận, tài liệu tham khảo và 2 chương.
Chương 1. Các khái niệm và định lý cơ bản.
Chương 1 trình bày một số bài toán dẫn đến khái niệm đồ thị, một số khái
niệm và định lý hay dùng trong lý thuyết đồ thị. Các lý thuyết này đã được
GS.TS Đặng Huy Ruận tích lũy trong cuốn sách “Lý thuyết đồ thị và ứng
dụng” bao gồm:
- Khái niệm về lý thuyết đồ thị.
- Các cách biểu diễn đồ thị.
5