» Từ khóa: ly thuyet roi rac

Bài giảng "Toán rời rạc - Chương 5: Lý thuyết đồ thị" cung cấp cho người học các kiến thức: Khái niệm đồ thị, các loại đồ thị, bậc của đồ thị, biểu diễn đồ thị, tính liên thông trong đồ thị, chu trình Euler – Hamilton, tìm đường đi ngắn nhất. Mời các bạn cùng tham khảo.

 59 p ntt 22/09/2020 167 0 Download

Từ khóa: Bài giảng Toán rời rạc, Toán rời rạc, Lý thuyết đồ thị, Phân loại đồ thị, Tính liên thông trong đồ thị, Chu trình Euler, Biểu diễn đồ thị

Chương 1 trình bày các khái niệm cơ bản về đồ thị như: Đồ thị trong thực tế, các loại đồ thị, bậc của đỉnh, đồ thị con, đồ thị đẳng cấu, đường đi và chu trình, tính liên thông, một số loại đồ thị đặc biệt, tô màu đồ thị.

 275 p ntt 30/09/2019 368 1 Download

Từ khóa: Toán rời rạc, Bài giảng Toán rời rạc, Lý thuyết đồ thị, Graph Theory, Đồ thị con, đồ thị đẳng cấu

Chương 4 trình bày về bài toán cây khung nhỏ nhất (The minimum spanning tree problem). Nội dung chính gồm có: Cây và các tính chất cơ bản của cây, cây khung của đồ thị, xây dựng tập các chu trình cơ bản của đồ thị, bài toán cây khung nhỏ nhất.

 60 p ntt 30/09/2019 252 1 Download

Từ khóa: Toán rời rạc, Bài giảng Toán rời rạc, Lý thuyết đồ thị, Graph Theory, Cây khung của đồ thị, Bài toán cây khung nhỏ nhất

Chương 5 trang bị cho người học những kiến thức cơ bản về bài toán đường đi ngắn nhất. Thông qua chương này người học có thể hiểu được: Bài toán đường đi ngắn nhất (ĐĐNN); tính chất của ĐĐNN, giảm cận trên; thuật toán Bellman-Ford; thuật toán Dijkstra; đường đi ngắn nhất trong đồ thị không có chu trình; thuật toán Floyd-Warshal.

 78 p ntt 30/09/2019 452 1 Download

Từ khóa: Toán rời rạc, Bài giảng Toán rời rạc, Lý thuyết đồ thị, Bài toán đường đi ngắn nhất, Thuật toán Bellman-Ford, Thuật toán Dijkstra

Bài giảng Toán rời rạc (Phần II: Lý thuyết đồ thị): Chương 6 - Bài toán luồng cực đại (Maximum flow problem). Những nội dung chủ yếu được trình bày trong chương này gồm có: Bài toán luồng cực đại trong mạng; lát cắt, đường tăng luồng; định lý về luồng cực đại và lát cắt hẹp nhất; thuật toán Ford-Fulkerson; thuật toán Edmond-Karp; các ứng dụng.

 83 p ntt 30/09/2019 291 1 Download

Từ khóa: Toán rời rạc, Bài giảng Toán rời rạc, Lý thuyết đồ thị, Bài toán luồng cực đại, Maximum flow problem, Luồng cực đại

Chương này trình bày một số ứng dụng của bài toán luồng cực đại như: Bài toán với nhiều điểm phát và điểm thu, bài toán với hạn chế thông qua ở nút, bài toán cặp ghép cực đại trong đồ thị hai phía, độ tin cậy của mạng. Mời các bạn cùng tham khảo.

 53 p ntt 30/09/2019 237 1 Download

Từ khóa: Toán rời rạc, Bài giảng Toán rời rạc, Lý thuyết đồ thị, Bài toán luồng cực đại, Bài toán luồng tổng quát, Độ tin cậy của mạng, Bài toán cặp ghép cực đại

Chương này trình bày về Bài toán ghép cặp (Graph Matching) với những nội dung chính sau: Bài toán ghép cặp trên đồ thị, bài toán cặp ghép cực đại trên đồ thị hai phía, qui về bài toán luồng cực đại, đường tăng cặp ghép, thuật toán tìm cặp ghép cực đại,... Mời các bạn cùng tham khảo.

 43 p ntt 30/09/2019 210 1 Download

Từ khóa: Toán rời rạc, Bài giảng Toán rời rạc, Lý thuyết đồ thị, Bài toán ghép cặp, Bài toán ghép cặp trên đồ thị, Bài toán luồng cực đại

Chương mở đầu về lý thuyết tổ hợp giúp người học hiểu được một số kiến thức cơ bản như: Tổ hợp là gì? Sơ lược về lịch sử phát triển của tổ hợp, tập hợp và ánh xạ. Mời các bạn cùng tham khảo.

 91 p ntt 30/09/2019 381 1 Download

Từ khóa: Toán rời rạc, Bài giảng Toán rời rạc, Lý thuyết tổ hợp, Toán tổ hợp, Bài toán đếm, Bài toán tồn tại tổ hợp

Chương 1 của phần lý thuyết tổ hợp trình bày về bài toán đếm. Những nội dung chính trong chương này gồm có: Nguyên lý cộng và nguyên lý nhân, các cấu hình tổ hợp cơ bản, nguyên lý bù trừ, công thức đệ qui, hàm sinh. Mời các bạn cùng tham khảo.

 178 p ntt 30/09/2019 286 1 Download

Từ khóa: Toán rời rạc, Bài giảng Toán rời rạc, Lý thuyết tổ hợp, Nguyên lý cộng, Nguyên lý nhân, Nguyên lý bù trừ, Công thức đệ qui

Chương 2 - Bài toán tồn tại. Nội dung chính được trình bày trong chương này gồm có: Giới thiệu bài toán, các kỹ thuật chứng minh cơ bản, nguyên lý Dirichlet, định lý Ramsey. Mời các bạn cùng tham khảo.

 103 p ntt 30/09/2019 292 1 Download

Từ khóa: Toán rời rạc, Bài giảng Toán rời rạc, Lý thuyết tổ hợp, Bài toán tồn tại, Nguyên lý Dirichlet, Định lý Ramsey

Trong chương trước, ta đã tập trung chú ý vào việc đếm số các cấu hình tổ hợp. Trong những bài toán đó sự tồn tại của các cấu hình là hiển nhiên và công việc chính là đếm số phần tử thoả mãn tính chất đặt ra. Tuy nhiên, trong rất nhiều bài toán tổ hợp, việc chỉ ra sự tồn tại của một cấu hình thoả mãn các tính chất cho trước là hết...

 108 p ntt 30/09/2019 303 1 Download

Từ khóa: Toán rời rạc, Bài giảng Toán rời rạc, Lý thuyết tổ hợp, Định lý Ramsey, Bài toán tồn tại, Nguyên lý Dirichlet

Chương 3 - Bài toán liệt kê tổ hợp. Những nội dung chính được trình bày trong chương này gồm có: Giới thiệu bài toán, thuật toán và độ phức tạp, phương pháp sinh, thuật toán quay lui. Mời các bạn cùng tham khảo.

 142 p ntt 30/09/2019 284 1 Download

Từ khóa: Toán rời rạc, Bài giảng Toán rời rạc, Lý thuyết tổ hợp, Bài toán liệt kê tổ hợp, Phương pháp sinh, Thuật toán quay lui