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

Chia sẻ: Hoang Diep | Ngày: | Loại File: PDF | Số trang:111

Thêm vào BST

Báo xấu

741
lượt xem 301
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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 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. Toán rời rạc là một lĩnh vực của toán học nghiên cứu các đối tượng rời rạc.Chúng ta sẽ sử dụng công cụ rời rạc khi phải đếm các đối tượng, khi nghiên cứu quan hệ giữa các tập rời rạc, khi phân tích các quá trình hữu hạn.Đồng thời tầm quan trọng của toán rời rạc...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài tập học phần toán rời rạc

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 : ð i h c H ñào t o : Chính quy/Liên thông
Giáo trình TOÁN R I R C 2 B môn Công ngh ph n m m - 2010 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. 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 Trang 1
Giáo trình TOÁN R I R C 2 B môn Công ngh ph n m m - 2010 M CL C Bài 1: Các khái ni m cơ b n c a Lý thuy t ñ th ..........................................................................4 M c tiêu...................................................................................................................................4 a. Nh c l i lý thuy t.................................................................................................................4 b. ð bài t p.............................................................................................................................4 c. Hư ng d n gi i ....................................................................................................................5 d. Bài t p t gi i ......................................................................................................................6 Bài 2: Bi u di n ñ th trên máy tính...............................................................................................9 M c tiêu...................................................................................................................................9 a. Nh c l i lý thuy t.................................................................................................................9 b. ð bài t p.............................................................................................................................9 c. Hư ng d n gi i ....................................................................................................................9 d. Bài t p t gi i ....................................................................................................................13 Bài 3: ð th Euler.........................................................................................................................14 M c tiêu.................................................................................................................................14 a. Nh c l i lý thuy t...............................................................................................................14 b. ð bài t p...........................................................................................................................15 c. Hư ng d n gi i ..................................................................................................................15 d. Bài t p t gi i ....................................................................................................................18 Bài 4: ð th hamilton ...................................................................................................................19 M c tiêu.................................................................................................................................19 a. Nh c l i lý thuy t...............................................................................................................19 b. ð bài t p...........................................................................................................................19 c. Hư ng d n gi i ..................................................................................................................19 d. Bài t p t gi i ....................................................................................................................21 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 .........................................................................................................................22 M c tiêu.................................................................................................................................22 a. Nh c l i lý thuy t...............................................................................................................22 b. ð bài t p...........................................................................................................................22 c. Hư ng d n gi i ..................................................................................................................22 d. Bài t p t gi i ....................................................................................................................30 Bài 6 Thu t toán tìm ki m trên ñ th và ng d ng.......................................................................33 M c tiêu.................................................................................................................................33 a. Nh c l i lý thuy t...............................................................................................................33 b. ð bài t p...........................................................................................................................33 c. Hư ng d n gi i ..................................................................................................................33 d. Bài t p t gi i ....................................................................................................................50 Bài 7: Cây và cây khung................................................................................................................51 M c tiêu.................................................................................................................................51 a. Nh c l i lý thuy t...............................................................................................................51 b. ð bài t p...........................................................................................................................52 c. Hư ng d n gi i ..................................................................................................................53 d. Bài t p t gi i ....................................................................................................................54 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 ...................................57 M c tiêu.................................................................................................................................57 a. Nh c l i lý thuy t...............................................................................................................57 b. ð bài t p...........................................................................................................................57 c. Hư ng d n gi i ..................................................................................................................57 d. Bài t p t gi i ....................................................................................................................69 Trang 2
Giáo trình TOÁN R I R C 2 B môn Công ngh ph n m m - 2010 Bài 9, 10: Bài toán tìm ñư ng ñi ng n nh t...................................................................................70 M c tiêu.................................................................................................................................70 a. Nh c l i lý thuy t...............................................................................................................70 b. ð bài t p...........................................................................................................................70 c. Hư ng d n gi i ..................................................................................................................72 d. Bài t p t gi i ....................................................................................................................91 Bài 12: Bài toán lu ng c c ñ i trong m ng ...................................................................................96 M c tiêu.................................................................................................................................96 a. Nh c l i lý thuy t...............................................................................................................96 b. ð bài t p...........................................................................................................................97 c. Hư ng d n gi i ..................................................................................................................98 d. Bài t p t gi i ..................................................................................................................100 Trang 3
Giáo trình TOÁN R I R C 2 B môn Công ngh ph n m m - 2010 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? Trang 4
Giáo trình TOÁN R I R C 2 B môn Công ngh ph n m m - 2010 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ó)? 1 2 5 8 00 3 6 G4 4 7 9 G1 G2 G3 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); H nh p (8,9) (5,6);(5,7);(6,7) 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 Trang 5
Giáo trình TOÁN R I R C 2 B môn Công ngh ph n m m - 2010 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: Trang 6
Giáo trình TOÁN R I R C 2 B môn Công ngh ph n m m - 2010 ð 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 iv 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 Trang 7
Giáo trình TOÁN R I R C 2 B môn Công ngh ph n m m - 2010 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ó)? Trang 8
Giáo trình TOÁN R I R C 2 B môn Công ngh ph n m m - 2010 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: 1 2 5 8 00 3 6 G4 4 7 9 G1 G2 G3 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 Trang 9
Giáo trình TOÁN R I R C 2 B môn Công ngh ph n m m - 2010 Tên ñ th a. ma tr n k b. danh sách c.danh sách k c nh(cung) G1 1234 Danh sách c nh 124 1 0101 12 214 2 1001 14 34 3 0001 23 4123 4 1110 24 34 G2 567 Danh sách cung 567 5 001 56 67 6 101 57 7 000 67 G3 89 Danh sách c nh 89 8 01 89 98 9 10 G4 0 0 0 G 1234567890 Danh sách cung 124 1 0101000000 12 214 2 1001000000 14 34 3 0001000000 21 4123 4 1110000000 23 567 5 0000001000 24 67 Trang 10
Giáo trình TOÁN R I R C 2 B môn Công ngh ph n m m - 2010 6 0000101000 32 89 7 0000000000 34 98 8 0000000010 41 0 9 0000000100 42 0 0000000000 43 56 57 67 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 Trang 11
Giáo trình TOÁN R I R C 2 B môn Công ngh ph n m m - 2010 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]; Trang 12
Giáo trình TOÁN R I R C 2 B môn Công ngh ph n m m - 2010 while t^.nextnil do begin write(t^.v:4); t:=t^.next; end; end; readln; End. d. Bài t p t gi i Trang 13
Giáo trình TOÁN R I R C 2 B môn Công ngh ph n m m - 2010 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). Trang 14
Giáo trình TOÁN R I R C 2 B môn Công ngh ph n m m - 2010 ð 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 Bài 1: ð th sau có là ñ th n a Euler hay ñ th Euler ko? Gi i thích? c. Hư ng d n gi i Bài 1: ð th sau có là ñ th n a Euler hay ñ th Euler ko? Gi i thích? Trang 15
Giáo trình TOÁN R I R C 2 B môn Công ngh ph n m m - 2010 b c a e d G1 ð th G1 là ñ th n a Euler Th t vây, các ñ nh a,b,e có b c là 2,4,4 là b c ch n, các ñ nh c và d có b c là 3 là b cl a b d c G2 ð th G2 là ñ th n a Euler Th t vây, các ñ nh c và d có b c là 2 là b c ch n, các ñ nh a và c có b c là 1 là b c l Trang 16
Giáo trình TOÁN R I R C 2 B môn Công ngh ph n m m - 2010 a b e d c f g G3 ð th G3 không là ñ th Euler Th t v y G3 có 3 ñ nh a,d và g có b c là 1 là b c l 1 5 2 4 3 G4 ð th G4 là ñ th n a Euler vì theo h qu .. Th t vây, các ñ nh 3,4,5 có b c là 2 là b c ch n, các ñ nh 1 và 2 có b c là 3 là b c l Bài 2 Trang 17
Giáo trình TOÁN R I R C 2 B môn Công ngh ph n m m - 2010 Xu t phát t u, ta có th ñi theo c nh (u,v) ho c (u,x), gi s là (u,v) (xoá (u,v)). T v có th ñi qua m t trong các c nh (v,w), (v,x), (v,t), gi s (v,w) (xoá (v,w)). Ti p t c, có th ñi theo m t trong các c nh (w,s), (w,y), (w,z), gi s (w,s) (xoá (w,s)). ði theo c nh (s,y) (xoá (s,y) và s). Vì (y,x) là c u nên có th ñi theo m t trong hai c nh (y,w), (y,z), gi s (y,w) (xoá (y,w)). ði theo (w,z) (xoá (w,z) và w) và theo (z,y) (xoá (z,y) và z). Ti p t c ñi theo c nh (y,x) (xoá (y,x) và y). Vì (x,u) là c u nên ñi theo c nh (x,v) ho c (x,t), gi s (x,v) (xoá (x,v)). Ti p t c ñi theo c nh (v,t) (xoá (v,t) và v), theo c nh (t,x) (xoá c nh (t,x) và t), cu i cung ñi theo c nh (x,u) (xoá (x,u), x và u). d. Bài t p t gi i Trang 18
Giáo trình TOÁN R I R C 2 B môn Công ngh ph n m m - 2010 Bài 4: ð th hamilton M c tiêu - Ki m tra ñư c m t ñ th b t kỳ có là ñ th Hamilton hay không. - Áp d ng ñư c thu t toán tìm chu trình Hamilton, ñư ng Hamilton, 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 Halmiton. - 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 - ð th Hamilton(n a Hamilton) là ñ th có ch a m t chu trình(ñư ng ñi) Hamilton Hay ðư ng ñi (x[1],x[2],…,x[n]) ñư c g i là ñư ng ñi Hamilton n u x[i]≠x[j] (1≤i