Đề thi môn Toán rời rạc - Đề 1+2

Đề thi môn: TOÁN RỜI RẠC – K56 Thời gian: 90 phút (Không sử dụng tài liệu, nộp lại đề) Bài 1: 1a) Trong không gian 3 chiều có bao nhiêu đường đi từ điểm (0,0,0) đến điểm (25, 35, 55) nếu mỗi bước đi có một trong ba toạ độ tăng lên 1, hai toạ độ còn lại giữ nguyên. 1b) Có bao nhiêu đơn đồ thị vô hướng với n đỉnh ? Bài 2: Xét hai mệnh đề (P1): Với mọi số nguyên dương lẻ m, luôn tìm được số nguyên dương n sao cho 2n – 1 chia hết cho m. (P2): Với mọi số nguyên dương m, n, đồ thị hai phía đầy đủ Km,n luôn chứa chu trình Hamilton. Hãy chứng minh tính đúng đắn hoặc đưa ra phản ví dụ cho mỗi mệnh đề. Bài 3: Trình diễn thuật toán nhánh cận giải bài toán cái túi biến nguyên sau: 10ݔଵ + 17ݔଶ + 30ݔଷ + 40ݔସ → ݉ܽݔ 3ݔଵ + 5ݔଶ + 7ݔଷ + 8ݔସ ≤ 28 ݔ௝ ≥ 0, ݔ௝ ∈ ℤ, ݆ = 1,2,3,4 Bài 4: Cho G=(V,E) là đồ thị có hướng mà giữa hai đỉnh bất kì u,v của nó luôn có hoặc là cạnh (u,v), hoặc là cạnh (v,u), nhưng không đồng thời có cả hai. Kí hiệu deg+(v) và deg-(v) tương ứng là bán bậc ra và bán bậc vào của đỉnh v. Chứng minh rằng với đồ thị G đã cho, đẳng thức sau đây luôn đúng: ෍ [degା(ݒ)]ଶ ௩∈௏ = ෍ [degି(ݒ)]ଶ ௩∈௏ Bài 5: Xét đồ thị có hướng có trọng số như dưới đây, trình diễn thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại: Đề thi môn: TOÁN RỜI RẠC – K56 Thời gian: 90 phút (Không sử dụng tài liệu, nộp lại đề) Bài 1: 1a) Trong không gian 3 chiều có bao nhiêu đường đi từ điểm (0,0,0) đến điểm (30, 40, 50) nếu mỗi bước đi có một trong ba toạ độ tăng lên 1, hai toạ độ còn lại giữ nguyên. 1b) Tính tổng số bậc của đơn đồ thị đủ Kn. Bài 2: Xét hai mệnh đề (P1): Với mọi số nguyên dương lẻ m, luôn tìm được số nguyên dương n sao cho 2n – 1 chia hết cho m. (P2): Với mọi số nguyên dương m, n, đồ thị hai phía đầy đủ Km,n luôn chứa chu trình Hamilton. Hãy chứng minh tính đúng đắn hoặc đưa ra phản ví dụ cho mỗi mệnh đề. Bài 3: Trình diễn thuật toán nhánh cận giải bài toán cái túi biến nguyên sau: 11ݔଵ + 18ݔଶ + 31ݔଷ + 41ݔସ → ݉ܽݔ 3ݔଵ + 5ݔଶ + 7ݔଷ + 8ݔସ ≤ 29 ݔ௝ ≥ 0, ݔ௝ ∈ ℤ, ݆ = 1,2,3,4 Bài 4: Cho G=(V,E) là đồ thị có hướng mà giữa hai đỉnh bất kì u,v của nó luôn có hoặc là cạnh (u,v), hoặc là cạnh (v,u), nhưng không đồng thời có cả hai. Kí hiệu deg+(v) và deg-(v) tương ứng là bán bậc ra và bán bậc vào của đỉnh v. Chứng minh rằng với đồ thị G đã cho, đẳng thức sau đây luôn đúng: ෍ [degା(ݒ)]ଶ ௩∈௏ = ෍ [degି(ݒ)]ଶ ௩∈௏ Bài 5: Xét đồ thị có hướng có trọng số như dưới đây, trình diễn thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh B đến các đỉnh còn lại: 1 2 Đề thi môn: TOÁN RỜI RẠC – K55 Thời gian: 90 phút (Không sử dụng tài liệu, nộp lại đề) Bài 1: 1a) Tìm số nghiệm nguyên (x,y) của bất phương trình: 3|ݔ| + |ݕ| ≤ ݊ , với n là số nguyên dương. 1b) Một hình lập phương có cạnh bằng 15 chứa 11000 điểm. Chứng minh rằng tồn tại một hình cầu bán kính bằng 1 chứa ít nhất 6 điểm trong số 11000 điểm đã cho. Bài 2: Xét hai mệnh đề (P1): Trong một đơn đồ thị luôn có ít nhất 2 đỉnh cùng bậc. (P2): Trong mặt phẳng cho 5 điểm phân biệt có toạ độ nguyên, luôn tìm được ít nhất 2 điểm mà trung điểm đoạn thẳng nối chúng có toạ độ nguyên. Hãy chứng minh tính đúng đắn hoặc đưa ra phản ví dụ cho mỗi mệnh đề. Bài 3: Sử dụng hàm sinh giải công thức đệ quy: ൜ ܽ଴ = 4,ܽଵ = 12 ܽ௡ = ܽ௡ିଵ + 2ܽ௡ିଶ + 2௡ (݊ ≥ 2) Bài 4: Cho G=(V,E) là đồ thị có v đỉnh và e cạnh. còn m và M tương ứng là bậc nhỏ nhất và bậc lớn nhất của các đỉnh của G. Chứng minh hệ bất đẳng thức: ݉ ≤ 2݁ ݒ ≤ ܯ Bài 5: Xét đồ thị vô hướng có trọng số như dưới đây, trình diễn thuật toán Prim tìm cây khung lớn nhất của đồ thị: Đề thi môn: TOÁN RỜI RẠC – K55 Thời gian: 90 phút (Không sử dụng tài liệu, nộp lại đề) Bài 1: 1a) Tìm số nghiệm nguyên của bất phương trình: ݔ + ݕ + ݖ ≤ 25 , với điều kiện ݔ,ݕ ≥ 2, 0 < ݖ < 6 1b) Một hình vuông có cạnh bằng 1 chứa 101 điểm. Chứng minh rằng có ít nhất 5 điểm trong số 101 điểm nói trên nằm trong một hình tròn bán kính bằng 1/7. Bài 2: Xét hai mệnh đề (P1): Trong số 10 người bất kì bao giờ cũng tìm được 2 người có tổng số tuổi chia hết cho 16, hoặc hiệu số tuổi chia hết cho 16. (P2): Trong không gian cho 9 điểm có toạ độ nguyên, luôn tìm được ít nhất 2 điểm mà đoạn thẳng nối chúng đi qua điểm có toạ độ nguyên. Hãy chứng minh tính đúng đắn hoặc đưa ra phản ví dụ cho mỗi mệnh đề. Bài 3: Sử dụng hàm sinh giải công thức đệ quy: ൜ ܽ଴ = 2,ܽଵ = 5 ܽ௡ = 4ܽ௡ିଵ − 4ܽ௡ିଶ + ݊ଶ (݊ ≥ 2) Bài 4: Cho G=(V,E) là đơn đồ thị hai phía có v đỉnh và e cạnh. Chứng minh bất đẳng thức sau: ݁ ≤ ݒଶ4 Bài 5: Xét đồ thị có hướng có trọng số như dưới đây, trình diễn thuật toán Kruskal tìm cây khung lớn nhất của đồ thị: 1 2 Đề thi môn: TOÁN RỜI RẠC – K54 Thời gian: 90 phút (Không sử dụng tài liệu, nộp lại đề) Bài 1: 1a) Trong tổng số 2504 sinh viên của khoa công nghệ thông tin, có 1876 theo học ngôn ngữ Pascal, 999 học môn ngôn ngữ Fortran và 345 học môn ngôn ngữ C. Ngoài ra 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 189 sinh viên học cả ba ngôn ngữ Pascal, Fortran và C thì trong trường hợp đó có bao nhiêu sinh viên không học môn nào trong cả 3 ngôn ngữ nói trên. 1b) Một đô vật tham gia thi đấu giành chức vô địch trong 75 giờ. Mỗi giờ anh ta thi đấu ít nhất một trận, nhưng toàn bộ anh ta không thi đấu quá 125 trận. Chứng tỏ rằng, có những giờ liên tiếp anh ta thi đấu 24 trận. Bài 2: Xét mệnh đề sau: “Trong n+1 số nguyên dương, mỗi số không vượt quá 2n, tồn tại ít nhất một số chia hết cho một số khác”. Hãy chứng minh tính đúng đắn hoặc đưa ra phản ví dụ cho mệnh đề trên. Bài 3: Trình diễn thuật toán nhánh cận giải bài toán người du lịch với ma trận chi phí như dưới đây (giả sử xuất phát từ A): A B C D E A 0 55 87 70 76 B 91 0 81 57 39 C 80 77 0 81 58 D 99 83 64 0 89 E 56 91 82 88 0 Bài 4: Một ngôi chùa linh thiêng có 5 trụ bằng kim cương. Người ta đúc các dây xích bằng vàng để nối các trụ lại với nhau, với điều kiện mỗi trụ chỉ được nối với đúng 3 trụ khác. Chứng minh rằng không thể tìm được cách nối thoả mãn điều kiện trên. Bài 5: Trình diễn thuật toán Ford-Fulkerson tìm luồng cực đại và lát cắt hẹp nhất trong mạng sau: Đề thi môn: TOÁN RỜI RẠC – K54 Thời gian: 90 phút (Không sử dụng tài liệu, nộp lại đề) Bài 1: 1a) Hiệu trưởng mời 2n (݊ ≥ 2) sinh viên giỏi đến dự tiệc. Mỗi sinh viên giỏi quen ít nhất n sinh viên giỏi khác đến dự tiệc. Chứng minh rằng luôn luôn có thể xếp tất cả các sinh viên giỏi ngồi xung quanh một bàn tròn, để mỗi người ngồi giữa hai người mà sinh viên đó quen. 1b) Đếm số xâu nhị phân 13 bit chứa hai số 0 liên tiếp. Bài 2: Xét mệnh đề sau: “Trong 102 người có chiều cao khác nhau đứng thành một hàng luôn tìm được 11 người có chiều cao tăng dần hoặc giảm dần mà không cần thay đổi thứ tự của họ trong hàng”. Hãy chứng minh tính đúng đắn hoặc đưa ra phản ví dụ cho mệnh đề trên. Bài 3: Trình diễn thuật toán nhánh cận giải bài toán người du lịch với ma trận chi phí như dưới đây (giả sử xuất phát từ A): A B C D E A 0 43 80 69 72 B 81 0 92 58 39 C 70 77 0 82 43 D 95 73 17 0 89 E 26 91 82 78 0 Bài 4: Giả sử đơn đồ thị phẳng liên thông có 6 đỉnh, mỗi đỉnh đều có bậc là 4. Biểu diễn phẳng của đồ thị này chia mặt phẳng thành bao nhiêu miền ? Bài 5: Trình diễn thuật toán Ford-Fulkerson tìm luồng cực đại và lát cắt hẹp nhất trong mạng sau: 1 2 Đề thi môn: TOÁN RỜI RẠC – K53 Thời gian: 90 phút (Không sử dụng tài liệu, nộp lại đề) Bài 1: a) Trong tập 2009 số nguyên dương đầu tiên có bao nhiêu số không chia hết cho bất kì số nào trong các số 11, 13, 15, 17. b) Trên một lưới ô vuông các số nguyên cho hai điểm A(3,2) và B(100, 99). Hỏi có bao nhiêu đường đi khác nhau từ A đến B mà không cắt đường thẳng y=x (chỉ cho phép đi trên cạnh các ô vuông theo chiều sang phải hoặc lên trên) ? Bài 2: Cho G=(V,E) là một đơn đồ thị vô hướng liên thông. Chứng minh rằng: a) Nếu tất cả các đỉnh của G đều có bậc là 2 thì G là đồ thị Euler. b) Nếu tất cả các cạnh của G là cầu thì G là một cây. Bài 3: Trình diễn thuật toán nhánh cận giải bài toán cái túi: 7ݔଵ + 15ݔଶ + 26ݔଷ + 34ݔସ → ݉ܽݔ 3ݔଵ + 4ݔଶ + 8ݔଷ + 9ݔସ ≤ 25 ݔ௝ ≥ 0, ݔ௝ ∈ ℤ, ݆ = 1,2,3,4 Bài 4: Giải công thức đệ quy: ൜ ܽଵ = 6,ܽଶ = 42 ܽ௡ = ܽ௡ିଵ + 6ܽ௡ିଶ + 6݊ (݊ ≥ 3) Bài 5: Trong mạng G=(V,E) cho luồng f như sau: a) Xây dựng đồ thị tăng luồng Gf. b) Cho biết luồng f có cực đại không ? Nếu không, hãy thực hiện tìm luồng cực đại và lát cắt hẹp nhất của mạng trên. Đề thi môn: TOÁN RỜI RẠC – K53 Thời gian: 90 phút (Không sử dụng tài liệu, nộp lại đề) Bài 1: a) Từ các chữ số 1,2,3,4,5,6,7, người ta lập tất cả các số có 5 chữ số (5 chữ số này đôi một khác nhau). Tính tổng của tất cả các số này. b) Trong tập A = {1,2,,30000} có bao nhiêu số không chia hết cho bất cứ số nào trong các số 6, 8, 9 ? Bài 2: a) Có 20 đội bóng thi đấu trong một giải. Mỗi đội phải đấu một trận với các đội còn lại. Chứng minh rằng luôn có hai đội bóng có số trận đã đấu là như nhau (tính cả trường hợp chưa đấu trận nào). b) Chứng minh rằng cây là đồ thị hai phía. Bài 3: Trình diễn thuật toán nhánh cận giải bài toán cái túi: 16ݔଵ + 9ݔଶ + 7ݔଷ + 5ݔସ → ݉ܽݔ 6ݔଵ + 5ݔଶ + 3ݔଷ + 2ݔସ ≤ 17 ݔ௝ ≥ 0,ݔ௝ ∈ ℤ, ݆ = 1,2,3,4 Bài 4: Giải công thức đệ quy: ൜ ܽ଴ = 1,ܽଵ = 2 ܽ௡ = 8ܽ௡ିଵ − 16ܽ௡ିଶ + 6݊ + 2 (݊ ≥ 2) Bài 5: Trong mạng G=(V,E) cho luồng f như sau: a) Xây dựng đồ thị tăng luồng Gf. Từ đó chứng minh f là luồng cực đại. b) Đưa ra giá trị luồng cực đại và lát cắt hẹp nhất. 1 2 Đề thi môn: TOÁN RỜI RẠC – K52 Thời gian: 90 phút (Không sử dụng tài liệu, nộp lại đề) Bài 1: a) Trường ĐHBKHN tiến hành phát học bổng cho sinh viên. Biết rằng có ba loại học bổng, hỏi cần trao học bổng cho ít nhất bao nhiêu sinh viên để chắc chắn rằng trong số họ có ít nhất 13 người nhận học bổng cùng loại ? b) Tìm số cách đặt các dấu ngoặc đơn vào tích của n + 1 số ݔ଴ݔଵ ݔ௡ để xác định thứ tự của phép nhân. Ví dụ có 5 cách đặt dấu ngoặc đơn cho tích ݔ଴ݔଵݔଶݔଷ để các định thứ tự phép nhân: ൫(ݔ଴ݔଵ)ݔଶ൯ݔଷ, ൫ݔ଴(ݔଵݔଶ)൯ݔଷ, (ݔ଴ݔଵ)(ݔଶݔଷ), ݔ଴൫(ݔଵݔଶ)ݔଷ൯, ݔ଴(ݔଵ(ݔଶݔଷ)). Bài 2: Cho đồ thị có hướng G được biểu diễn dưới dạng ma trận trọng số: A B C D E F A 0 3 ∞ 3 ∞ ∞ B ∞ 0 3 4 1 ∞ C ∞ ∞ 0 ∞ 3 1 D ∞ ∞ 1 0 2 ∞ E ∞ ∞ ∞ ∞ 0 1 F ∞ ∞ ∞ ∞ ∞ 0 a) Thực hiện thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh C đến các đỉnh còn lại của đồ thị G. b) Chứng minh G là một mạng. Thực hiện thuật toán Ford – Fulkerson tìm luồng cực đại và lát cắt nhỏ nhất của mạng G. c) Gọi G’ là phiên bản vô hướng của G (tức là không xét tới hướng của các cung trên G). Thực hiện thuật toán Prim tìm cây khung nhỏ nhất của đồ thị G’. Bài 3: Giải công thức đệ quy sau: ൜ ܽ଴ = 1, ܽଵ = 4 ܽ௡ = 4ܽ௡ିଵ − 3ܽ௡ିଶ + 2௡ + ݊ + 3 (݊ ≥ 2) Đề thi môn: TOÁN RỜI RẠC – K52 Thời gian: 90 phút (Không sử dụng tài liệu, nộp lại đề) Bài 1: a) Trường ĐHBKHN tiến hành phát học bổng cho sinh viên. Biết rằng có năm loại học bổng, hỏi cần trao học bổng cho ít nhất bao nhiêu sinh viên để chắc chắn rằng trong số họ có ít nhất 28 người nhận học bổng cùng loại ? b) Một máy bán tem tự động chỉ nhận loại tiền xu 1$, tiền giấy 1$ và tiền giấy 5$. Tìm số cách đưa 30 $ vào máy (có chú ý đến thứ tự của xu và giấy bỏ vào). Bài 2: Cho đồ thị có hướng G được biểu diễn dưới dạng ma trận trọng số: A B C D E F A 0 5 ∞ 3 ∞ ∞ B ∞ 0 4 6 ∞ ∞ C ∞ ∞ 0 ∞ 4 3 D ∞ ∞ 2 0 2 ∞ E ∞ 1 ∞ ∞ 0 2 F ∞ ∞ ∞ ∞ ∞ 0 a) Thực hiện thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh E đến các đỉnh còn lại của đồ thị G. b) Chứng minh G là một mạng. Thực hiện thuật toán Ford – Fulkerson tìm luồng cực đại và lát cắt nhỏ nhất của mạng G. c) Gọi G’ là phiên bản vô hướng của G (tức là không xét tới hướng của các cung trên G). Thực hiện thuật toán Kruskal tìm cây khung nhỏ nhất của đồ thị G’. Bài 3: Giải công thức đệ quy sau: ൜ ܽ଴ = −2, ܽଵ = 0, ܽଶ = 5 ܽ௡ = 7ܽ௡ିଵ − 16ܽ௡ିଶ + 12ܽ௡ିଷ + ݊4௡ (݊ ≥ 3) 1 2