tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 1 - Ngô Hữu Phúc

"Bài giảng Lý thuyết đồ thị - Chương 1: Các khái niệm cơ bản" gồm các nội dung khái niệm đồ thị; bậc của đỉnh; đường đi, chu trình; đồ thị liên thông; đơn đồ thị đặc biệt; biểu diễn đồ thị trên máy tính. | LÝ THUYẾT ĐỒ THỊ 1 THÔNG TIN VỀ GIÁO VIÊN TT Họ tên giáo Học Học vị Đơn vị công tác Bộ môn viên hàm 1 Ngô Hữu Phúc GVC Tiến sỹ Bộ môn Khoa học máy tính 2 Vi Bảo Ngọc TG Thạc sỹ 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 đồ 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