Tài liệu

Bài tập toán rời rạc có lời giải

Bài viết này mình tổng hợp lại đề thi toán rời rạc 1

Download Bài tập toán rời rạc có lời giải

Link down Bài tập toán rời rạc có lời giải

Bai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L BÀI TẬP CHƯƠNG I Bài 1: Số mã vùng thiết yếu nhỏ nhất là bao nhiêu để đảm bảo 25 triệu máy điện thoại khác nhau. Mỗi điện thoại sở hữu 9 chữ số mang dạng 0XX-8XXXXX sở hữu X nhận giá trị trong khoảng 0 đến 9. Giải: Vì số mã vùng có dạng: 0XX-8XXXXX, có X nhận những trị giá trong khoảng 0 đến 9 (10 số), có 07 ký tự X do vậy sẽ với 107 trường hợp. vì thế, theo nguyên lý Dirichlet với 10 triệu máy điện thoại thì số mã vùng ⎤ 25.000.000 ⎡ = ]2,5[ = 3 . Vậy số mã vùng cần phải có thỏa yêu cầu bài toán là 3. cấp thiết là: ⎥ ⎦ 10.000.000 ⎢ ⎣ Bài 2: Biển số xe gồm 8 ký tự, dạng NN-NNNN-XN, tỉ dụ 75_1576_F1. hai số đầu là mã tỉnh, X là chữ cái (26 chũ cái). N gồm các số 0, một, …, 9. Hỏi 1 tỉnh nào đó cần đăng ký cho 10 triệu xe thì cần bao lăm serial (X). Giải Bài toán này sở hữu 02 bí quyết hiểu: serial ở đây mang thể là 02 ký tự NN trước tiên hoặc là 02 ký tự XN cuối cùng. bí quyết hiểu 1: (serial là 02 ký tự XN cuối cùng). 2 số NN đầu là mã tỉnh giấc, do nhà nước quy định nên ko ảnh hưởng đến kết quả bài toán. Sáu ký tự còn lại mang 5 ký tự là N, tương tự có 10 5 trường hợp. Theo nguyên lý Dirichlet, số serial ⎤10.000.000 ⎡ = 100 . Điều này ko hợp lý vì số ký tự chữ cái chỉ là 26. Do X tối thiểu phải thỏa mãn: ⎥ ⎦ 100.000 ⎢ ⎣ vậy, ví như bài toán sửa lại là 1 triệu bảng số xe thì kết quả hợp lý hơn, lúc ấy số serial là: ⎤1.000.000 ⎡ ⎥ 100.000 ⎢ = 10 . ⎦ ⎣ cách thức hiểu 2: (serial là 02 ký tự NN đầu tiên) Bốn ký tự NNNN sẽ với 104 trường hợp, 02 ký tự XN sẽ sở hữu 2610 = 260 trường hợp. Theo quy tắc nhân, tổng số trường hợp sẽ là: 104260 = hai.600.000. bởi thế, theo nguyên lý Dirichlet, số serial tối thiểu phải là: ⎤ 10.000.000 ⎡ ⎥ 2.600.000 ⎢ = ]3,84[ = 4 . ⎦ ⎣ Vậy cần 04 số serial để đăng ký đủ cho 10 triệu xe. Bài 3: sở hữu bao lăm xâu nhị phân với độ dài 10: a. khởi đầu bằng 00 hoặc kết thúc bằng 11. b. khởi đầu bẳng 00 và chấm dứt bằng 11. Giải a. bắt đầu bằng 00 hoặc chấm dứt bằng 11. Xâu nhị phân khởi đầu bằng 00 sở hữu dạng: 00.xxxx.xxxx. Ký tự x có thể là 0 hoặc 1, với 8 ký tự x vì vậy mang 2 8 xâu. Xâu nhị phân chấm dứt bằng 11 mang dạng: xx.xxxx.xx11. Tương tư ta cũng tính được sở hữu 28 xâu. Xâu nhị phân bắt đầu bằng 00 và chấm dứt bằng 11 với dạng 00.xxxx.xx11. tương tự như trên, ta cũng tính được mang hai 6 xâu. Vậy số xâu nhị phân bắt đầu bằng 00 hay chấm dứt bằng 11 là: 1 BT Toan roi rac
Bai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L n = hai * hai 8 − 2 6 = 512 − 64 = 448 xâu. b. khởi đầu bằng 00 và chấm dứt bằng 11. Xâu nhị phân thỏa mãn đề bài phải sở hữu dạng: 00.xxxx.xx11. 2 ký tự đầu và 02 ký tự cuối là ko đổi, vì thế chỉ còn 06 ký tự ở giữa. thành ra số xâu nhị phân thỏa mãn đề bài là: 26 xâu. Bài 4: Khóa 29 CNTT với 150 SV học NNLT Java, 160 SV hoc Delphi, 40 SV học cả 2 môn trên. a. sắm toàn bộ SV của khóa 29 biết rằng SV nào cũng phải học ít nhất 01 môn. b. Biết tổng số SV là 285, hỏi mang bao nhiêu SV ko học Java hoặc Delphi. Giải Gọi J: SV học Java D: SV học Delphi a. Số SV của khóa 29 là: n1 = J U D = J + D − J I D = 150 + 160 − 40 = 270 SV b. Câu b mang 02 phương pháp hiểu: cách 01: không học ít nhất 01 môn. Số SV ko học Java hoặc Delphi là (áp dụng nguyên lý bù trừ) ta tính được: n hai = n − J I D = 285 − 40 = 245 SV bí quyết 02: không học Java cũng chẳng học Delphi: Theo cách hiểu này, áp dụng nguyên lý bù trừ ta tính được số SV như sau: n2 = J U D = n − J − D + J I D = 285 − 150 − 160 + 40 = 15 SV ‘ Bài 5: Mỗi người sử dụng máy tính tiêu dùng password với 6 -> 8 ký tự. những ký tự sở hữu thể là chữ số hoặc chữ dòng, mỗi password phải mang ít ra 01 chữ số. sắm tổng số password có thể mang. Giải Bài toán này cũng với thể được hiểu theo 02 phương pháp. cách thức 01: phân biệt chữ thường với chữ hoa. Chữ chiếc thường: 26 Chữ dòng hoa: 26 Chữ số: 10 vì thế, tổng cộng có 26 + 26 + 10 = 62 ký tự khác nhau. giả dụ password sở hữu n ký tự. Tổng số trường hợp: 62 n Số password ko với chữ số: 52 n Suy ra số password với ít ra 01 chữ số: nn = 62 n − 52 n vận dụng cho những trường hợp n = 6, 7, 8. Tổng số password thỏa bắt buộc đề bài là: n = n6 + n7 + n8 = 626 − 526 + 627 − 527 + 628 − 528 = 167.410.949.583.040 bí quyết 02: ko phân biệt chữ thường mang chữ hoa: phương pháp khiến hoàn toàn như vậy, nhưng thay vì sử dụng các số 62 và 52 thì ở đây dùng 02 số: 36 và 26. Kết quả sẽ là: n = n6 + n7 + n8 = 366 − 266 + 367 − 267 + 368 − 268 = hai.684.483.063.360 Bài 6: mang n lá thư bỏ vào n phong bì. Hỏi xác suất để xảy ra trường hợp ko mang lá thư nào bỏ đúng được phong bì của nó. Giải hai BT Toan roi rac
Bai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L Vì sở hữu n bao thơ và n bao thơ nên với toàn bộ N = n! bí quyết bỏ thư khác nhau. Để đếm số cách bỏ thư sao cho không lá thư nào đúng địa chỉ, ta ứng dụng nguyên lý bù trừ: N = n! − N1 + N2 − … + (−1)nNn, trong ấy Nm (1 ≤ m ≤ n) là số bí quyết bỏ thư sao cho với ít nhất m lá thư đúng liên hệ, Nm là số cách thức lấy m lá thư từ n lá, sở hữu mỗi phương pháp lấy m lá thư, có (n-m)! phương pháp bỏ để m lá thư này đúng liên hệ, như vậy: n! 11 một vì thế N = n!(1 − + − … + (−1)n ), m Nm = C n (n – m)! = k! 1! 2! n! NN 111 1 Dođó xác suất thỏa bài toán: p = = = 1 − + – +…+(-1) k N n! 1! 2! 3! k! Bài 7: Chỉ ra rằng ví như chọn 5 số từ tập 8 số 1, 2, …, 7, 8 thì bao giờ cũng có chí ít 01 cặp số mang tổng là 9. Giải trong khoảng 8 số ở trên, ta chia thành 04 cặp: 1, 8, 2, 7, 3, 6, 4, 5 và tổng của mỗi cặp đều bằng 9. như vậy, đề bài sẽ phát triển thành chọn 5 số trong khoảng 4 cặp số trên. Theo nguyên lý Dirichlet, phải có ít nhất 01 cặp số được chọn hết. Vậy bài toán đã được chứng minh. Bài 8: Chứng minh rằng trong bất kỳ một hàng ngũ 27 từ tiếng Anh nào cũng với chí ít 2 từ bắt đầu từ cùng 01 chữ cái. Giải Bảng chữ cái của tiếng anh gồm 26 ký tự: a, b, c, …, x, y, z. Vì có 27 trong khoảng tiếng Anh và mỗi trong khoảng khởi đầu bằng 01 chữ chiếc nên theo nguyên lý Dirichlet phải có ít nhất 02 trong khoảng khởi đầu bằng cùng 01 chữ loại. Bài 9: nhu yếu bao lăm SV ghi tên vào lớp TRR để chắc chắn mang ít ra 65 SV đạt cộng điểm thi, ví thử thang điểm thi gồm 10 bậc. Giải ] 10[ = 65 . bởi thế Gọi n là số sinh viên tối thiểu thỏa mãn đề bài, theo nguyên lý Dirichlet thì n n = 10 * 64 + một = 641 SV. Bài 10: mua hệ thức truy hồi và cho điều kiện đầu để tính số những xâu nhị phân mang độ dài n và ko sở hữu 2 số 0 liên tiếp. sở hữu bao nhiêu xâu nhị phân như thế có độ dài bằng 5. Giải có xâu nhị phân mang độ dài n, ta chia thành 02 trường hợp: ví như ký tự rút cuộc là 1 thì ký tự trước đấy (ký tự thứ n – 1) sở hữu thể là 1 hay là 0 đều được. nếu ký tự rốt cuộc là 0 thì ký tự trước đó (ký tự thứ n – 1) chỉ sở hữu thể là 1 (vì nếu là 0 thì vi phạm đề nghị bài toán) nhưng ký tự trước đó nữa (thứ n – 2) mang thể là 0 hay 1 đều được. trong khoảng 02 trường hợp trên ta suy ra được: f n = f n −1 + f n − 2 các điều kiện đầu: f1 = hai , f 2 = 3 sở hữu 13 xâu nhị phân có độ dài 5 và không mang hai số 0 liên tiếp. 3 BT Toan roi rac
Bai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L Bài 11: ⎧f =0 Dãy các số Fibonacci thõa f n = f n −1 + f n − hai , cho điều kiện đầu: ⎨ 0 . Hãy tìm hệ thức truy hỏi ⎩ f1 = 1 hồi của Fibonacci. Giải Phương trình đặc trưng: x 2 − x − 1 = 0 1+ 5 1− 5 sở hữu các nghiệm là: r1 = và r2 = . hai 2 n n ⎛ 1+ 5 ⎞ ⎛ 1− 5 ⎞ cho nên các số Fibonacci tổng quát sẽ với dạng: f n = α1 ⎜ ⎟ + α2 ⎜ ⎜ ⎜ ⎟ ⎟ ⎟ ⎝2⎠ ⎝2⎠ ⎧ 1 ⎧α1 + α 2 = 0 ⎪α1 = 5 ⎧ f0 = 0 ⎪ ⎪ ⇒ ⎨ ⎛ 1+ 5 ⎞ ⎛ 1− 5 ⎞ ⇒⎨ có các điều kiện ban sơ : ⎨ ⎪α1 ⎜ hai ⎟ + α hai ⎜ hai ⎟ = một ⎪α = −1 ⎩ f1 = một ⎜ ⎟ ⎜ ⎟ ⎩⎝ ⎠ ⎝ ⎠ ⎪2 ⎩ 5 bởi vậy các số Fibonacci được cho bởi công thức như sau: n n 1 ⎛ 1+ 5 ⎞ một ⎛ 1− 5 ⎞ fn = ⎜ 2 ⎟ − 5⎜ 2 ⎟ ⎜ ⎟ ⎜ ⎟ 5⎝ ⎠ ⎝ ⎠ Bài 12: sắm nghiệm của hệ thức tróc nã hồi sau: a n = 2a n −1 + 5a n − hai − 6a n −3 trong đó các điều kiện đầu là: a 0 = 7 , a1 = −4 , a hai = 8 . Giải Phương trình đặc trưng x 3 − hai x 2 − 5 x + 6 = 0 ⇔ ( x − 1)( x hai − x − 6) = 0 ⎧ x0 = một ⎪ những nghiệm của phương trình đặc trưng: ⎨ x1 = −2 ⎪x = 3 ⎩2 vì thế, hệ thức truy tìm hồi sẽ có dạng: a n = α 11n + α hai (−2) n + α 3 3 n với các điều kiện đầu được cho: a 0 = 7 , a1 = −4 , a hai = 8 . Ta mang hệ phương trình như sau: ⎧7 = α một + α hai + α 3 ⎧α một = 5 ⎪ ⎪ ⎨− 4 = α 1 − 2α hai + 3α 3 ⇒ ⎨α hai = 3 ⎪8 = α + 4α + 9α ⎪α = −1 ⎩3 ⎩ một hai 3 Vậy nghiệm của hệ thức truy tìm hồi là: a n = 5 + 3(−2) n − 3 n Bài 13: tìm hệ thức truy hỏi hồi và rn . sở hữu rn là số miền của mặt phẳng bị phân chia bởi n các con phố thẳng. Biết rằng ko sở hữu hai trục đường thẳng nào song song và cũng ko sở hữu 03 đường thẳng nào đi qua cộng 1 điểm. Giải 4 BT Toan roi rac
Bai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L mang n trục đường thẳng, theo đề bài thì trục đường thẳng thứ n sẽ cắt n – một con đường thẳng còn lại tại n – một điểm, tức là sẽ cắt n – một + một = n phần mặt phẳng. cho nên, số phần mặt phẳng tăng lên là n. từ đó, ta sở hữu được hệ thức truy tìm hồi: rn = rn −1 + n . các điều kiện đầu là: n = 0: r0 = 1. n = 1: r1 = 2. BÀI TẬP CHƯƠNG II Bài 14 Chứng minh rằng trong 1 đơn đồ thị luôn với ít nhất 02 đỉnh sở hữu cộng bậc. Giải Trong đồ thị đơn, số bậc tối đa cung TH1: giả tỉ đồ thì ko mang đỉnh treo, do vậy số bậc tối thiểu của những đỉnh là 1, số bậc tối đa của các đỉnh là n-1 (vì là đơn đồ thị). sở hữu n đỉnh, số bậc của những đỉnh đi trong khoảng một tới n-1 (n-1) trị giá. do đó theo nguyên lý Dirichlet phải có ít ra 02 đỉnh có cùng bậc. TH2: giả sử đồ thị sở hữu chí ít 01 đỉnh treo, lúc ấy số bậc tối thiểu của các đỉnh là 0, và số bậc tối đa chỉ là n-2 (vì là đơn đồ thị, song song với đỉnh treo). sở hữu n đỉnh, số bậc của các đỉnh chỉ mang thể đi từ 0 đến n-2 (n-1) trị giá. vì thế theo nguyên lý Dirichlet phải sở hữu ít nhất 02 đỉnh sở hữu cùng bậc. Bài 15: Tính tổng số bậc của K n (đơn đồ thị đủ). Giải sở hữu đồ thị đủ thì mỗi đỉnh đều nối mang các đỉnh còn lại. vì vậy, lúc với n đỉnh thì mỗi đỉnh đều nối sở hữu n -1 đỉnh còn lại, tức là bậc của mỗi đỉnh đều bằng n – một. Vậy, tổng số bậc của cả đồ thị là: n*(n – 1) bậc. II. các bài tập trong giấy rà soát lần 1. Bài 16: (giống bài 12 phần trước). sắm nghiệm của hệ thức truy tìm hồi sau: a n = 2a n −1 + 5a n − hai − 6a n −3 trong đó những điều kiện đầu là: a 0 = 7 , a1 = −4 , a hai = 8 . Giải Phương trình đặc thù x 3 − 2 x 2 − 5 x + 6 = 0 ⇔ ( x − 1)( x 2 − x − 6) = 0 ⎧ x0 = một ⎪ các nghiệm của phương trình đặc trưng: ⎨ x1 = −2 ⎪x = 3 ⎩2 vì vậy, hệ thức truy nã hồi sẽ có dạng: a n = α 11n + α 2 (−2) n + α 3 3 n có các điều kiện đầu được cho: a 0 = 7 , a1 = −4 , a hai = 8 . Ta với hệ phương trình như sau: ⎧7 = α một + α hai + α 3 ⎧α một = 5 ⎪ ⎪ ⎨− 4 = α một − 2α 2 + 3α 3 ⇒ ⎨α hai = 3 ⎪8 = α + 4α + 9α ⎪α = −1 ⎩3 ⎩ 1 2 3 Vậy hệ thức truy tìm hồi là: a n = 5 + 3(−2) n − 3 n Bài 17: 5 BT Toan roi rac
Bai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L Trong tổng số 2504 sinh viên của 1 khoa công nghệ thông báo, mang 1876 theo học môn NNLT Pascal, 999 học môn tiếng nói Fortran và 345 học môn tiếng nói C. tuy nhiên còn biết 876 sinh viên học cả Pascal và Fortran, 232 học cả Fortran và C, 290 học cả Pascal và C. nếu như 189 sinh viên học cả 03 môn Psacal, Fortran và C thì trong trường hợp ấy có bao nhiêu sinh viên không học môn nào trong cả 03 môn kể trên. Giải Gọi P: là tập gồm những SV học Pascal F: là tập gồm những SV học Fortran C: là tập gồm những SV học C N: là tổng số SV (2504 SV) Gọi K là số SV học chí ít 01 môn Theo nguyên lý bù trừ, ta có: K = PU F UC = P + F + C − PI F − F IC − C I P + PI F IC K = 1876 + 999 + 345 − 876 − 232 − 290 + 189 = 2011 ⇒ K = N − K = 2504 − 2011 = 493 SV Vậy sở hữu 493 SV ko học môn nào trong 03 môn: Pascal, Fortran và C. Bài 18: Hãy tậu số đỉnh, số cạnh, số bậc của mỗi đỉnh và xác định những đỉnh cô lập, đỉnh treo, ma trận liền kề, ma trận liên thuộc trong mỗi đồ thị vô hướng sau: Giải Câu 18.1. Số đỉnh: 8 Số cạnh: 11 Đỉnh cô lập: D Đỉnh treo: không có Tên đỉnh a b C d e g h i Bậc của định 3 hai 4 0 5 3 2 3 ⎛0 1⎞ 0 1 0 1 0 0 ⎜ ⎟ ⎜0 0⎟ 0 0 0 một 0 1 ⎜0 1⎟ 0 0 0 1 1 0 ⎜ ⎟ ⎜0 0⎟ 0 0 0 0 0 0 Ma trận liền kề: , quy trình đỉnh: a, b, c, d, e, g, h, i ⎜ 0⎟ ⎜1 1 1 0 0 2 0 ⎟ ⎜0 0⎟ 0 1 0 2 0 0 ⎜ ⎟ ⎜0 1 0 0 0 0 0 1⎟ ⎜1 0⎟ ⎝ ⎠ 0 một 0 0 0 1 6 BT Toan roi rac
Bai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L ⎛ e11 ⎞ e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 ⎜ ⎟ ⎜A 0⎟ một 1 một 0 0 0 0 0 0 0 ⎜B 0⎟ 0 0 0 1 1 0 0 0 0 0 ⎜ ⎟ ⎜C 0⎟ 1 0 0 0 0 một 1 1 0 0 ⎜ 0⎟ Ma trận liên thuộc: ⎜D 0 0 0 0 0 0 0 0 0 0 ⎟ ⎜E 0⎟ 0 một 0 một 0 1 0 0 1 1 ⎜ ⎟ ⎜G 0 0 0 0 0 0 một 0 một 1 0⎟ ⎜H 1⎟ 0 0 0 0 một 0 0 0 0 0 ⎜ ⎟ ⎜I 1⎟ ⎝ ⎠ 0 0 1 0 0 0 0 1 0 0 = (b, h) ⎧e1 = (a, c) ⎧e5 ⎧e9 = (e, g ) ⎪e ⎪e = (a, e) = ( c , e) ⎪2 ⎪6 ⎪ ⎨e10 = (e, g ) trong đó: ⎨ ⎨ ⎪e3 = (a, i ) = (c , g ) ⎪e7 ⎪e = (h, i ) ⎩ 11 ⎪e4 = (b, e) ⎪e8 = (c, i ) ⎩ ⎩ a Câu 18.2. b c d e Số đỉnh: 5 Số cạnh: 12 Đỉnh cô lập: ko mang Đỉnh treo: ko có Tên đỉnh a b c d e Bậc của định 6 5 5 5 3 ⎛1 1⎞ 3 0 0 ⎜ ⎟ ⎜3 1⎟ 0 0 1 ⎜0 0 ⎟ , quy trình đỉnh: a, b, c, d, Ma trận liền kề: 0 một 3 ⎜ ⎟ ⎜0 1⎟ 1 3 0 ⎜1 0⎟ ⎝ ⎠ một 0 1 ⎛ e12 ⎞ e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 ⎜ ⎟ ⎜a một 0⎟ 1 1 1 1 0 0 0 0 0 0 ⎜b 0 0⎟ 1 1 1 0 một 1 0 0 0 0 Ma trận liên thuộc: ⎜ ⎟ ⎜c 0 0⎟ 0 0 0 0 0 0 1 1 một 1 ⎜d 0 1⎟ 0 0 0 0 0 một 0 một 1 một ⎜ ⎟ ⎜e 0 1⎟ ⎝ ⎠ 0 0 0 1 1 0 0 0 0 0 ⎧e5 = (a, e) ⎧e9 = (c, d ) ⎧e1 = (a, a) ⎪e = (b, e) ⎪e = (c, d ) ⎪e = (a, b) ⎪2 ⎪6 ⎪ 10 trong đó: ⎨ ⎨ ⎨ ⎪e3 = (a, b) ⎪e7 = (b, d ) ⎪e11 = (c, d ) ⎪e4 = (a, b) ⎪e8 = (c, c) ⎪e12 = (d , e) ⎩ ⎩ ⎩ 7 BT Toan roi rac
Bai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L Bài 19: 2 đơn đồ thị với ma trận liền kề sau đây mang là đẳng cấu không? ⎛0 ⎛0 1 0 1⎞ một 1 1⎞ ⎜ ⎜ ⎟ ⎟ ⎜1 ⎜1 0 0 1⎟ 0 0 1⎟ ⎜0 ⎜1 0 0 1⎟ 0 0 1⎟ ⎜ ⎜ ⎟ ⎟ ⎜1 ⎜1 một 1 0 ⎟, 1 1 0 ⎟. ⎝ ⎝ ⎠ ⎠ Giải Dựa vào ma trận liền kề của 2 đơn đồ thị ta có thể vẽ lại những đồ thị bằng hình vẽ: V1 U1 U2 V2 U4 U3 V4 V3 Theo hình vẽ của hai đơn đồ thị ta thấy chúng không với cộng số cạnh, 1 bên sở hữu 4 cạnh và 1 bên với 5 cạnh. Vậy hai đồ thị sở hữu ma trận liền kề đã cho ở trên không đẳng cấu. Bài toán này sở hữu thể không cần vẽ hình lại cũng được, trong khoảng ma trận kề ta cũng có thể thuận tiện xác định được số cạnh của mỗi đồ thị tuần tự là 4 và 5. do đó chúng chẳng thể đẳng cấu. Bài 20: Xét xem các đồ thị cho sau đây có đẳng cấu mang nhau không? Giải a. Hình 01. u1 v2 v1 u2 v6 v5 u3 u4 u5Hai đồ thị cho ở trên có:u6 đỉnh, số cạnh, tổng số bậcvvà số bậc củav3 ỗi đỉnh bằng nhau. đặc thù, 4 số m những đỉnh của đồ thị thứ nhất và thứ hai lúc sắp theo thứ tự sau đây thì chúng hoàn toàn tương đương về mọi mặt: Đồ thị thứ nhất u2 u3 u4 u5 u6 u1 Đồ thị thứ 2 v5 v6 v3 v2 v1 v4 8 BT Toan roi rac
Bai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L Số bậc của mỗi đỉnh 3 4 4 3 5 5 Chính thành ra, 2 đồ thị trên là đẳng cấu. b. Hình 02. u3 u1 u2 v1 v2 v6 v3 u4 u5 u6 v5 v4 2 đồ thị với hướng cho ở trên lúc sắp theo thứ tự sau đây về các đỉnh thì chúng tương đương về rất nhiều những mặt: trong khoảng số đỉnh, tổng số bậc, bậc vào, bậc ra của mỗi đỉnh, tổng số cạnh, thứ tự và chiều của các cạnh đều tương ứng: Đồ thị thứ nhất u2 u3 u4 u5 u6 u1 Đồ thị thứ hai v3 v5 v1 v2 v4 v6 Bậc vào: deg-(X) 1 hai 1 hai 2 1 Bậc ra: deg+(X) 2 một 2 một 1 hai vì vậy, hai đồ thị có hướng ở trên là đẳng cấu có nhau. Bài 21: (3.1) Cho G là đồ thị với v đỉnh và e cạnh, còn m và M tương ứng là bậc nhỏ nhất và lớn nhất các 2e đỉnh của G. Chứng tỏ rằng: m ≤ ≤M v Giải Vì m và M tương ứng là bậc nhỏ nhất và lớn nhất những đỉnh của G, vì vậy ta thuận tiện mang được: ⎧v ⎪ ∑ deg( v i ) ≥ v .m ⎪ i =1 m ≤ deg( v i ) ≤ M , i = 1, v ⇔ ⎨ v ⎪ ⎪∑ deg( v i ) ≤ v .M ⎩ i =1 ⎧2e ≥ vm . 2e ⇔⎨ ⇔vm ≤ 2e ≤ vM ⇔ m ≤ ≤ M . . ⎩2e ≤ vM (đpcm) . v Bài 22: (3.2) Chứng minh rằng ví như G là đơn đồ thị phân đôi mang v đỉnh và e cạnh, lúc đấy chứng minh bất v2 e ≤ (1) đẳng thức sau đây: 4 Giải 9 BT Toan roi rac
Bai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L Gọi n1, n2 lần lượt là số đỉnh của mỗi phần (n1 + n2 = v). Vì là đơn đồ thị phân đôi nên số cạnh K n1 , n2 đa dạng nhất lúc nó là đơn đồ thị phân đôi đủ, tức là: . n = n1 × n2 ⇔ e ≤ n1n2 (2) . khi đó, số cạnh phổ biến nhất sẽ là: Ta tiện lợi có được: (n1 − n2 ) 2 ≥ 0 ⇔ n12 − 2n1n2 + n2 ≥ 0 ⇔ n12 + 2n1n2 + n2 ≥ 4n1n2 2 2 (n1 + n2 )2 v2 ⇔ ≥ n1n2 ≥ e ⎯⎯ → ≥e (2) (đpcm). 4 4 Bài 23: (3.4) Hãy vẽ những đồ thị vô hướng biểu diễn bởi những ma trận sau: ⎛0 một 4⎞ 3 0 ⎛1 hai 0 1⎞ ⎜ ⎟ ⎛1 2 3⎞ ⎜ ⎟ ⎜1 hai 1 3 0⎟ ⎜ ⎟ 2 0 3 0⎟ b. ⎜ c. ⎜ 3 1 1⎟ a. ⎜ 2 0 4 ⎟ một 0 ⎜0 3 1 1⎟ ⎜ ⎟ ⎜3 4 0⎟ ⎜ ⎟ ⎝ ⎠ ⎜0 3 0 0 2⎟ ⎝1 0 một 0⎠ ⎜4 0 3⎟ ⎝ ⎠ 1 hai Giải A B C A C D B h.a h.b A B C D E h.c Bài 24: (3.6) tìm ma trận liền kề cho các đồ thị sau: a.Kn b.Cn c.Wn d.Km,n e.Qn Giải 10 BT Toan roi rac
Bai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L ⎛ 0 1 0 0 … 0 1 ⎞ ⎛0 1⎞ một 1 một … 1 ⎜ ⎟ ⎜ ⎟ ⎜ 1 0 1 0 … 0 0 ⎟ ⎜1 0 một 1 … một 1⎟ ⎜ 0 một 0 một … 0 0 ⎟ ⎜1 1⎟ một 0 1 … 1 ⎜ ⎟ ⎜ ⎟ b.C n : ⎜ 0 0 1 0 … 0 0 ⎟ a .K n : ⎜ 1 1 1 0 … 1 1⎟ ⎜ … … … … … … … ⎟ ⎜ … … ⎟ … … … … … ⎜ ⎟ ⎜ ⎟ ⎜ 0 0 0 0 … 0 một ⎟ ⎜1 1⎟ 1 1 một … 0 ⎜ 1 0 0 0 … 1 0 ⎟ ⎜1 0⎟ ⎝ ⎠ ⎝ ⎠ 1 1 một … một ⎛ 6474 6 n 8 ⎞ 8 474 m ⎛0 1⎞ một 0 0 … một ⎜ ⎧ 0 … 0 1 … một ⎟ ⎜ ⎟ ⎜⎪ ⎟ ⎜1 0 một 0 … 0 1⎟ ⎜ ⎨… … …… … … ⎟ ⎜0 1⎟ ⎜ ⎪ 0 … 0 một … một ⎟ một 0 1 … 0 ⎩ ⎜ ⎟ :⎜ ⎟ một ⎟ d .K m , n c.Wn : ⎜ 0 0 1 0 … 0 ⎜ 6474 6 n 8 ⎟ 8 474 m ⎜ … … ⎟ ⎜ ⎧ một … 1 0 … 0 ⎟ … … … … … ⎜ ⎟ ⎜⎪ ⎟ ⎜1 1⎟ 0 0 0 … 0 ⎜⎨ … … …… … … ⎟ ⎜1 0⎟ ⎜ ⎪ 1 … 1 0 … 0 ⎟ ⎝ ⎠ 1 1 1 … 1 ⎝⎩ ⎠ Bài 25: (3.8) hai đồ thị với ma trận liền kề sau đây có đẳng cấu có nhau không? ⎛0 1 0 1⎞ ⎛0 1 1 1⎞ ⎜ ⎟ ⎜ ⎟ ⎜ một 0 0 một ⎟ (h.1) ⎜ 1 0 0 1 ⎟ (h.2) ⎜0 0 0 1⎟ ⎜1 0 0 1⎟ ⎜ ⎟ ⎜ ⎟ ⎝1 một 1 0⎠ ⎝1 một 1 0⎠ Giải 2 đồ thị với ma trận liền kề ở trên chẳng thể đẳng cấu với nhau vì: chúng sở hữu số cạnh khác nhau: đồ thị thứ nhất mang 4 cạnh, đồ thị thứ hai mang 5 cạnh. Bài 26: (3.9) hai đồ thị với ma trận liền kề sau đây sở hữu đẳng cấu mang nhau không? ⎛1 một 0 0 0⎞ ⎛0 một 0 0 1⎞ ⎜ ⎟ ⎜ ⎟ ⎜1 0 1 0 1⎟ ⎜0 1 1 một 0⎟ (h.1) (h.2) ⎜0 0 0 1 1⎟ ⎜1 0 0 một 0⎟ ⎜ ⎟ ⎜ ⎟ ⎝0 một 1 một 0⎠ ⎝1 0 1 0 1⎠ Giải Thưa thầy, theo em nghĩ thì đây là 2 ma trận liên thuộc chứ chẳng phải là 2 ma trận liền kề. Và nếu là 2 ma trận liên thuộc thì chúng đẳng cấu có nhau vì: 11 BT Toan roi rac
Bai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L ⎛ e5 ⎞ ⎛ e5 ⎞ e1′ e2 ‘ ‘ ‘ ‘ e1 e2 e3 e4 e3 e4 ⎜ ⎟ ⎜’ ⎟ ⎜ v1 11 0 0 0⎟ ⎜ v1 0 một 0 0 1⎟ ⎜ v2 0 ⎟ (h.2 ‘) ⎜ v2 1 ⎟ (h.1’) ‘ 10 một 0 0 một 1 một ⎜’ ⎟ ⎜ ⎟ ⎜ v3 0⎟ ⎜ v3 0 0 0 một 1⎟ một 0 0 một ⎜v 0⎟ ⎜ v’ 1⎟ ⎝4 ⎠ 0 một 1 1 ⎝4 ⎠ một 0 1 0 ⎧ f (v1 ) = v1′ & f (v2 ) = v2 ; ‘ ⎪ Xét ánh xạ f từ V1 lên V2 sao cho: ⎨ , đồng thời trình diễn lại đồ thị ⎪ f (v3 ) = v3 & f (v4 ) = v4 ; ‘ ‘ ⎩ của ma trận liên thuộc ở hình (h.2’). Trong đấy, những cạnh được gần theo thứ tự: e2 ⎯⎯ e5 ⎯⎯ e3 ⎯⎯ e1′ ⎯⎯ e4 . →’ →’ → →’ ‘ khi này, hai ma trận liên thuộc hoàn toàn giống nhau. vì thế chúng đẳng cấu có nhau. ⎛ e5 ⎞ ⎛ e1′ e4 ⎞ e1’ e2 ‘ ‘ ‘ ‘ ‘ ‘ ‘ ‘ e3 e4 e2 e5 e3 ⎜’ ⎟ ⎜’ ⎟ ⎜ v1 ⎜ v1 0 1 0 0 1⎟ 1 1 0 0 0⎟ ⎜ v2 0 ⎟ ( h.2 ‘) ⇒ ⎜ v2 0 1 ⎟ (h.2 ”) ‘ ‘ 0 một 1 một 1 0 một ⎜’ ⎟ ⎜’ ⎟ ⎜ v3 0⎟ ⎜ v3 1 1⎟ 1 0 0 một 0 0 0 ⎜ v’ 1⎟ ⎜ v’ 1 0⎟ ⎝4 ⎠ ⎝4 ⎠ 1 0 1 0 0 1 1 Bài 27: (3.10) những cặp đồ thị sau có đẳng cấu mang nhau không? Giải Bài này hoàn toàn giống bài số 20 đã giải ở trên. Bài 28: (3.11) Cho V = 2, 3, 4, 5, 6, 7, 8 và E là tụ hội các cặp phần tử (u, v) của V sao cho u < v và u mang v là những số yếu tố cùng nhau. Hãy vẽ đồ thị có hướng G = (V , E ) . tậu số đường đi phân biệt độ dài 3 trong khoảng đỉnh 2 đến đỉnh 8. Giải hai 3 7 8 4 12 BT Toan roi rac
Bai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L Bài 29: (3.12) Hãy mua số trục đường đi độ dài n giữa hai đỉnh liền kề (t.ư ko liền kề) tùy ý trong K3,3 với mỗi trị giá của n sau: a. n = hai, b. n = 3, c. n = 4, d. n = 5. Giải một 4 (I) (II) 5 2 3 6 hai đỉnh liền kề phải ở 2 phần khác nhau. một cạnh chỉ sở hữu thể nối trong khoảng 1 đỉnh ở phần (I) tới 1 đỉnh ở phần (II) và ngược lại. Gọi m là số tuyến đường đi giữa hai đỉnh bất kỳ trong K3,3 có độ dài n. TH1: n chẵn. nếu như n chẵn thì đỉnh đầu và đỉnh cuối của đường đi phải ở cộng 1 phần, bởi thế chúng chẳng thể liền kề. TH2: n lẻ. ví như n lẻ thì đỉnh đầu và đỉnh cuối của con đường đi phải ở trên 2 phần khác nhau, bởi thế chúng phải liền kề (vì đây là K3,3). Mặc khác mỗi 1 đỉnh ở phần này luôn mang 3 phương án để đi qua một đỉnh ở phần kia. thành ra ta với được các kết luận sau đây: o 2 đỉnh liền kề, n chẵn: m = 0, m = 3n-1, o 2 đỉnh liền kề, n lẻ: m = 3n-1, o hai đỉnh ko liền kề, n chẵn: o hai đỉnh không liền kề, n lẽ: m = 0. áp dụng cho những trường hợp: Số cạnh n=2 n=3 n=4 n=5 Liền kề 0 9 0 81 không liền 3 0 27 0 kề 13 BT Toan roi rac
Bai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L Bài tập chương III Câu 1: Cho G là đồ thị sở hữu v đỉnh và e cạnh, còn M, m tương ứng là bậc to nhất và nhỏ nhất của những đỉnh của G. Chứng tỏ rằng: 2e m≤ ≤ M. v Câu 2: Chứng minh rằng nếu G là đơn đồ thị phân đôi mang v đỉnh và e cạnh, lúc đấy e ≤ v2/4. Câu 4: Hãy vẽ các đồ thị vô hướng được biểu diễn bởi ma trận liền kề sau: ⎛0 4⎞ một 3 0 ⎜ ⎟ ⎛1 hai 0 1⎞ ⎜1 0⎟ 2 1 3 ⎜ ⎟ ⎜3 1⎟ ⎛1 2 3 ⎞ 1 1 0 ⎜2 0 3 0⎟ ⎜ ⎟ ⎜ ⎟ ⎜0 3 một 1⎟ ⎜0 2⎟ ⎜ 2 0 4⎟ 3 0 0 ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ 3 4 0 ⎠ , b) ⎝ một 0 1 0⎠, c) ⎝ 4 3⎠ . 0 1 hai a) Câu 6: tậu ma trận liền kề cho các đồ thị sau: a) K n b) Cn c) Wn d) Km,n e) Q n Câu 8: hai đơn đồ thị mang ma trận liền kề sau đây với là đẳng cấu không? ⎛0 ⎛0 1⎞ 1⎞ 1 0 một 1 ⎜ ⎜ ⎟ ⎟ ⎜1 ⎜1 1⎟ 1⎟ 0 0 0 0 ⎜0 ⎜1 1⎟ 1⎟ 0 0 0 0 ⎜ ⎜ ⎟ ⎟ ⎜1 ⎜1 0 ⎟, 0 ⎟. ⎝ ⎝ ⎠ ⎠ 1 1 một 1 Câu 9: 2 đơn đồ thị sở hữu ma trận liên thuộc sau đây với là đẳng cấu không? ⎛1 ⎛0 một 0 0 0⎞ một 0 0 1⎞ ⎜ ⎜ ⎟ ⎟ ⎜1 ⎜0 0 1 0 1⎟ 1 1 một 0⎟ ⎜0 ⎜1 0 0 một 1⎟ 0 0 một 0⎟ ⎜ ⎜ ⎟ ⎟ ⎜0 ⎜1 một 1 1 0 ⎟, 0 một 0 1⎟. ⎝ ⎝ ⎠ ⎠ 14 BT Toan roi rac
Bai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L Câu 10: những đồ thị G và G’ sau mang đẳng cấu mang nhau không? a) u v2 v 1 1 u2 v6 v5 u3 u4 v3 v4 u6 u5 b) u3 u1 u2 v1 v2 v6 v3 u4 u5 u6 v5 v4 Câu 11: Cho V=2,3,4,5,6,7,8 và E là tập trung các cặp phần tử (u,v) của V sao cho u
Bai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L Câu 1: Vì m và M tương ứng là bậc nhỏ nhất và to nhất các đỉnh của G, bởi vậy ta dễ dàng có được: ⎧ ∑ deg(vi ) ≥ v.m v ⎪ m ≤ deg(vi ) ≤ M , i=1,v ⇔ ⎨ i =1 ⎪ ∑ deg(vi ) ≤ v.M v ⎩ i =1 ⎧2e ≥ vm . 2e ⇔⎨ ⇔vm ≤ 2e ≤ vM ⇔ m ≤ ≤ M . . ⎩2e ≤ vM . v Câu 2: Gọi n1, n2 lần lượt là số đỉnh của mỗi phần (d1 + d2 = v). Vì là đơn đồ thị phân đôi nên số cạnh phổ biến nhất lúc nó là đơn đồ thị phân đôi đủ, tức là: K d một ,d hai d = d1 × d hai ⇔ e ≤ d1d hai (2) lúc đấy, số cạnh phổ biến nhất sẽ là: Ta thuận tiện có được: (d1 − d 2 ) 2 ≥ 0 ⇔ d12 − 2d1d hai + d 2 ≥ 0 ⇔ d12 + 2d1d 2 + d hai ≥ 4d1d 2 2 hai (d + d ) 2 ≥ d .d ≥ e một 2 (đã chứng minh xong). một 2 4 Câu 4: a) V1 V2 V3 b) V1 V2 16 V4 V3 BT Toan roi rac
Bai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L c) V1 V5 V2 V4 V3 Câu 6: ⎡0 1⎤ một 1 1 … một ⎢1 1⎥ 0 1 1 … 1 ⎢ ⎥ ⎢1 1⎥ 1 0 một … 1 a) K : ⎢ một 1⎥ 1 1 0 … một ⎢ ⎥ n ⎢… …⎥ … … … … … ⎢ ⎥ ⎢1 một 1 1 … 0 1⎥ ⎢1 0⎥ ⎣ ⎦ 1 1 một … 1 17 BT Toan roi rac
Bai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L ⎡0 1⎤ một 0 0 … 0 ⎢1 0⎥ 0 1 0 … 0 ⎢ ⎥ ⎢0 0⎥ một 0 một … 0 b ) Cn : ⎢ 0 0⎥ 0 một 0 … 0 ⎢ ⎥ ⎢… …⎥ … … … … … ⎢ ⎥ ⎢0 0 0 0 … 0 1⎥ ⎢1 0⎥ ⎣ ⎦ 0 0 0 … 1 ⎡0 1⎤ 1 0 0 … một ⎢1 1⎥ 0 1 0 … 0 ⎢ ⎥ ⎢0 1⎥ 1 0 1 … 0 c) Wn : ⎢ 0 1⎥ 0 1 0 … 0 ⎢ ⎥ ⎢… … … … … … …⎥ ⎢ ⎥ ⎢1 0 0 0 … 0 một ⎥ ⎢1 một 1 1 … 1 0 ⎥ ⎣ ⎦ 18 BT Toan roi rac
Bai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L ⎡ 64 m 8 6 74 ⎤ 74 4 n 8 ⎢ ⎧ 0 … 0 1 … 1 ⎥ ⎢⎪ ⎥ ⎢⎨ … … …… … …⎥ ⎢ ⎪ 0 … 0 1 … một ⎥ ⎩ d ) Km,n : ⎢ ⎥ ⎢ 64 8 6 74 ⎥ 74 4 8 m n ⎢ ⎧ một … 1 0 … 0 ⎥ ⎢ ⎪… … …… … …⎥ ⎢⎨ ⎥ ⎪ một … 1 0 … 0 ⎥ ⎢⎩ ⎣ ⎦ 19 BT Toan roi rac
Bai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L Câu 8: Dựa vào ma trận liền kề của hai đơn đồ thị ta với thể vẽ lại các đồ thị bằng hình vẽ: V1 V2 U1 U2 V4 V3 U4 U3 Dựa vào hình vẽ của 2 đơn đồ thị ta thấy hai đơn đồ thị không sở hữu cùng số cạnh, 1 bên sở hữu 4 cạnh và 1 bên có 5 cạnh. Vậy 2 đơn đồ thị có ma trận liền kề đã cho ko đẳng cấu. Câu 9: Theo em dề ra là hai ma trận liên thuộc Dựa vào 2 ma trận liên thuộc ta với thể vẽ lại đồ thị của 2 ma trận như sau: e1 e2 V1 V1 V2 V2 e2 e3 e5 e5 e3 e4 e4 e1 V4 V3 V4 V3 G1 G2 hai đồ thị có những cạnh tương ứng là: G1 e1 e2 e3 e4 e5 G2 e2 e5 e3 e1 e4 hai đồ thị G1 và G2 hoàn toàn giống nhau nên chúng đẳng cấu sở hữu nhau 20 BT Toan roi rac

Trả lời

DMCA.com Protection Status