Tên học phần: Lý thuyết đồ thị Tên tiếng Anh: Graph Theory Mã học phần: 14258 Số đơn vị học trình: 4 Trình độ (cho sinh viên năm thứ 2) Phân bổ thời gian: - Lên lớp: 30 tiết - Thực tập phòng thí nghiệm, thực hành: 30 tiết Giảng viên phụ trách: ThS. Nguyễn Đức Thành Bộ môn: Mạng MT và truyền thông Khoa: Công Nghệ Thông Tin Mục tiêu của học phần: Sau khi hoàn tất học phần, sinh viên có khả năng : - Cung cấp cho sinh viên những kiến thức cần thiết về lý thuyết đồ thị và các ứng dụng trên máy tính. - Nâng cao kỹ năng lập trình thông qua các bài tập thực hành. Mô tả vắn tắt nội dung học phần: Các học phần tiên quyết hay có liên quan: Lập trình A2, Toán rời rạc Nội dung chi tiết phân bố theo chương trình và số tiết tương ứng của học phần: Phần 1: Giới thiệu (6 LT / 3 TH) + Lý thuyết (6 tiết) - Các khái niệm cơ bản về đồ thị, đỉnh, cạnh - Các loại đồ thị - Bậc của đỉnh, đồ thị cân bằng - Biểu diễn đồ thị - Hai đồ thị đẳng hình - Đường đi và chu trình - Miền liên thông, liên thông mạnh - Một số định lý và tính chất quan trọng - Giới thiệu một số khái niệm cơ bản về độ phức tạp của thuật toán + Thực hành (3tiết) - Biểu diễn đồ thị bằng ma trận kề và bằng danh sách liên kết - Viết chương trình tính bậc của một đỉnh, xác định đồ thị cân bằng Phần 2: Đường đi và chu trình (6 LT / 6 TH) + Lý thuyết (6 tiết) - Đường đi Euler và chu trình Euler - Điều kiện cần và đủ để xác định một chu trình, đường đi Euler - Thuật toán xác định chu trình, đường đi Euler - Đường đi Halmiton và chu trình Halmiton - Bài toán người du lịch - Các quy tắc xác định chu trình Halmiton - Một số định lý và tính chất quan trọng + Thực hành (6tiết) - Viết chương trình xác định đường đi, chu trình Euler - Viết chương trình xác định đường đi, chu trình Halmiton, khảo sát thời gian thực hiện thuật toán khi số đỉnh đồ thị tăng Phần 3: Đồ thị phẳng và bài toán tô màu đồ thị (6 LT / 3 TH) + Lý thuyết (6 tiết) - Định nghĩa đồ thị phẳng, đồ thị phẳng tối đa - Công thức Euler - Bài toán 3 nhà – 3 giếng - Bất đẳng thức cạnh – đỉnh - Định lý Kuratowski - Bài toán tô màu bản đồ + Thực hành (3tiết) - Giải bài toán tô màu đồ thị, khảo sát thời gian thực hiện thuật toán khi số đỉnh của đồ thị tănghttps://drive.google.com/drive/folders/1yLBzZ1rSQoNjmWeJTZ3WGQHg04L1 Phần 4: Cây (6 LT / 9 TH) + Lý thuyết (6 tiết) - Định nghĩa cây, cây có gốc - Định lý Daisy Chain - Cây bao trùm - Thuật toán xác định cây bao trùm theo chiều sâu – DFS - Thuận toán xác định cây bao trùm theo chiều rộng – BFS - Kiểm tra tính liên thông của một đồ thị - Cây bao trùm nhỏ nhất – thuật toán xác định cây bao trùm tối thiểu - Thuật toán Prim - Thuật toán Kruskal + Thực hành (9tiết) - Cài đặt thuật toán DFS, BFS (so sánh thời gian thực hiện DFS và BFS) - Cài đặt thuật toán Prim - Cài đặt thuật toán Kruskal - So sánh thời gian thực hiện Prim và Kruskal Phần 5: Đồ thị có hướng – Bài toán tìm đường đi ngắn nhất (6 LT / 9 TH) + Lý thuyết (6 tiết) - Thuật toán Dijsktra - Thuật toán Floyd - Bài toán xác định bao đóng bắc cầu – thuật toán Warshall + Thực hành (9tiết) - Cài đặt thuật toán Dijsktra - Cài đặt thuật toán Floy Tài liệu học tập, trang thiết bị phụ vụ thực hành thực tập, trợ huấn cụ Tài liệu tham khảo 1. W W L Chen, Discrete mathematics, University of London. 2. Nguyễn Cam, Chu Đức Khánh, Lý thuyết Đồ thị, 1998. 3. S. Even, Graph Algorithms, 1979. 4. Robert Sedgewick, Cẩm nang thuật toán – tập 2 (bản dịch Việt ngữ), 1995. 5. L. Lovász and K. Vesztergombi, Discrete Mathematics, Lecture notes, Yale University, Spring 1999. 6. Nguyễn Trung Trực, Cấu trúc Dữ liệu, Khoa CNTT – Đại học Bách Khoa TP.HCM, 1997. Nhiệm vụ của sinh viên: - Dự lớp - Bài tập Tiêu chuẩn đánh giá sinh viên: - Thi giữa kỳ - Thi cuối học phần - Bài tập cộng điểm Thang điểm: Thi giữa kỳ (30%) + thi cuối kỳ (50%) + bài tập cộng điểm (20%) Download Link: http://fit.hcmuaf.edu.vn/data/file/LTDT.rar eBook có trong tuyển tập DVD Tin Học
