Bài tập học phần toán rời rạc 2

TRƯỜNG ðẠI HỌC SƯ PHẠM KỸ THUẬT HƯNG YÊN KHOA CÔNG NGHỆ THÔNG TIN BÀI TẬP HỌC PHẦN TOÁN RỜI RẠC 2 Trình ñộ ñào tạo Hệ ñào tạo : : ðại học Chính quy/Liên thông Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010 Trang 2 LỜI NÓI ĐẦU Có thể nói toán học rời rạc là môn tiên quyết và hiệu quả nhất ñể người học nâng cao tư duy toán học trong phân tích, thiết kế thuật toán và rèn luyện kỹ năng lập trình với những thuật toán phức tạp. Không những thế nó còn là “cửa ngõ” ñể người học có thể tiếp cận với rất nhiều modul trong khoa học máy tính (như Chương trình dịch, lý thuyết tính toán, Trí tuệ nhân tạo,...). Bài tập ñể củng cố và nâng cao kiến thức trong môn học này Về nội dung, bám sát với chương trình của nhà trường và hệ thống bài tập cũng ñược biên soạn theo các chương lý thuyết. Với mỗi chương sẽ ñược chia thành 4 phần: Phần A. Nhắc lại lý thuyết: tóm tắt các kiến thức cơ bản, các ví dụ và các lưu ý hữu ích, các kinh nghiệm trong khi lập trình Phần B. ðề bài tập: ñưa ra các loại bài tập khác nhau, với các mức ñộ khác nhau. Phần C. Bài tập mẫu: Hướng dẫn giải một số bài tiêu biểu trong phần B, có phân tích thuật toán và cài ñặt chương trình. Phần D. Bài tập tự giải: Người học thực hiện việc giải các bài tập này Mong rằng tài liệu này ñáp ứng ñược phần nào nhu cầu của học sinh, sinh viên. ðây là bản ñầu tiên chắc chắn còn rất nhiều sai sót. Nhóm tác giả mong nhận ñược sự ñóng góp của các thầy cô giáo, các bạn sinh viên và của tất cả những ai quan tâm tới lĩnh vực này. Hưng Yên, tháng 7 năm 2010 Bộ môn Công nghệ phần mềm Khoa Công nghệ thông tin Trường ñại học sư phạm kỹ thuật Hưng Yên Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010 Trang 3 MỤC LỤC Bài 1: Các khái niệm cơ bản của Lý thuyết ñồ thị ............................................................5 Mục tiêu ...................................................................................................................5 a. Nhắc lại lý thuyết ..................................................................................................5 b. ðề bài tập..............................................................................................................5 c. Hướng dẫn giải......................................................................................................6 d. Bài tập tự giải .......................................................................................................7 Bài 2: Biểu diễn ñồ thị trên máy tính..............................................................................10 Mục tiêu .................................................................................................................10 a. Nhắc lại lý thuyết ................................................................................................10 b. ðề bài tập............................................................................................................10 c. Hướng dẫn giải....................................................................................................10 d. Bài tập tự giải .....................................................................................................14 Bài 3: ðồ thị Euler .........................................................................................................15 Mục tiêu .................................................................................................................15 a. Nhắc lại lý thuyết ................................................................................................15 b. ðề bài tập............................................................................................................16 c. Hướng dẫn giải....................................................................................................16 d. Bài tập tự giải .....................................................................................................19 Bài 4: ðồ thị hamilton....................................................................................................20 Mục tiêu .................................................................................................................20 a. Nhắc lại lý thuyết ................................................................................................20 b. ðề bài tập............................................................................................................20 c. Hướng dẫn giải....................................................................................................20 d. Bài tập tự giải .....................................................................................................22 Bài 5: Thảo luận cài ñặt ñồ thị, các thuật toán liệt kê chu trình Euler và Hamilton. Thảo luận về bài tập lớn.................................................................................................23 Mục tiêu .................................................................................................................23 a. Nhắc lại lý thuyết ................................................................................................23 b. ðề bài tập............................................................................................................23 c. Hướng dẫn giải....................................................................................................23 d. Bài tập tự giải .....................................................................................................31 Bài 6 Thuật toán tìm kiếm trên ñồ thị và ứng dụng.........................................................34 Mục tiêu .................................................................................................................34 a. Nhắc lại lý thuyết ................................................................................................34 b. ðề bài tập............................................................................................................34 c. Hướng dẫn giải....................................................................................................34 d. Bài tập tự giải .....................................................................................................51 Bài 7: Cây và cây khung ................................................................................................52 Mục tiêu .................................................................................................................52 a. Nhắc lại lý thuyết ................................................................................................52 b. ðề bài tập............................................................................................................53 c. Hướng dẫn giải....................................................................................................54 d. Bài tập tự giải .....................................................................................................55 Bài 8: Thảo luận về cài ñặt thuật toán tìm cây khung nhỏ nhất trên ñồ thị ......................58 Mục tiêu .................................................................................................................58 Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010 Trang 4 a. Nhắc lại lý thuyết ................................................................................................58 b. ðề bài tập............................................................................................................58 c. Hướng dẫn giải....................................................................................................58 d. Bài tập tự giải .....................................................................................................70 Bài 9, 10: Bài toán tìm ñường ñi ngắn nhất ....................................................................71 Mục tiêu .................................................................................................................71 a. Nhắc lại lý thuyết ................................................................................................71 b. ðề bài tập............................................................................................................71 c. Hướng dẫn giải....................................................................................................73 d. Bài tập tự giải .....................................................................................................92 Bài 12: Bài toán luồng cực ñại trong mạng.....................................................................97 Mục tiêu .................................................................................................................97 a. Nhắc lại lý thuyết ................................................................................................97 b. ðề bài tập............................................................................................................98 c. Hướng dẫn giải....................................................................................................99 d. Bài tập tự giải ...................................................................................................101 Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010 Trang 5 Bài 1: Các khái niệm cơ bản của Lý thuyết ñồ thị Mục tiêu - Lưu trữ ñược ñồ thị trên máy tính theo những phương pháp khác nhau. - Cài ñặt ñược chương trình chuyển ñổi giữa các phương pháp. - Sinh viên có khả năng tự học. a. Nhắc lại lý thuyết - Hai ñỉnh x, y ñược gọi là cặp ñỉnh liên thông , nếu hoặc giữa x và y có ít nhất một xích nối với nhau, hoặc tồn tại ít nhất một ñường ñi từ y sang x. - ðồ thị vô hướng G(V,E) ñược gọi là ñồ thị liên thông, nếu mọi cặp ñỉnh của nó ñều liên thông. - ðồ thị có hướng G(V,E) ñược gọi là ñồ thị liên thông mạch, nếu mọi cặp ñỉnh của nó ñều liên thông. - Biểu diễn dạng hình học: Giả sử có ñồ thị G(V,E). Biểu diễn ñỉnh: lấy các ñiểm trên mặt phẳng hay trên không gian tương ứng với các phần tử của tập V và dùng ngay ký hiệu các phần tử này ñẻ ghi trên các ñiểm tương ứng. Biểu diễn cạnh: Nếu cạnh a với hai ñỉnh ñầu là x,y thì nó ñược biểu diễn bằng ñoạn thẳng hay một ñoạn cong nối giữa hai ñiểm x, y và không ñi qua các ñiểm tương ứng trong không gian. Biểu diễn cung: nếu cung a có ñỉnh ñầu là x, ñỉnh cuối là y, thì nó ñược biểu diễn bằng một ñoạn thẳng hoặc ñoạn cong ñược ñịnh hướng ñi từ x sang y và không qua các ñiểm tương ứng trung gian khác. Hình nhận ñược gọi là dạng biểu diễn hình học của ñồ thị G(V, E). ðôi khi người ta cũng gọi dạng biểu diễn hình học là một ñồ thị. b. ðề bài tập Bài 1 Cho G ñồ thị gồm 4 phần G1, G2, G3 và G4 như sau: a. Chỉ ra tập ñỉnh, cạnh(vô hướng,có hướng, khuyên,..) của mỗi ñồ thị ñã cho? Chỉ loại ñồ thị ñó? b. ðồ thị G, G1, G2, G3, G4 và G5 có liên thông ko? Nếu ñồ thị ko liên thông hãy chỉ ra các thành phần liên thông? Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010 Trang 6 c. ðồ thị G, G1, G2, G3, G4 và G5 có chu trình ko? Chỉ ra các chu trình của ñồ thị (nếu có)? c. Hướng dẫn giải Bài 1 a. Tên ñồ thị Tập ñỉnh V Tập cạnh E Loại ñồ thị G1 1,2,3,4 (1,2);(1,4);(2,3);(2,4);(3,4) Vô hướng G2 5,6,7 (5,6);(5,7);(6,7) Có hướng G3 8,9 (8,9) Vô hướng G4 0 G 1,2,3,4,5,6,7,8,9,0 (1,2);(1,4);(2,3);(2,4);(3,4); (8,9) (5,6);(5,7);(6,7) Hỗn hợp b. Tên ñồ thị Tính liên thông Tên thành phần liên thông G1 Có G1 G2 Có G2 G1 1 4 3 2 5 7 6 8 9 00 G2 G3 G4 Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010 Trang 7 G3 Có G3 G4 Có G4 G Không G1,G2,G3,G4 c. Tên ñồ thị Có chu trình? Tên chu trình G1 Có (1,2,4,1);(1,2,3,4,1);(2,3,4,2) G2 Không G3 Không G4 Không G Có (1,2,4,1);(1,2,3,4,1);(2,3,4,2) d. Bài tập tự giải Bài 1. Một quần ñảo có n( n ) hòn ñảo và hai hòn ñảo bất kì thuộc quần ñảo ñều có số ñầu mối ñường ngầm tới một trong nhưng hòn ñảo nầy ñều nhỏ hơn n. Chứng minh rằng từ một hòn ñảo tùy ý thuộc quần ñảo ta có thể ñi ñến một hòn ñảo bất kì khác của quần ñảo bằng ñường ngầm. Bài 2 Khi về nghỉ hè mỗi bạn học sinh của lớp 11A trường Lê Hồng Phong ñều trao ñổi ñịa chỉ với ít nhất một nửa số bạn trong lớp. Chứng minh rằng trong thời gian nghỉ hè mỗi bạn của lớp 11A ñều có thể báo tin trực tiếp hay gián tiếp cho các bạn trong lớp. Bài 3 Trong một cuộc họp có ñúng hai ñại biểu không que nhau và mỗi ñại biểu này có một số lẻ người que ñến dự. Chứng minh rằng luôn luôn có thể xếp một số ñại bieetr ngồi chen giữa hai ñại biể nói trên , ñể người ngồi giữa hai người mà anh( chị) ta quen. Hướng ñẫn: Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010 Trang 8 ðể giải ñược bài toán trên trước hết ta xây dựng các ñồ thị tương ứng, sau ñó vận dụng kết quả của ñịnh lý 4.1, hệ quả 4.1 và ñịnh lý 4.2 mà suy ra kết luận. Xuây dựng ñồ thị • ðỉnh: Lấy các ñiểm trong mặt phẳng hay trong không gian tương ứng với các hòn ñảo thuộc quần ñảo ( các bạn học sinh trong lớp 11A, các ñại biểu ñến họp). • Cạnh: Hai ñiểm x, y ñược nối bằng một cạnh khi và chỉ khi hai hòn ñảo x, y có ñường ngầm trực tiếp với nhau( các bạn x, y trao ñổi ñịa chỉ cho nhau, các ñại biểu x, y quen nhau) - ðồ thị nhân ñược ký hiệu bằng G1 , (G2 , G3) - ðồ thị G1 mô tả toàn bộ lưới ñường ngầm trong quần ñảo - ðồ thị G2 mô tả toàn bộ quan hệ trao ñổi ñịa chỉ trong lớp 11A - ðồ thị G3 mô tả toàn bộ quen biết trong các ñại biểu trong các ñại biểu ñến dự họp. Vận dụng kết quả các ñịnh lý ñể suy ra kết luận - Do hai hòn ñảo bất kì ñều có tổng số ñầu mối ñường ngầm không nhỏ hơn n, nên hai ñỉnh bất kì của ñồ thị G1 ñều có tổng bậc không nhỏ hơn n. Bởi vậy theo ñịnh lý 4.1. ñồ thị G1 liên thông, nên hai hòn ñảo bất kì có ñường hầm nối với nhau. - Vì mỗi bạn học sinh trong lớp 11A trao ñổi ñịa chỉ với ít nhất một nửa số bạn tron lớp, nên bậc của mỗi ñỉnh của G2 không nhỏ hơn một nửa số ñỉnh của ñồ thị. Khi ñó , theo hệ quả 4.1. ñồ thị G2 liên thông. Bởi vậy hai ñỉnh x, y ñều có xích nối với nhau. Khi ñó thông qua các bạn tương ứng với các ñỉnh thuộc xích , mà bạn tương ứng với ñỉnh x báo tin ñược cho tương ứng với ñỉnh y và ngược lại. - Hai ñại biểu không quen nhau, thì hai ñỉnh tương ứng không kề nhau. Mỗi ñại biểu này lại có một số lẻ người quen ñến họp, nên trong ñồ thị liên thông G3 có ñúng hai ñỉnh bậc lẻ và hai ñỉnh này lại không kề nhau. Khi dó, theo ñịnh lý 4.2, hai ñỉnh này liên thông nên có ít nhất một xich nối giữa hai ñỉnh này. Giả sử là một trong những mối xích nối giữa hai bậc lẻ này. Dựa vào ta sắp xếp các ñại biểu tương ứng ngồi giữa hai người mà anh chị quen. Bài 4 Cho G ñồ thị như sau: Chỉ ra tập ñỉnh, cạnh(vô hướng,có hướng, khuyên,..) của mỗi ñồ thị ñã cho? Chỉ loại ñồ thị ñó? ðồ thị có liên thông ko? Nếu ñồ thị ko liên thông hãy chỉ ra các Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010 Trang 9 thành phần liên thông? ðồ thị có chu trình ko? Chỉ ra các chu trình của ñồ thị (nếu có)? Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010 Trang 10 Bài 2: Biểu diễn ñồ thị trên máy tính Mục tiêu - Nêu ñược các cách biểu diễn ñồ thị và biểu diễn ñồ thị trên máy tính trên máy tính. - ðưa ra ñược ma trận kề, danh sách các cạnh, cung tương ứng với 1 ñồ thị cho trước. - Lưu trữ ñược ñồ thị trên máy tính theo những phương pháp khác nhau. - - Phân tích ñược bài toán thực tế tương ứng phần lý thuyết ñã học. - Sinh viên có khả năng tự học. a. Nhắc lại lý thuyết b. ðề bài tập Bài 1 Cho G ñồ thị gồm 4 phần G1, G2, G3 và G4 như sau: a. Biểu diễn các ñồ thị G,G1,G2,G3,G4 dưới dạng ma trận kề b. Biểu diễn các ñồ thị G,G1,G2,G3,G4 dưới dạng danh sách cạnh(cung) c. Biểu diễn các ñồ thị G,G1,G2,G3,G4 dưới dạng danh sách kề Bài 2 Cài ñặt chương trình nhập danh sách kề của ñồ thị từ bàn phím và ñưa danh sách ñó ra màn hình. c. Hướng dẫn giải Bài 1 G1 1 4 3 2 5 7 6 8 9 00 G2 G3 G4 Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010 Trang 11 Tên ñồ thị a. ma trận kề b. danh sách cạnh(cung) c.danh sách kề G1 1 2 3 4 1 0 1 0 1 2 1 0 0 1 3 0 0 0 1 4 1 1 1 0 Danh sách cạnh 1 2 1 4 2 3 2 4 3 4 1 2 4 2 1 4 3 4 4 1 2 3 G2 5 6 7 5 0 0 1 6 1 0 1 7 0 0 0 Danh sách cung 5 6 5 7 6 7 5 6 7 6 7 G3 8 9 8 0 1 9 1 0 Danh sách cạnh 8 9 8 9 9 8 G4 0 0 0 G 1 2 3 4 5 6 7 8 9 0 1 0 1 0 1 0 0 0 0 0 0 2 1 0 0 1 0 0 0 0 0 0 3 0 0 0 1 0 0 0 0 0 0 4 1 1 1 0 0 0 0 0 0 0 5 0 0 0 0 0 0 1 0 0 0 Danh sách cung 1 2 1 4 2 1 2 3 2 4 1 2 4 2 1 4 3 4 4 1 2 3 5 6 7 6 7 Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010 Trang 12 6 0 0 0 0 1 0 1 0 0 0 7 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 1 0 9 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 3 2 3 4 4 1 4 2 4 3 5 6 5 7 6 7 8 9 9 8 0 Bài 2 Chương trình nhập danh sách kề của ñồ thị từ bàn phím và ñưa danh sách ñó ra màn hình Phân tích bài toán : Trong rất nhiều thuật toán làm việc với ñồ thị chúng ta thường xuyên phải thực hiện các thao tác: Thêm hoặc bớt một số cạnh. Trong trường hợp này Cấu trúc dữ liệu dùng ở trên là không thuận tiện. Khi ñó nên chuyển sang sử dụng danh sách kề liên kết (Linked Adjancency List) như mô tả trong chương trình nhập danh sách kề của ñồ thị từ bàn phím và ñưa danh sách ñó ra màn hình Chương trình minh họa : Program AdjList; Const maxV=100; Type link=^node; node=record Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010 Trang 13 v:integer; next:link; End; Var j,x,y,m,n,u,v:integer; t:link; Ke:array[1. .Vmax] of link; Begin Write(‘Cho so canh va dinh cua do thi:’); readln(m,n); (*Khoi tao*) for j:=1 to n do Ke[j]:=nil; for j:=1 to m do begin write(‘Cho dinh dau va cuoi cua canh ‘,j,’:’); readln(x,y); new(t); t^.v:=x, t^.next:=Ke[y]; Ke[y]:=t; new(t); t^.v:=y, t^.next:=Ke[x]; Ke[x]:=t; end; writeln(‘Danh sach ke cua cac dinh cua do thi:’); for J:=1 to m do begin writeln(‘Danh sachcac dinh ke cua dinh ‘,j,’:’); t:=Ke[j]; Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010 Trang 14 while t^.nextnil do begin write(t^.v:4); t:=t^.next; end; end; readln; End. d. Bài tập tự giải Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010 Trang 15 Bài 3: ðồ thị Euler Mục tiêu - Kiểm tra ñược một ñồ thị bất kỳ có là ñồ thị euler hay không. - Áp dụng ñược thuật toán tìm chu trình Euler, ñường Euler, với 1 ñồ thị cho trước. - Lưu trữ ñược ñồ thị trên máy tính theo những phương pháp khác nhau. Cài ñặt ñược chương trình chuyển ñổi giữa các phương pháp. - Cài ñặt ñược thuật toán Tìm chu trình Euler. - Cài ñặt ñược thuật toán duyêt ñồ thị duyệt theo chiều sâu hoặc duyệt theo chiều rộng. - Sinh viên có khả năng tự học. a. Nhắc lại lý thuyết - 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). Bài tập TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010 Trang 16 ðịnh lý ðồ thị (vô hướng) liên thông G là ñồ thị Euler khi và chỉ khi mọi ñỉnh của G ñều có bậc chẵn. Hệ quả ðồ thị liên thông G là nửa Euler (mà không là Euler) khi và chỉ khi có ñúng hai ñỉnh bậc lẻ trong G. Thuật toán vạch ñược một chu trình Euler trong ñồ thị liên thông G có bậc của mọi ñỉnh là chẵn theo thuật toán Fleury sau ñây. Xuất phát từ một ñỉnh bất kỳ của G và tuân theo hai quy tắc sau: 1. Mỗi khi ñi qua một cạnh nào thì xoá nó ñi; sau ñó xoá ñỉnh cô lập (nếu có); 2. Không bao giờ ñi qua một cầu, trừ phi không còn cách ñi nào khác. b. ðề bài tập