Đồ án, luận văn, do an, luan van

Khẳng định Trong số 6 người luôn có ba người đôi một quen nhau hoặc ba người đôi một lạ nhau Bài tập Hãy chứng minh rằng trong 9 người luôn có 3 người đôi một quen nhau hoặc 4 người đôi một không quen nhau. Lý thuyết Ramsey Lý thuyết Ramsey, theo tên của nhà toán học người Anh, Frank Plumpton Ramsey.

27 trang | Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 18 | Lượt tải: 0

Bài tập ▶ GS Mc Brain và vợ là bà April tới một bữa tiệc ở đó có 4 đôi vợ chồng khác. ▶ Có một vài cặp bắt tay nhau nhưng không ai bắt tay với vợ hoặc chồng mình. ▶ GS hỏi mọi người khác xem họ bắt tay bao nhiêu người và ông ấy nhận được 9 con số khác nhau. ▶ Hỏi có bao nhiêu người đã bắt tay April?

37 trang | Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 19 | Lượt tải: 0

Định nghĩa Ta nói rằng đồ thị T là một cây nếu nó có hai tính chất: (T1) T liên thông; (T2) T không có chu trình. Các cây với 1; 2 hoặc 3 đỉnh Có hai cây với 4 đỉnh Có ba cây với 5 đỉnh Mệnh đề Nếu T = (V; E) là một cây với ít nhất hai đỉnh, thì với mỗi cặp đỉnh x; y có duy nhất một đường đi từ x tới y. Chứng minh. Vì T liên thông nên có...

46 trang | Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 20 | Lượt tải: 0

Ví dụ Trường BK muốn xếp giờ học cho sáu môn học v1; v2; v3; v4; v5; v6 biết rằng có một vài sinh viên học các môn : v1 và v2, v1 và v4, v3 và v5, v2 và v6, v4 và v5, v5 và v6, v1 và v6. Xếp lịch học ▶ Ta tìm cách phân hoạch tập đỉnh thành 4 phần sao cho không phần nào chứa cặp đỉnh kề nhau. ▶ Một cách hình thức, đây là một hàm c : fv1; v2...

44 trang | Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 18 | Lượt tải: 0

Ghép cặp trên đồ thị hai phần ▶ Eric Lehman, F Thomson Leighton & Albert R Meyer, Mathematics for Computer Science, 2013 (Miễn phí) ▶ Albert R Meyer’s slides 2 / 39Tìm bạn nhảy ▶ Tối thứ bảy, hội sinh viên tổ chức tiệc. ▶ Có 300 sinh viên tham gia. ▶ Họ không quen hết nhau! ▶ Trong 6 người luôn có ba người đôi một quen nhau hoặc ba người đ...

39 trang | Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 21 | Lượt tải: 0

Định nghĩa (Đồ thị nửa Hamilton) ▶ Một đường đi trong đồ thị G được gọi là đường đi Hamilton nếu nó chứa tất cả các đỉnh của G. ▶ Một đồ thị được gọi là đồ thị nửa Hamilton nếu nó có đường đi Hamilton. Nói cách khác, đồ thị nửa Hamilton là đồ thị có đường đi bao trùm

24 trang | Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 23 | Lượt tải: 0

Định nghĩa Một đồ thị có hướng là một cặp có thứ tự G = (V; E), ở đây V là một tập, còn E là một tập con của tích đề các V × V, tức E là một quan hệ hai ngôi trên V. ▶ Các phần tử của V thường được gọi là các đỉnh. ▶ Các phần của E gọi là các cung. ▶ Cụ thể hơn, nếu (a; b) 2 E thì (a; b) được gọi là cung của G với đỉnh đầu là a và đỉnh cuối ...

34 trang | Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 20 | Lượt tải: 0

Dãy và tập ▶ Dãy: có thứ tự, các phần tử có thể trùng nhau (a; b; a) 6= (b; a; a) ▶ Tập: không thứ tự, các phần tử không trùng nhau fa; b; cg = fb; a; cg 4 / 48Định nghĩa Một hoán vị của một tập S là một dãy chứa mỗi phần tử của S đúng một lần. 5 / 48Số hoán vị của một tập ▶ Tập fa; b; cg có 6 hoán vị: f (a; b; c); (b; c; a); (c; a; b); ...

48 trang | Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 19 | Lượt tải: 0

Ký hiệu hình thức ▶ Có 2 quả táo, 3 quả mận, và 4 quả đào. ▶ Ta ký hiệu T := “lấy một quả táo” M := “lấy một quả mận” D := “lấy một quả đào”: ▶ Lấy 1 quả táo, 2 quả mận, và 3 quả đào: TMMDDD = TM2D3: ▶ Lấy 1 quả táo, 1 quả mận, và 1 quả đào hoặc lấy 1 quả táo, 1 quả đào, và 2 quả mận”: TMD + TMD2

51 trang | Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 21 | Lượt tải: 0

Định nghĩa Ta ký hiệu [xn]G(x) là hệ số của xn trong hàm sinh G(x) = g0 + g1x + g2x2 + ·· · : Có nghĩa rằng [xn]G(x) = gn: 3 / 26Bài tập Tìm hệ số của xn trong hàm sinh (1 − x)c : 4 / 26Lời giải Ta có (1 − x)c = (1 + x + x2 + · · · )c: Hệ số của xn trong hàm sinh trên chính là số nghiệm nguyên không âm của phương trình

26 trang | Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 21 | Lượt tải: 0