tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 1 - PGS.TS. Hoàng Chí Thành

Bài giảng Lý thuyết đồ thị: Chương 1 cung cấp cho người đọc những kiến thức như: Các khái niệm về đồ thị; Biểu diễn đồ thị trong máy tính; Một số tính chất về đường đi trên đồ thị; Bậc của đỉnh và tính liên thông. Mời các bạn cùng tham khảo! | LÝ THUYẾT ĐỒ THỊ Giảng viên . Hoàng Chí Thành Trường Đại học Khoa học Tự nhiên ĐHQG HN MỞ ĐẦU - Lý thuyết Đồ thị là một trong những ngành khoa học ra đời khá sớm. - Lý thuyết Đồ thị giúp mô tả hình học và giải quyết nhiều bài toán thực tế phức tạp liên quan đến các khái niệm như đường đi chu trình tập ổn định chu số sắc số duyệt đồ thị đường đi ngắn nhất tâm đồ thị luồng vận tải đồ thị phẳng cây bao trùm cây biểu thức cây mã tối ưu bằng các thuật toán ngắn gọn và lý thú. - Lý thuyết Đồ thị đã gắn kết nhiều ngành khoa học với nhau. 2 63 MỞ ĐẦU tiếp Bài giảng điện tử Lý thuyết Đồ thị này bao gồm - 11 chương - phân thành 20 bài học trình bày những vấn đề cốt lõi nhất của lý thuyết đồ thị cùng các thuật toán tiêu biểu giúp người học có thể cài đặt trên máy tính và ứng dụng trong thực tế. 3 63 CHƯƠNG 1 ĐẠI CƯƠNG VỀ ĐỒ THỊ 4 63 NỘI DUNG Các khái niệm về đồ thị Biểu diễn đồ thị trong máy tính Một số tính chất về đường đi trên đồ thị Bậc của đỉnh và tính liên thông 5 63 . CÁC KHÁI NIỆM VỀ ĐỒ THỊ Định nghĩa Đồ thị là một cặp G V E trong đó - V là tập hợp các đỉnh vertex - E V V là tập hợp các cạnh edge . 6 63 VÍ DỤ Đồ thị G cho như hình vẽ. - Tập đỉnh V a b c d e - Tập các cạnh E a b a c b c d b d c e a e b e d . b c a e d Hình Đồ thị hữu hạn 7 63 TÍNH KỀ TRONG ĐỒ THỊ Đỉnh kề Nếu a b là một cạnh của đồ thị G thì - Đỉnh b kề với đỉnh a - Hai đỉnh a và b cùng kề với cạnh a b . Hai cạnh kề nhau là hai cạnh có ít nhất một đỉnh chung. 8 63 ĐỊNH NGHĨA ĐỒ THỊ tiếp Định nghĩa Đồ thị là một cặp G V F trong đó - V là tập hợp các đỉnh - F V 2V được gọi là ánh xạ kề. Sự tương đương của hai định nghĩa x y V x y E y F x . 9 63 VÍ DỤ Ánh xạ kề của đồ thị trên hình vẽ F a b c F b c F c F d b c và F e a b d . b c a e d Hình Đồ thị hữu hạn 10 63 ĐỒ THỊ VÔ HƯỚNG VÀ CÓ HƯỚNG Cạnh vô hướng cặp đỉnh x y E không sắp thứ tự. Cạnh có hướng cặp đỉnh x y E có sắp thứ tự. 11 63 ĐỒ THỊ VÔ HƯỚNG VÀ CÓ HƯỚNG tiếp Định nghĩa - Đồ thị chỉ chứa các cạnh vô hướng được .