Tài liệu Toán Học

Định nghĩa ▶ Chu trình chứa mọi đỉnh của đồ thị gọi là chu trình Hamilton. ▶ Hành trình dùng mỗi cạnh đúng một lần gọi là hành trình Euler. Tìm chu trình Hamilton của đồ thị tạo bởi các đỉnh và cạnh của khối lập phương. 10.7 P K4 Drawn sings. FIGURE 4 The Graph Q3. FIGURE 5 Represent 56 / 57Bài tập Năm tới, Dr Chunner và Dr Dodder đị...

57 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 399 | Lượt tải: 0

Ví dụ Ở nước Quy nạp, họ dùng đơn vị tiền Mạnh. Họ chỉ có hai loại tiền 3M (Mạnh) và 5M. Dù họ có vấn đề nhỏ với việc đổi tiền 4M hoặc 7M, nhưng họ nhận thấy rằng họ có thể đổi mọi số tiền ít nhất 8M. Hãy giải thích cho họ xem tại sao điều này đúng. ▶ Có một chồng hộp. Bạn sẽ thực hiện một dãy bước chuyển. ▶ Mỗi bước chuyển bạn chia một hộp kích th...

37 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 597 | Lượt tải: 0

Định lý Mọi số nguyên dương lớn hơn một đều phân tích được thành tích các số nguyên tố. Chứng minh bằng STTT. ▶ Giả sử tập phản ví dụ của định lý C ̸= ∅. ▶ Có phần tử n nhỏ nhất thuộc C. Vậy n không nguyên tố. Có nghĩa rằng n = a · b với a; b > 1 ▶ Hơn nữa a; b phải phân tích được thành tích các số nguyên tố. Tại sao? a = p1 · · · pk và b...

37 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 692 | Lượt tải: 0

Số Ramsey có khó tính không? Số Ramsey khá gần đây người ta tính được là r(4; 5) = 25. Dưới đây là thời gian tìm số này: ▶ 1955: Chặn trên đầu tiên cho r(4; 5) ≤ 31. ▶ 1965: Chặn dưới đầu tiên và cải thiện chặn trên 25 ≤ r(4; 5) ≤ 30. ▶ 1968: Cải thiện chặn trên r(4; 5) ≤ 29. ▶ 1971: Cải thiện chặn trên r(4; 5) ≤ 28. ▶ 1991: Cải thiện chặn ...

27 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 498 | Lượt tải: 0

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) 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...

5 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 649 | Lượt tải: 0

9. Có năm sinh viên V, W, X, Y, Z muốn thực tập tại năm công ty A, B, C, D, E. Sau đây là danh sách xếp hạng mức độ ưa thích của các sinh viên và của các công ty (trái nhất là thích nhất): Sinh viên Công ty V A B C D E W B C D A E X C D A B E Y D A B C E Z A B C D E Công ty Sinh viên A W X Y Z V B X Y Z V W C Y Z V W X D Z V W X Y E V ...

4 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 581 | Lượt tải: 0

9. Ta có ba bình thể tích 10 lít, 7 lít, và 4 lít. Ban đầu, bình 7 lít và 4 lít chứa đầy nước, còn bình 10 lít rỗng. Ta chỉ được phép sử dụng thao tác sau: Đổ hết lượng nước còn lại từ một bình sang một bình khác, chỉ dừng khi bình rỗng hoặc bình kia đầy. Bài toán đổ nước: Liệu với một dãy các thao tác này, ta có thể để lại đúng 2 lít nước trong...

2 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 563 | Lượt tải: 0

1. Cho bàn cờ n × n như sau: Xét đường đi ngắn nhất từ góc A tới góc B đi qua các cạnh (mỗi đường qua 2n cạnh). (a) Có bao nhiêu đường như vậy? (b) Chứng minh rằng số đường không xuống dưới đường chéo chính là số Catalan Cn. 2. Hãy tìm cách chứng minh số cách đặt dấu ngoặc là số Catalan mà không dùng hàm sinh. 3. Có 2n người đứng đợi mua vé xe...

5 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 361 | Lượt tải: 0

13. Xác định hệ số của x12 y24 trong đa thức (x3 + 2x y2 + y + 3)18. (Chú ý: x hoặc y có thể xuất hiện trong nhiều số hạng!) 14. Với mỗi xâu dưới đây, hãy xác định số cách sắp xếp các chữ trong đó mọi chữ đều được dùng. (a) OVERNUMEROUSNESSES (b) OPHTHALMOOTORHINOLARYNGOLOGY (c) HONORIFICABILITUDINITATIBUS 15. Có bao nhiêu cách tô lên 27 bức...

2 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 440 | Lượt tải: 0

6. Chứng minh rằng: Tồn tại đồ thị thi đấu n đỉnh thỏa mãn mọi đỉnh đều có bậc vào bằng bậc ra nếu và chỉ nếu n lẻ. 7. Với n ≥ 1, hãy chứng minh hoặc bác bỏ rằng: mọi đồ thị có hướng với n đỉnh đều có hai đỉnh có cùng bậc ra hoặc hai đỉnh có cùng bậc vào. 8. Chứng minh rằng đồ thị có hướng là liên thông mạnh nếu với mọi cách phân hoạch tập đỉn...

1 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 423 | Lượt tải: 0