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

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: 532 | 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: 462 | 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: 312 | 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: 332 | 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: 349 | 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: 490 | Lượt tải: 0

Trong ví dụ trên, sau một vài bước, mọi sinh viên trong lớp sẽ bị nhiễm cúm. Hãy chứng minh định lý sau đây. Định lý. Nếu tại thời điểm ban đầu trong lớp có ít hơn n sinh viên bị nhiễm cúm, thì không bao giờ xảy ra việc cả lớp đều bị nhiễm cúm. Gợi ý: Để hiểu hệ thống kiểu như trên “tiến triển" thế nào theo thời gian, một chiến lược là 1. xác ...

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

Bài 5 Mục đích của bài tập này là kiểm tra xem những đặc tả sau đây có thỏa được không: 1. Nếu hệ thống file không bị khóa, thì (a) các thông điệp mới sẽ được đặt trong hàng đợi. (b) các thông điệp mới sẽ được gửi tới bộ đệm thông điệp. (c) hệ thống đang hoạt động bình thường, và ngược lại, nếu hệ thông đang hoạt động bình thường, thì hệ thốn...

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

Bài 3 Với n = 40 giá trị của đa thức p(n) ::= n2 + n + 41 không phải là số nguyên tố. Ta dự đoán rằng, ngoại trừ các đa thức hằng số, không có đa thức nào chỉ sinh ra các giá trị là các số nguyên tố. Cụ thể, xét đa thức q(n) với hệ số nguyên dương, và xét c ::= q(0) là số hạng hằng số của q(n). (a) Chứng minh rằng q(cm) là bội của c với mọi m...

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