ỨNG DỤNG CÁC THUẬT TOÁN ĐỒ THỊ GIẢI CÁC BÀI TOÁN TỐI ƯU TRONG CHƯƠNG TRÌNH CHUYÊN TIN TRUNG HỌC PHỔ THÔNG
Lý thuyết đồ thị là một lĩnh vực quan trọng được nghiên cứu từ lâu đời và có nhiều ứng dụng hiện đại. Những tư tưởng cơ bản của lý thuyết đồ thị được đề xuất từ những năm đầu của thế kỷ 18 bởi nhà toán học lỗi lạc người Thụy Sĩ Leonhard Euler. Chính ông là người đã sử dụng đồ thị để giải bài toán nổi tiếng về các cái cầu ở thành phố Konigsberg. Từ đó lý thuyết đồ thị ngày càng khẳng định được vị trí quan trọng của mình trong việc áp dụng để giải quyết các bài toán thực tế nhờ vào việc tìm ra ngày càng nhiều các định lý, công thức và thuật toán.
Lý thuyết đồ thị không những có nhiều ứng dụng trong thực tế mà còn là công cụ đắc lực cho ngành công nghệ thông tin. Nó giúp cho chúng ta mô tả một cách dễ dàng các bài toán phức tạp cụ thể, để từ đó ta có thể mã hoá các bài toán đó vào máy tính. Ngoài ra đồ thị được sử dụng để giải quyết các bài toán trong nhiều lĩnh vực khác nhau và được ứng dụng nhiều trong thực tế. Chẳng hạn, sử dụng đồ thị có thể sử dụng để xác định các mạch vòng trong vấn đề giải tích mạch điện. Chúng ta có thể phân biệt các hợp chất hoá học hữu cơ khác nhau với cùng công thức phân tử nhưng khác nhau về cấu trúc phân tử nhờ đồ thị. Chúng ta có thể xác định xem hai máy tính trong mạng có thể trao đổi thông tin được với nhau hay không nhờ mô hình đồ thị của mạng máy tính. Đồ thị có trọng số trên các cạnh có thể sử dụng để giải các bài toán như: tìm đường đi ngắn nhất giữa hai thành phố trong cùng một mạng giao thông; chúng ta còn sử dụng đồ thị để giải các bài toán về lập lịch, thời khoá biểu, và phân bố tần số cho các trạm phát thanh và truyền hình….
Hiện nay có rất nhiều tài liệu, sách, giáo trình đã viết về lý thuyết đồ thị với những nội dung đầy đủ, giúp cho những người muốn nghiên cứu về lý thuyết đồ thị tham khảo. Tuy nhiên các giáo trình chỉ nghiên cứu về phần lý thuyết, giới thiệu các thuật toán của đồ thị mà chưa đi sâu nghiên cứu các ứng dụng, đặc biệt là những bài toán ứng dụng thực tế phục vụ cho việc tham khảo và bồi dưỡng học sinh tham gia thi học sinh giỏi ở các trường THPT, thi Olympic,.. Lý thuyết đồ thị là một mảng rất lớn trong việc giải quyết các bài toán Tin học, đặc biệt là giúp cho học sinh có những nhận biết về ứng dụng thực tế của đồ thị.
Xuất phát từ nhu cầu trên tôi chọn đề tài: “ỨNG DỤNG CÁC THUẬT TOÁN ĐỒ THỊ GIẢI CÁC BÀI TOÁN TỐI ƯU TRONG CHƯƠNG TRÌNH CHUYÊN TIN TRUNG HỌC PHỔ THÔNG”
Mục đích chính của đề tài là: nghiên cứu về lý thuyết đồ thị và một số thuật toán ứng dụng đồ thị trong việc bồi dưỡng học sinh giỏi bộ môn Tin học.
- Nắm được những khái niệm cơ bản của lý thuyết đồ thị.
- Xây dụng một số thuật toán trên đồ thị.
- Ứng dụng một số thuật toán trên đồ thị giải quyết một số bài toán liên quan đến đồ thị.
– Nghiên cứu về lý thuyết đồ thị, xây dựng một số thuật toán và từ đó hệ thống hóa các dạng bài tập liên quan đến đồ thị. Nhận dạng một số bài toán Tin học có thể sử dụng phương pháp đồ thị.
- Đối tượng nghiên cứu
Lý thuyết đồ thị và các ứng dụng của đồ thị.
b. Phạm vi nghiên cứu
Trong khuôn khổ của luận văn thuộc loại nghiên cứu và ứng dụng, tôi chỉ giới hạn nghiên cứu các vấn đề sau:
+ Lý thuyết đồ thị, các ứng dụng.
+ Xây dựng và hệ thống hóa một số ứng dụng của các thuật toán liên quan đến đồ thị nhằm phục vụ cho việc bồi dưỡng học sinh giỏi bậc THPT.
a. Phương pháp nghiên cứu lý thuyết
+ Nghiên cứu lý thuyết về đồ thị, các thuật toán ứng dụng của đồ thị.
+ Hệ thống hóa một số ứng dụng của đồ thị.
b. Phương pháp nghiên cứu thực nghiệm
Sử dụng phương pháp nghiên cứu lý thuyết kết hợp với nghiên cứu thực nghiệm:
+ Thiết kế các thuật toán ứng dụng.
+ Viết các chương trình cho các bài toán ứng dụng cụ thể.
+ Chạy thử nghiệm và lưu trữ các kết quả đạt được, đánh giá lại kết quả.
a. Về mặt lý thuyết
– Nghiên cứu được về lý thuyết đồ thị và các thuật toán trên đồ thị từ đó bồi dưỡng học sinh giỏi bộ môn Tin học.
– Hệ thống hóa và nhận dạng được các loại bài tập mà có thể sử dụng các thuật toán trên đồ thị.
– Cài đặt các thuật toán bằng ngôn ngữ lập trình Turbo Pascal.
b. Về mặt thực tiễn
Ngoài phần mở đầu và kết luận. Toàn bộ nội dung của luận văn được chia thành 3 chương như sau :
Chương 1: Trình bày nội dung nghiên cứu tổng quan về lý thuyết đồ thị: Các định nghĩa, các loại đồ thị, bậc của đồ thị, đường và chu trình trong đồ thị, đồ thị con, đồ thị bộ phận và tính liên thông trong đồ thị, các phương pháp biểu diễn đồ thị, đồ thị Euler, đồ thị nửa Euler và đồ thị Hamilton.
Chương 2: Giới thiệu một số thuật toán trên đồ thị:
+ Thuật toán tìm kiếm theo chiều sâu, tìm kiếm theo chiều rộng.
+ Tìm đường đi và kiểm tra tính liên thông.
+ Đồ thị có trọng số và bài toán tìm đường đi ngắn nhất: Thuật toán Ford – Bellman; thuật toán Dijkstra; thuật toán Floyd – đường đi ngắn nhất giữa tất cả các cặp đỉnh.
+ Thuật toán tìm luồng cực đại trong mạng.
Chương 3: Trong chương này giới thiệu một số bài toán, đồng thời hệ thống hóa, phân loại các dạng bài toán ứng dụng các thuật toán trên đồ thị. Ngoài ra, trong chương này cũng giới thiệu một số bài toán ứng dụng thực tế trong các kỳ thi học sinh giỏi, olympic.
CHƯƠNG 1 ĐẠI CƯƠNG VỀ LÝ THUYẾT ĐỒ THỊ
1.1. MỘT SỐ KHÁI NIỆM LIÊN QUAN ĐẾN ĐỒ THỊ
Định nghĩa 1.1: Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh của đồ thị. Các loại đồ thị khác nhau được phân biệt bởi kiểu và số lượng cạnh nối hai đỉnh nào đó của đồ thị.
Giả sử X là tập hữu hạn, không rỗng và U ⊆ X x X. Bộ G=<X,U> được gọi là đồ thị hữu hạn. Mỗi phần tử x∈X gọi là một đỉnh và mỗi phần tử u=(x,y)∈U gọi là một cạnh của đồ thị G=<X, U>.
Xét một cạnh u ∈ U khi đó tồn tại 2 đỉnh x, y ∈ X sao cho u = (x,y), ta nói rằng x nối với y hoặc x và y thuộc u.
x
y
u
– Nếu cạnh u = (x,y) mà x và y là hai đỉnh phân biệt thì ta nói x, y là hai đỉnh kề nhau.
– Nếu u = (x,x) thì u là cạnh có hai đỉnh trùng nhau ta gọi đó là một khuyên.
– Nếu u = (x,y) mà x, y là cặp đỉnh có phân biệt thứ tự hay có hướng từ x đến y thì u là một cung, khi đó x là gốc còn y là ngọn.
– Khi giữa cặp đỉnh (x,y) có nhiều hơn một cạnh thì ta nói những cạnh cùng cặp đỉnh là những cạnh song song hay là cạnh bội.
x
y
x
y
y
(a) (b) (c)
Hình 1.1. Ví dụ về cạnh (cung) đồ thị
(a). Tại đỉnh y có một khuyên (b). Một cung có hướng từ x sang y
(c). Cặp đỉnh (x,y) có 2 cạnh song song.
Ví dụ 1.1: Xét một mạng máy tính, có thể biểu diễn mạng này bằng một mô hình đồ thị trong đó mỗi máy là một đỉnh, giữa các máy được nối với nhau bằng các dây truyền, chúng tương ứng là các cạnh của đồ thị. Một mô hình mạng máy tính như hình 1.2 trong đó có các máy tính A, B, C, D tương ứng là các đỉnh, giữa 2 máy được nối trực tiếp với nhau thì tương ứng với 1 cặp đỉnh kề nhau.
A
B
C
D
Đồ thị đơn: Đồ thị G=<X, U> được gọi là đồ thị đơn nếu giữa hai đỉnh bất kỳ được nối với nhau bởi không quá một cạnh (cung), tức là đồ thị không có cạnh bội, không có khuyên. Hình 1.2 là một ví dụ về đơn đồ thị.
Đa đồ thị: Đồ thị G=<X, U> được gọi là đa đồ thị nếu nó có ít nhất một cặp đỉnh được nối với nhau bởi hai cạnh (cung) trở lên (hình 1.3a).
Giả đồ thị: Là đồ thị có ít nhất một khuyên, có thể chứa cạnh bội, cạnh đơn (hình 1.3b).
A
B
C
D
A
B
C
D
a) b)
Hình 1.3. Đa đồ thị, giả đồ thị
a. Đồ thị vô hướng
Đồ thị G=<X,U> được gọi là đồ thị vô hướng nếu tất cả các cạnh u ∈ U mà cặp đỉnh thuộc nó u = (x,y) (trong đó x, y ∈ X) không phân biệt thứ tự. Đồ thị vô hướng là đồ thị không có bất kỳ một cung nào.
b. Đồ thị có hướng
Đồ thị G=<X, U> được gọi là đồ thị có hướng nếu tất cả các cạnh u∈U mà cặp đỉnh thuộc nó u = (x, y) (trong đó x, y ∈ X) có phân biệt thứ tự. Đồ thị có hướng là đồ thị mà mọi u = (x, y) ∈ X đều là cung.
A
B
C
c. Đồ thị hỗn hợp
Đồ thị G=<X,U> vừa có cạnh vô hướng, vừa có cạnh có hướng thì nó được gọi là đồ thị hỗn hợp, loại đồ thị này rất ít khi được dùng tới.
Định nghĩa 1.2: Ta gọi bậc của đỉnh u trong đồ thị vô hướng G là số cạnh liên thuộc với nó và ký hiệu là deg(u).
Xét đồ thị trong hình 1.5 ta có :
f
e
g
d
c
b
a
deg(a) = 1, deg(b) = 4, deg(c) = 4, deg(d) = 1,
deg(e) = 3, deg(f) = 3, deg(g) = 0.
Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 gọi là đỉnh treo. Trong hình 1.5 đỉnh g là đỉnh cô lập, a và d là các đỉnh treo. Bậc của đỉnh có các tính chất sau:
Định lý 1.1: Giả sử G=<X,U> là đồ thị vô hướng với m cạnh. Khi đó
Chứng minh: Rõ ràng mỗi cạnh e=(u,v) được tính một lần trong deg(u) và một lần trong deg(v). Từ đó suy ra tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh.
Định nghĩa 1.3: Ta gọi bán bậc ra (bán bậc vào) của đỉnh u trong đồ thị có hướng là số cung của đồ thị đi ra khỏi nó (đi vào nó) và ký hiệu là deg+(u) (deg–(u)).
Xét đồ thị cho trong hình 1.6. Ta có :
d
e
c
b
a
deg–(a) = 1, deg–(b) = 2, deg–(c) = 2, deg–(d) = 2, deg–(e) = 2.
deg+(a) = 3, deg+(b) = 1, deg+(c) = 1, deg+(d) = 2, deg+(e) = 2.
Do mỗi cung (u,v) sẽ được tính một lần trong bán bậc vào của đỉnh v và một lần trong bán bậc ra của đỉnh u nên ta có:
Do tính chất, dạng biểu diễn có những nét đặc thù riêng biệt nên ta phân loại một số đồ thị thành các dạng đặc biệt sau:
F:\DỮ LIỆU COP CỦA CHỊ YẾN\DAI HOC DA NANG\KHOA HOC MAY TINH\BUI THI THU TRUC
