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. | LÝ THUYẾT ĐỒ THỊ 1 THÔNG TIN VỀ GIÁO VIÊN TT Họ tên giáo viên Học hàm 1 Ngô Hữu Phúc GVC 2 Vi Bảo Ngọc TG Họ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ính Bộ 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ông nghệ thông tin - Học viện Kỹ thuật Quân sự. • Điện thoại, email: ngohuuphuc76@ • 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. 2 THÔNG TIN CHUNG VỀ MÔN HỌC • • • • • Tên học phần: Lý thuyết đồ thị Mã học phần: Số tín chỉ: 3 Học phần (bắt buộc hay lựa chọn): tự chọn Các học phần tiên quyết: Đại số tuyến tính, Giải tích đại cương, Tin họ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ết Làm bài tập trên lớp: 15 tiết Thảo luận: 6 tiết Thực hành, thực tập (ở PTN, nhà máy, thực tập.): 9 tiết Hoạ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áy tính - Khoa Công nghệ thông tin - Học viện Kỹ thuật Quân sự. 3 CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN BÀ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 đỉnh này. • Phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nối hai đỉ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á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. Hình 1. Sơ đồ mạng máy tính đơn kênh thoại. 4 CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN BÀ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ếu chúng cùng tương ứng với một cặp đỉnh. Mỗi đơn đồ .
