Tài liệu Khoa Học Tự Nhiên

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: 264 | 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: 332 | 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: 327 | Lượt tải: 0

7. Giả sử G = (V, E) là đồ thị Peterson. a. Chứng minh rằng G là đồ thị nửa Hamilton, nhưng không là Hamilton. b. Chứng minh rằng với mọi v 2 V, đồ thị G − v là đồ thị Hamilton. 8. Chứng minh rằng đồ thị hai phần với một số lẻ đỉnh không là đồ thị Hamilton. 9. Chứng minh rằng đồ thị đầy đủ Kn có thể phân rã thành các chu trình Hamilton nếu và ...

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

12. Chứng minh rằng: Nếu trọng số trên các cạnh của đồ thị G là khác nhau từng đôi một, vậy đồ thị có duy nhất một MST. 13. Cây bao trùm lớn nhất của một đồ thị liên thông, có trọng số là cây bao trùm có trọng số lớn nhất. Hãy đề xuất một thuật toán tương tự thuật toán Kruskal xây dựng cây bao trùm cực đại của một đồ thị liên thông có trọng số....

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

7. Định nghĩa. Giao số của đồ thị được định nghĩa là số giao điểm ít nhất khi vẽ đồ thị trên mặt phẳng sao cho không có ba cạnh nào cắt nhau tại cùng một điểm. a) Chứng minh rằng K3,3 có giao số bằng 1. b) *Tìm giao số của mỗi đồ thị không phẳng sau c) *Chứng minh rằng nếu m và n là các số nguyên chẵn, thì giao số của Km,n nhỏ hơn hoặc bằng m...

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

3. Giả sử có nhiều nam hơn nữ. (a) Định nghĩa cặp ghép ổn định trong trường hợp này. (b) Giải thích tại sao áp dụng Thủ tục kén chồng trong trường hợp này sẽ mang lại một cặp ghép ổn định trong đó mọi cô gái đều được kết hôn. 14. Hãy đưa ra một ví dụ cặp ghép ổn định giữa 3 nam và 3 nữ trong đó không ai lấy được người mình thích nhất. Giải thí...

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

5. Các nhà nghiên cứu sau nhiều năm đã chỉ ra 20 đức tính cơ bản của con người: Trung thực, rộng lượng, trung thành, kiên trì, hoàn thành bài tập đầy đủ,. Vào đầu khóa học, mỗi sinh viên Khoa học máy tính đều có đúng 8 trong số 20 đức tính trên. Hơn nữa tập đức tính cơ bản cho mọi sinh viên là duy nhất; có nghĩa rằng không có hai sinh viên n...

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

8. Có bốn sinh viên a, b, c, d muốn thực tập tại bốn công ty A, B, C, D. 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 thích Công ty a A B C D b D C B A c A B C D d C D A B Công ty thích Sinh viên A a b c d B b a c d C a d c b D d c a b Hãy dùng thuật toán kén chồ...

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

15. Một dãy số d1; d2; : : : ; dn là dãy bậc nếu có một đồ thị với n đỉnh gán nhãn v1; v2; : : : ; vn sao cho deg(vi) = di (1 ≤ i ≤ n). Chứng minh rằng nếu d1; d2; : : : ; dn là dãy bậc và d1 ≥ d2 ≥ · · · ≥ dn, vậy thì d1 + d2 + · · · + dk ≤ k(k − 1) + n∑ j=k+1 min(k; di) với 1 ≤ k ≤ n. 16. Chu vi nhỏ nhất của một đồ thị G là giá trị nhỏ nh...

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