BÀI GIẢNG TOÁN RỜI RẠC 2

BÀI GIẢNG TOÁN RỜI RẠC 2
Toán rời rạc là một lĩnh vực nghiên cứu và xử lý các đối tượng rời rạc dùng để
đếm các đối tượng, và nghiên cứu mối quan hệ giữa các tập rời rạc. Một trong những yếu tố làm Toán rời rạc trở nên quan trọng là việc lưu trữ, xử lý thông tin trong các hệ thống máy tính về bản c[r]

Slide bài giảng, Toán rời rạc,bài toán đếm nguyên lý cộng , nguyên lý nhân

Toán rời rạc là lĩnh vực nghiên cứu và xử lý các đối tượng rời rạc. Toán rời rạc
dùng để đếm, quan sát, và xử lý mối quan hệ giữa các đối tượng trong các tập hợp khác nhau. Bản chất tính toán trên máy tính là rời rạc. Chính vì vậy, toán học rời rạc được xem là môn học kinh điển cho sinh viên các ng[r]

Nếu trong đồ thị phẳng mà tất cả các đỉnh đều có bậc không nhỏ hơn 6 thì do mỗi đỉnh của đồ thị phải là đầu mút của ít nhất 6 cạnh mà mỗi cạnh lại có hai đầu mút nên ta có 6n  2p hay 3n  p. Từ đó suy ra 3d+3n  2p+p hay d+n  p, trái với hệ thức Euler d+n=p+2. 7.2. ĐỒ THỊ KHÔNG PHẲNG[r]

Thuật toán sẽ xây dựng tập cạnh ET của cây khung nhỏ nhất T=(VT, ET) theo từng bước. Trước hết sắp xếp các cạnh của đồ thị G theo thứ tự không giảm của trọng số. Bắt đầu từ ET=, ở mỗi bước ta sẽ lần lượt duyệt trong danh sách cạnh đã sắp xếp, từ cạnh có độ dài nhỏ đến cạnh có độ dài lớn hơn, để tìm[r]

, ..., vk-1, vk (= vi) là một chu trình đơn cần tìm. Điều kiện đủ: Quy nạp theo số cạnh của G. Do G liên thông và bậc của mọi đỉnh là chẵn nên mỗi đỉnh có bậc không nhỏ hơn 2. Từ đó theo Bổ đề 4.1.3, G phải chứa một chu trình đơn C. Nếu C đi qua tất cả các cạnh của G thì nó chính là chu trình[r]

.(A+a’) = (a+A).(a’+A) = (a+B).(a’+B)=(a.a’)+B=0+B= B hay ta có 2a) và đối ngẫu ta có 2b). Ngoài ra, tính duy nhất của phần tử bù cũng được suy ra từ các tiên đề khác. Tương tự trong đại số lôgic, trong đại số Boole ta cũng xét các công thức, được thành lập từ các biến a, b, c, … nhờ[r]

158PHẦN PHỤ LỤC Phụ lục 2 Bài toán luồng cực đại Cho mạng G=(V,E). Hãy tìm luồng f* trong mạng với giá trị luồng val(f*) là lớn nhất. Luồng như vậy ta sẽ gọi là luồng cực đại trong mạng. Bài toán như vậy có thể xuất hiện trong rất nhiều ứng dụng thực tế. Chẳng hạn khi cần xác định cường độ[r]

1LỜI NÓI ĐẦU Nhằm đảm bảo quyền tự chủ cho sinh viên trong quá trình học tập học phần Toán rời rạc theo hệ thống tín chỉ với thời lượng 60 tiết. Chúng tôi biên soạn giáo trình Toán rời rạc với khối lượng kiến thức tối thiểu, cập nhật, cô đọng, chính xác và phù hợp với đố[r]

22CHƯƠNG II BÀI TOÁN ĐẾM Lý thuyết tổ hợp là một phần quan trọng của toán học rời rạc chuyên nghiên cứu sự phân bố các phần tử vào các tập hợp. Thông thường các phần tử này là hữu hạn và việc phân bố chúng phải thoả mãn những điều kiện nhất định nào đó, tùy theo yêu cầu của bài toán cần nghi[r]

