TAILIEUCHUNG - Bài giảng Toán rời rạc (Phần II: Lý thuyết đồ thị): Chương 1 - Nguyễn Đức Nghĩa

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ị. | Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 1 Phần 2 LÝ THUYẾT ĐỒ THỊ Graph Theory 1 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 2 Nội dung Chương 1. Các khái niệm cơ bản Đồ thị vô hướng và có hướng Các thuật ngữ cơ bản Một số dạng đồ thị vô hướng đặc biệt Chương 2. Biểu diễn đồ thị Ma trận kề, ma trận trọng số, Ma trận liên thuộc đỉnh cạnh Danh sách cạnh, Danh sách kề Chương 3. Duyệt đồ thị Tìm kiếm theo chiều sâu; Tìm kiếm theo chiều rộng Tìm đường đi và kiểm tra tính liên thông 2 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 3 Nội dung Chương 4. Cây và cây khung của đồ thị Cây và các tính chất của cây Cây khung của đồ thị Bài toán cây khung nhỏ nhất Chương 5. Bài toán đường đi ngắn nhất Phát biểu bài toán Đường đi ngắn nhất xuất phát từ một đỉnh (Thuật toán Dijkstra, Ford-Bellman) Đường đi ngắn nhất trên đồ thị không có chu trình Đường đi ngắn nhất giữa mọi cặp đỉnh (Thuật toán Floyd) Chương 6. Bài toán luồng cực đại trong mạng Mạng, luồng và bài toán luồng cực đại Định lý Ford-Fulkerson Thuật toán Ford-Fulkerson Một số ứng dụng 3 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 4 Chương 1 CÁC KHÁI NIỆM CƠ BẢN Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 5 Chương 1 CÁC KHÁI NIỆM CƠ BẢN . Đồ 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ị Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 6 Trong toán học đời thường hiểu là: Bản vẽ hay Sơ đồ biểu diễn dữ liệu nhờ sử dụng hệ thống toạ độ. Trong toán rời rạc: Đây là cấu trúc rời rạc có tính trực quan cao, rất tiện ích để biểu diễn các quan hệ. Đồ thị là gì? Không phải cái ta muốn đề cập Không phải cái này Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 7 Các ứng dụng thực tế của đồ thị Có tiềm năng ứng dụng trong nhiều .

• Kỹ thuật lập trình
• 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
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Bài tập về toán rời rạc
• Ôn tập toán rời rạc
• Đề thi toán rời rạc