Bài giảng Lý thuyết đồ thị - Học viện Kỹ thuật Quân sự

Bài giảng Lý thuyết đồ thị được biên soạn nhằm trang bị cho các bạn những kiến thức về các khái niệm cơ bản, các thuật toán tìm kiếm trên đồ thị; đồ thị euler và đồ thị hamilton; cây và cây khung của đồ thị; bài toán luồng cực đại.
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết đồ thị - Học viện Kỹ thuật Quân sựLÝ THUYẾT ĐỒ THỊ1THÔNG TIN VỀ GIÁO VIÊNTTHọ tên giáoviênHọchàm1 Ngô Hữu Phúc GVC2 Vi Bảo NgọcTGHọc vịTiến sỹThạc sỹĐơn vị công tác (Bộ môn)Bộ môn Khoa học máy tínhBộ môn Khoa học máy tính• Thời gian, địa điểm làm việc: Bộ môn Khoa học máy tính Khoa Công nghệ thông tin - Học viện Kỹ thuật Quân sự.• Địa chỉ liên hệ: Bộ môn Khoa học máy tính - Khoa Côngnghệ thông tin - Học viện Kỹ thuật Quân sự.• Điện thoại, email: ngohuuphuc76@gmail.com• Các hướng nghiên cứu chính: Xử lý ảnh, Trí tuệ nhân tạo,Nhận dạng mẫu, Tính toán mềm, Xử lý tiếng nói.2THÔNG TIN CHUNG VỀ MÔNHỌC•••••Tên học phần: Lý thuyết đồ thịMã học phần:Số tín chỉ: 3Học phần (bắt buộc hay lựa chọn): tự chọnCác học phần tiên quyết: Đại số tuyến tính, Giải tích đại cương, Tinhọc cơ bản• Các yêu cầu đối với học phần (nếu có):• Giờ tín chỉ đối với các hoạt động:––––––Nghe giảng lý thuyết: 30 tiếtLàm bài tập trên lớp: 15 tiếtThảo luận: 6 tiếtThực hành, thực tập (ở PTN, nhà máy, thực tập...): 9 tiếtHoạt động theo nhóm:Tự học: 90 tiết• Khoa/Bộ môn phụ trách học phần, địa chỉ: Bộ môn Khoa học máytính - Khoa Công nghệ thông tin - Học viện Kỹ thuật Quân sự.3CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢNBÀI 1 KHÁI NIỆM ĐỒ THỊ• Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnhnày.• Phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nốihai đỉnh nào đó của đồ thị.Định nghĩa 1 (Đơn đồ thị). Đơn đồ thị vô hướng G = (V,E) bao gồm V là tập các đỉnh khácrỗng, và E là tập các cặp không có thứ tự gồm hai phần tử khácnhau của V gọi là các cạnh.Hình 1. Sơ đồ mạng máy tính đơn kênh thoại.4CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢNBÀI 1 KHÁI NIỆM ĐỒ THỊĐịnh nghĩa 2 (Đa đồ thị). Đa đồ thị vô hướng G= (V, E) bao gồm V là tập các đỉnh khác rỗng, vàE là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi làcác cạnh. Hai cạnh e1 và e2 được gọi là cạnh lặp (bội hay song song) nếuchúng cùng tương ứng với một cặp đỉnh. Mỗi đơn đồ thị là đa đồ thị, nhưng không phải đa đồ thị nào cũng là đơnđồ thị, vì trong đa đồ thị có thể có hai (hoặc nhiều hơn) cạnh nối một cặpđỉnh nào đó.Hình 2. Sơ đồ mạng máy tính đa kênh thoại.5