Luận văn Thạc sĩ Toán học: Đồ thị luồng - Các khái niệm và tính chất

Luận văn sẽ tập trung trình bày chi tiết về mô hình đồ thị luồng, luồng liên kết và chỉ rõ mối quan hệ với đồ thị. Sau đó, chúng tôi tìm hiểu về thuật toán liệt kê clique cực đại trong luồng liên kết và đề xuất thuật toán tìm đường đi ngắn nhất, đường đi nhanh nhất trong đồ thị luồng.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Toán học: Đồ thị luồng - Các khái niệm và tính chất BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Nguyễn Thị Thu HằngĐỒ THỊ LUỒNG: CÁC KHÁI NIỆM VÀ TÍNH CHẤT LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội - 2019 BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Nguyễn Thị Thu HằngĐỒ THỊ LUỒNG: CÁC KHÁI NIỆM VÀ TÍNH CHẤT Chuyên ngành: Toán ứng dụng Mã số: 8 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN: PGS.TSKH. Phan Thị Hà Dương Hà Nội - 2019 LỜI CAM ĐOAN Tôi xin cam đoan những gì viết trong luận văn là do sự tìm tòi, học hỏicủa bản thân và sự hướng dẫn tận tình của cô Phan Thị Hà Dương. Mọi kết quảnghiên cứu cũng như ý tưởng của tác giả khác, nếu có đều được trích dẫn cụ thể.Đề tài luận văn này cho đến nay chưa được bảo vệ tại bất kì một hội đồng bảovệ luận văn thạc sĩ nào và cũng chưa hề được công bố trên bất kì một phươngtiện nào. Tôi xin chịu trách nhiệm về những lời cam đoan. Hà Nội, tháng 10 năm 2019 Học viên Nguyễn Thị Thu Hằng LỜI CẢM ƠN Đầu tiên, tôi xin được tỏ lòng biết ơn sâu sắc nhất của mình tới PGS.TSKHPhan Thị Hà Dương, người trực tiếp hướng dẫn tôi tìm ra hướng nghiên cứu.Luận văn này được hoàn thành dưới sự hướng dẫn tận tình của cô trong một thờigian dài. Cô đã luôn quan tâm, giúp đỡ, động viên tôi trong suốt quá trình họctập và nghiên cứu. Tôi xin chân thành cảm ơn các thầy cô và các anh chị thuộc phòng Cơ sởToán - Tin, Viện Toán học vì sự giúp đỡ và tạo điều kiện để tôi hoàn thành luậnvăn. Ngoài ra, trong quá trình học tập, nghiên cứu và thực hiện luận văn tôi cònnhận được nhiều sự quan tâm, góp ý, hỗ trợ quý báu của quý thầy cô, anh chị vàbạn bè trong Viện Toán học Việt Nam. Tôi cũng xin trân trọng cảm ơn sự giúp đỡ và tạo điều kiện thuận lợi của cơsở đào tạo là Học viện Khoa học và Công nghệ, Viện Hàn lâm Khoa học vàCông nghệ Việt Nam trong quá trình thực hiện luận văn. Đặc biệt, tôi xin cảm ơn gia đình, người thân và bạn bè đã luôn sát cánh,động viên và khích lệ tôi trong suốt quá trình học tập và nghiên cứu. Hà Nội, tháng 10 năm 2019 Học viên Nguyễn Thị Thu HằngMục lụcLời cam đoanLời cảm ơnMục lụcDanh mục các hình vẽ và đồ thịMỞ ĐẦU 11 CÁC ĐỊNH NGHĨA CƠ BẢN VỀ ĐỒ THỊ 3 1.1 Đồ thị, đồ thị con, bậc của đỉnh . . . . . . . . . . . . . . . . . . 3 1.2 Đường, chu trình . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Liên thông và thành phần liên thông . . . . . . . . . . . . . . . 7 1.4 Mật độ, hệ số phân cụm và tỷ lệ bắc cầu . . . . . . . . . . . . . 92 CÁC ĐỊNH NGHĨA CƠ BẢN VỀ ĐỒ THỊ LUỒNG VÀ MỐI QUAN HỆ VỚI ĐỒ THỊ 12 2.1 Định nghĩa đồ thị luồng và luồng liên kết . . . . . . . . . . . . . 13 2.2 Mở rộng khái niệm đỉnh và cạnh . . . . . . . . . . . . . . . . . 17 2.3 Đồ thị luồng con . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4 Hàng xóm và bậc . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.5 Đường, chu trình trong đồ thị luồng . . . . . . . . . . . . . . . . 21 2.6 Liên thông và thành phần liên thông . . . . . . . . . . . . . . . 24 2.7 Mật độ, hệ số phân cụm và tỷ lệ bắc cầu . . . . . . . . . . . . . 293 MỘT SỐ TÍNH TOÁN TRÊN ĐỒ THỊ LUỒNG VÀ LUỒNG LIÊN KẾT 33 3.1 Tìm các clique cực đại trong luồng liên kết . . . . . . . . . . . . 33 3.1.1 Clique và thuật toán tìm clique cực đại trên đồ thị . . . . . 34 3.1.2 Clique và thuật toán tìm ∆-clique cực đại trên luồng liên kết 36 3.2 Tìm đường đi ngắn nhất và đường đi nhanh nhất trong đồ thị luồng 42 3.2.1 Thuật toán tìm đường đi ngắn nhất . . . . . . . . . . . . . 42 3.2.2 Thuật toán tìm đường đi nhanh nhất . . . . . . . . . . . . 46KẾT LUẬN CHUNG 50TÀI LIỆU THAM KHẢO 51 DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊSố hiệu hình vẽ Tên hình vẽ Trang 1.1 Ví dụ về đơn đồ thị vô hướng 4 1.2 Ví dụ về đầy đủ K4 4 1.3 Ví dụ về đồ thị con cảm sinh 5 1.4 Ví dụ về hàng xóm và bậc của đỉnh 6 1.5 Ví dụ về đường đi và chu trình 7 1.6 Ví dụ về thành phần liên thông K4 8 1.7 Ví dụ liên thông trong đồ thị có hướng 8 2.1 Ví dụ về đồ thị luồng 15 2.2 Ví dụ về luồng liên kết 16 2.3 Mối quan hệ giữa đồ thị và luồng liên kết 17 2.4 Ví dụ về đồ thị luồng con cảm sinh 21 2.5 Ví dụ về đường trong đồ thị luồng 22 2.6 Ví dụ đồ thị luồng không liên thông yếu 25 2.7 Ví dụ đồ thị luồng không liên thông 26 mạnh 2.8 Ví dụ về cluster liên thông mạnh cực đại 27 2.9 Ví dụ thành phần liên thông trong ...