4CHƯƠNG I: THUẬT TOÁN 1.1. KHÁI NIỆM THUẬT TOÁN. 1.1.1. Mở đầu: Có nhiều lớp bài toán tổng quát xuất hiện trong toán học rời rạc. Chẳng hạn, cho một dãy các số nguyên, tìm số lớn nhất; cho một tập hợp, liệt kê các tập con của nó; cho tập hợp các số nguyên, xếp chúng theo thứ tự tăng dần; cho[r]

37 CHƯƠNG III ĐỒ THỊ Lý thuyết đồ thị là một ngành khoa học được phát triển từ lâu nhưng lại có nhiều ứng dụng hiện đại. Những ý tưởng cơ bản của nó được đưa ra từ thế kỷ 18 bởi nhà toán học Thụy Sĩ tên là Leonhard Euler. Ông đã dùng đồ thị để giải quyết bài toán 7 chiếc cầu Konigsberg nổi tiếng.[r]

và "x+y=z" không phải là mệnh đề vì chúng chẳng đúng cũng chẳng sai bởi các biến trong những câu đó chưa gán cho giá trị cụ thể nào. Giá trị đúng, sai của một mệnh đề được gọi là giá trị chân lí của mệnh đề đó. Giá trị chân lí của mệnh đề đúng ký hiệu là T (true), giá trị chân lí của Các kiến thức c[r]

ví dụ về giải thuật có thể được hiểu rõ ràng hơn. Tuy nhiên có khả năng người học chưa được học cụ thể một ngôn ngữ lập trình nên tác giả sẽ chỉ dùng mã giả tựa-Pascal để minh hoạ các giải thuật. Sau này - khi cần – người học sẽ chuyển các giải thuật đó thành chương trình trong một ngôn ngữ cụ thể ([r]

5.2.3. Thuật toán Kruskal: Thuật toán sẽ xây dựng tập cạnh ET của cây khung nhỏ nhất T=(VT, ET) theo từng bước. Trước hết sắp xếp các cạnh của đồ thị G theo thứ tự không giảm của trọng số. Bắt đầu từ ET=∅, ở mỗi bước ta sẽ lần lượt duyệt trong danh sách cạnh đã sắp xếp, từ cạnh có độ dài Cây Nguyễn[r]

141 Với hàm G(x,y,z) nhận giá trị 1 khi x=z=0 và y=1 hoặc x=y=1 và z=0. Tương tự như ở trên tích x.y.¬z=1 hoặc tích ¬x.y.¬z=1 sau đó xét tổng của chúng. Vậy hàm G(x,y,z) sẽ là tổng của 2 tích này G(x,y,z)=x.y.¬z + ¬x.y.¬z Như vậy việc tìm một biểu thức boole biểu diễn một hàm Boole có giá t[r]

Chương IICÁC KIẾN THỨC CƠ BẢN.I. Thuật toán:1. Khái niệm thuật toán và đặc trưng của nó:Giả sử nhằm đảm bảo vệ sinh an toàn thực phẩm chúng ta muốn đóng gói kẹo dừa trên một dây chuyền tự động thay cho gói kẹo bằng tay như hiện nay. Để giải quyết bài toán này, chúng ta phải thiết kế và chế tạo ra mộ[r]

Chương IICÁC KIẾN THỨC CƠ BẢN.I. Thuật toán:1. Khái niệm thuật toán và đặc trưng của nó:Giả sử nhằm đảm bảo vệ sinh an toàn thực phẩm chúng ta muốn đóng gói kẹo dừa trên một dây chuyền tự động thay cho gói kẹo bằng tay như hiện nay. Để giải quyết bài toán này, chúng ta phải thiết kế và chế tạo ra mộ[r]

— Đỉnh lý Euler
«Ổ Bậc mỗi đỉnh > 2, đồ thị có chu trình
G là đồ thị Euler khi và chỉ khi bậc mỗi đỉnh là chẵn
G là đồ thị nửa Euler khi và chỉ khi G có không quá hai đỉnh bậc lẻ

{Item quy ước là một kiểu dữ liệu bất kì nào đó} Ví dụ 2: Mô tả thuật toán tìm tổng các phần tử dương trong một dãy hữu hạn các số bất kì. a) Dùng ngôn ngữ tự nhiên để mô tả các bước cần phải thực hiện: 1. Đặt giá trị tổng ban đầu bằng 0. 2. Đi từ đầu dãy tới cuối dãy, kiểm tra số hi[r]