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

Câu hỏi 2 Ta sẽ tiếp tục thế nào khi đã tìm được một thành phần liên thông mạnh? Mệnh đề Nếu C và D là các thành phần liên thông mạnh, và có một cạnh từ một đỉnh trong C tới một đỉnh trong D, vậy thì số post lớn nhất trong C phải lớn hơn số post lớn nhất trong D. Khi ta tìm thấy một thành phần liên thông mạnh và xóa nó khỏi đồ thị G, vậy th...

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

Câu hỏi 2 Ta sẽ tiếp tục thế nào khi đã tìm được một thành phần liên thông mạnh? Mệnh đề Nếu C và D là các thành phần liên thông mạnh, và có một cạnh từ một đỉnh trong C tới một đỉnh trong D, vậy thì số post lớn nhất trong C phải lớn hơn số post lớn nhất trong D. Khi ta tìm thấy một thành phần liên thông mạnh và xóa nó khỏi đồ thị G, vậy th...

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

Định lý Cho c1; c2; : : : ; ck là các số thực. Giả sử phương trình kr − c1rk−1 − · · · − ck = 0 có k nghiệm phân biệt r1; r2; : : : ; rk. Khi đó dãy ⟨an⟩ là nghiệm của hệ thức truy hồi an = c1an−1 + c2an−2 + · · · + ckan−k nếu và chỉ nếu an = α1r1n + α2r2n + · · · + αkrkn trong đó αi là các hằng số. Ví dụ Tìm nghiệm của hệ thức truy hồi ...

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

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: 271 | 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: 270 | 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: 305 | 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: 287 | 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: 343 | 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: 293 | 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: 286 | Lượt tải: 0