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

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: 365 | 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: 443 | 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: 305 | Lượt tải: 0

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

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

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

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

Định lý Mọi số nguyên dương lớn hơn một đều phân tích được thành tích các số nguyên tố. Chứng minh bằng STTT. ▶ Giả sử tập phản ví dụ của định lý C ̸= ∅. ▶ Có phần tử n nhỏ nhất thuộc C. Vậy n không nguyên tố. Có nghĩa rằng n = a · b với a; b > 1 ▶ Hơn nữa a; b phải phân tích được thành tích các số nguyên tố. Tại sao? a = p1 · · · pk và b...

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

Số Ramsey có khó tính không? Số Ramsey khá gần đây người ta tính được là r(4; 5) = 25. Dưới đây là thời gian tìm số này: ▶ 1955: Chặn trên đầu tiên cho r(4; 5) ≤ 31. ▶ 1965: Chặn dưới đầu tiên và cải thiện chặn trên 25 ≤ r(4; 5) ≤ 30. ▶ 1968: Cải thiện chặn trên r(4; 5) ≤ 29. ▶ 1971: Cải thiện chặn trên r(4; 5) ≤ 28. ▶ 1991: Cải thiện chặn ...

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

Bài 2: Cho đồ thị có hướng G được biểu diễn dưới dạng ma trận trọng số: a) Thực hiện thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh E đến các đỉnh còn lại của đồ thị G. b) Chứng minh G là một mạng. Thực hiện thuật toán Ford – Fulkerson tìm luồng cực đại và lát cắt nhỏ nhất của mạng G. c) Gọi G’ là phiên bản vô hướng của G (tức là không xét...

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

9. Có năm sinh viên V, W, X, Y, Z muốn thực tập tại năm công ty A, B, C, D, E. 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 Công ty V A B C D E W B C D A E X C D A B E Y D A B C E Z A B C D E Công ty Sinh viên A W X Y Z V B X Y Z V W C Y Z V W X D Z V W X Y E V ...

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

9. Ta có ba bình thể tích 10 lít, 7 lít, và 4 lít. Ban đầu, bình 7 lít và 4 lít chứa đầy nước, còn bình 10 lít rỗng. Ta chỉ được phép sử dụng thao tác sau: Đổ hết lượng nước còn lại từ một bình sang một bình khác, chỉ dừng khi bình rỗng hoặc bình kia đầy. Bài toán đổ nước: Liệu với một dãy các thao tác này, ta có thể để lại đúng 2 lít nước trong...

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