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

Bài tập ▶ Ta cần $15 để đóng góp cứu trợ đồng bào vùng bão lụt. ▶ Có 20 sinh viên tham gia đóng góp. ▶ Biết rằng 19 người đầu tiên sẽ góp $1 hoặc không, người thứ 20 sẽ góp $1 hoặc $5 (hoặc không góp). ▶ Hãy dùng hàm sinh để tính số cách quyên góp $15. Bài tập Hãy tính số cách để lấy 25 quả bóng giống nhau từ 7 chiếc hộp biết rằng hộp đầu t...

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

Bài tập Có bao nhiêu cách để lấy n quả thỏa mãn ba yêu cầu sau đây? ▶ Nhiều nhất 2 quả cam. ▶ Số táo là tùy ý. ▶ Số chuối phải chia hết cho 3. 41 / 51Với n = 4 quả 1. 0 quả cam, 1 quả táo, 3 quả chuối 2. 0 quả cam, 4 quả táo, 0 quả chuối 3. 1 quả cam, 0 quả táo, 3 quả chuối 4. 1 quả cam, 3 quả táo, 0 quả chuối 5. 2 quả cam, 2 quả táo, 0 q...

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

Đếm bằng hai cách 1. Định nghĩa S. 2. Chứng minh jSj = n (một cách đếm). 3. Chứng minh jSj = m (một cách đếm khác). 4. Kết luậ Chứng minh ▶ S = các bộ bài gồm n quân chọn từ n quân đỏ và 2n quân đen trên bàn.

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

Nhắc lại tương đương logic :P _ Q ≡ P ) Q 33 / 34Chứng minh Ta chứng minh bằng phản chứng. Xét u có bậc ra cao nhất và u không là vua. Vậy tồn tại v thỏa mãn: 1. v ! u, và 2. Với mọi w: :(u ! w) | {z } w!u hoặc :(w ! v) | {z } v!w Khẳng định 2 tương đương với Nếu u ! w vậy v ! w. Kết hợp với khẳng định 1 ta được outdeg(v) ≥ outdeg(u...

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

Định lý (Dirac) Nếu G là một đồ thị với n ≥ 3 đỉnh thỏa mãn: bậc của mỗi đỉnh ít nhất bằng n/2, khi đó G là đồ thị Hamilton. Chứng minh. ▶ Với hai đỉnh không kề nhau bất kỳ u và v ta có deg(u) + deg(v) ≥ n/2 + n/2 = n ▶ Suy ra, G thỏa mãn các điều kiện của định lý Ore, vì thế nó có chu trình Hamilton. Bài tập ▶ Hãy chỉ ra rằng các điều kiệ...

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

Hai đồ thị đồng phôi Định nghĩa ▶ Phép toán loại bỏ cạnh fu; vg và thêm một đỉnh mới w cùng hai cạnh fu; wg; fw; vg gọi là phép phân chia sơ cấp. ▶ Hai đồ thị gọi là đồng phôi nếu chúng có thể nhận được từ cùng một đồ thị bằng một dãy phép phân chia sơ cấp. 10.7 Planar Graphs 723 FIGURE 12 Homeomorphic Graphs. Using r = e − v + 2 (Euler’s f...

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

Định nghĩa ▶ Bạn đời tốt nhất của một người là người tốt nhất trong các lựa chọn có thể của anh/chị ta. ▶ Bạn đời tệ nhất của một người là người tệ nhất trong các lựa chọn có thể của anh/chị ta. Định lý Trong thủ tục kén chồng, mọi chàng trai đều được bạn đời tốt nhất. Định lý Trong thủ tục kén chồng, mọi cô gái đều được bạn đời tệ nhất. ...

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

Chứng minh ▶ Xét M∗ là một ghép cặp cực đại; ▶ đặt F là tập mọi cạnh thuộc M hoặc M∗, nhưng không thuộc cả hai. ▶ Tập cạnh F và các đỉnh tạo thành đồ thị với các đỉnh chỉ có bậc 1 hoặc 2. Tại sao? ▶ Vậy mỗi thành phần liên thông của đồ thị chỉ là đường đi hoặc chu trình; ▶ và trong mỗi đường đi hoặc chu trình này, các cạnh thuộc M luân phi...

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

Số hội đồng bảo vệ ▶ Xét đồ thị với tập đỉnh là các hội đồng, giữa hai dỉnh có cạnh nối nếu hai hội đồng có chung thành viên. ▶ Bài toán tương đương với bài toán tìm số màu ít nhất để tô đồ thị này. ▶ Đồ thị này có chứa clique f1; 2; 3; 4g có kích thước 4 nên số ngày bằng 4 là ít nhất có thể. Ký hiệu ei(G) là số đỉnh của đồ thị G có bậc...

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

Prüfer code ▶ Ta không cần lưu trữ toàn bộ Prüfer code mở rộng, mà ▶ ta chỉ cần lưu tữ dãy gồm n − 2 phần tử của hàng thứ hai. ▶ Dãy này gọi là Prüfer code của cây. ▶ Vậy thì, Prüfer code là một dãy số độ dài n − 2, với mỗi phần tử của nó là một số nguyên từ 0 đến n − 1. Bổ đề Mọi dãy có độ dài n − 2 gồm các số nguyên giữa 0 và n − 1 đều là ...

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