• Bài giảng Toán rời rạc - Bài 13: Đếm - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 13: Đếm - Trần Vĩnh Đức

    Đế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.

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

  • Bài giảng Toán rời rạc - Bài 12: Đồ thị có hướng - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 12: Đồ thị có hướng - Trần Vĩnh Đức

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

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

  • Bài giảng Toán rời rạc - Bài 11: Đồ thị Hamilton - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 11: Đồ thị Hamilton - Trần Vĩnh Đức

    Đị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ệ...

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

  • Bài giảng Toán rời rạc - Bài 9: Đồ thị phẳng - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 9: Đồ thị phẳng - Trần Vĩnh Đức

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

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

  • Bài giảng Toán rời rạc - Bài 8 - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 8 - Trần Vĩnh Đức

    Đị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. ...

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

  • Bài giảng Toán rời rạc - Bài 7: Ghép cặp trên đồ thị hai phần - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 7: Ghép cặp trên đồ thị hai phần - Trần Vĩnh Đức

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

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

  • Bài giảng Toán rời rạc - Bài 6: Tô màu đỉnh của đồ thị - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 6: Tô màu đỉnh của đồ thị - Trần Vĩnh Đức

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

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

  • Bài giảng Toán rời rạc - Bài 5: Cây - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 5: Cây - Trần Vĩnh Đức

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

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

  • Bài giảng Toán rời rạc - Bài 4: Đồ thị - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 4: Đồ thị - Trần Vĩnh Đứ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 đị...

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

  • Bài giảng Toán rời rạc - Bài 3: Quy nạp - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 3: Quy nạp - Trần Vĩnh Đức

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

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