Luận văn Thạc sĩ Khoa học: Ứng dụng đồ thị tìm ước số và xác định tập đồng dư

Lý thuyết đồ thị là một chuyên ngành toán học hiện đại đã được ứng dụng vào nhiều ngành khoa học, kỹ thuật khác nhau, bởi vì lý thuyết đồ thị là phương pháp khoa học có tính khái quát cao và có tính ổn định vững chắc vì thế thông qua đồ thị có thể mã hóa các mối quan hệ của các đối tượng được nghiên cứu.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Khoa học: Ứng dụng đồ thị tìm ước số và xác định tập đồng dư ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------ PHẠM THỊ THỦY ỨNG DỤNG ĐỒ THỊTÌM ƯỚC SỐ VÀ XÁC ĐỊNH TẬP ĐỒNG DƯ LUẬN VĂN THẠC SỸ TOÁN HỌC Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60 46 01 13 NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TS. ĐẶNG HUY RUẬN Hà Nội - Năm 2013Mục lụcMỞ ĐẦU 21 MỘT SỐ KHÁI NIỆM CƠ BẢN 4 1.1 Các khái niệm cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.1 Định nghĩa đồ thị . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.2 Biểu diễn đồ thị bằng hình học . . . . . . . . . . . . . . . 6 1.1.3 Xích, chu trình, đường và vòng . . . . . . . . . . . . . . . 7 1.1.4 Đồ thị liên thông và chu số . . . . . . . . . . . . . . . . . 10 1.2 Đồ thị được gán nhãn . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.2 Nguồn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 CÂY SINH ƯỚC 16 2.1 Cây . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.2 Đặc điểm của cây và cây có hướng . . . . . . . . . . . . . . 18 2.2 Cây sinh ước . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2.2 Thuật toán xây dựng cây sinh ước . . . . . . . . . . . . . . 22 2.2.3 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 NGUỒN ĐỒNG DƯ 27 3.1 Nguồn đồng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.1.1 Định nghĩa nguồn đồng dư . . . . . . . . . . . . . . . . . . 27 3.1.2 Định nghĩa Euclid . . . . . . . . . . . . . . . . . . . . . . . 27 3.1.3 Thuật toán xây dựng nguồn đồng dư . . . . . . . . . . . . . 28 3.2 Nguồn giao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 1MỞ ĐẦU Toán học rời rạc nghiên cứu các cấu trúc có tính chất rời rạc không liên tục.Toán rời rạc bao gồm các lĩnh vực như quan hệ, lý thuyết đồ thị, logic toán,ngôn ngữ hình thức . . . , trong đó lý thuyết đồ thị là một bộ phận trọng tâm vớinhiều khối lượng kiến thức khá lý thú và được nghiên cứu nhiều nhất. Lý thuyết đồ thị là một chuyên ngành toán học hiện đại đã được ứng dụngvào nhiều ngành khoa học, kỹ thuật khác nhau, bởi vì lý thuyết đồ thị là phươngpháp khoa học có tính khái quát cao và có tính ổn định vững chắc vì thế thôngqua đồ thị có thể mã hóa các mối quan hệ của các đối tượng được nghiên cứu. Vận dụng lý thuyết đồ thị để mô hình hóa các mối quan hệ trong giảng dạysẽ chuyển thành phương pháp dạy học đặc thù và nâng cao được hiệu quả giảngdạy thúc đẩy quá trình tự học, tự nghiên cứu của học sinh theo hướng tối ưuhóa. Đặc biệt việc vận dụng lý thuyết đồ thị trong giảng dạy còn nhằm rèn luyệnnăng lực hệ thống hóa kiến thức và năng lực sáng tạo của học sinh. Từ nhận thức trên, đề tài Ứng dụng đồ thị tìm ước số và xác định tập đồng dưkhông những là nhiệm vụ em phải thực hiện trong kỳ bảo vệ luận văn tốt nghiệp,mà thực sự là đề tài em rất quan tâm và say mê nghiên cứu. “Ứng dụng đồ thị tìm ước số và tập đồng dư” là đề tài mang tính nghiên cứulý thuyết, có tầm quan trọng và ý nghĩa thiết thực cao. Luận văn bao gồm phần mở đầu và ba chương: Chương 1. Một số khái niệm cơ bản Nhằm trình bày những khái niệm cơ bản nhất về đồ thị, là cơ sở tìm hiểu sâusắc hơn các vấn đề tiếp theo. Mỗi phần gồm: Định nghĩa, định lý và các tínhchất cơ bản của đồ thị. Ngoài ra, trong chương này còn trình bày một số phươngpháp biểu diễn đồ thị, mỗi phương pháp đều có những ưu và nhược điểm riêng,vì vậy cần lựa chọn phương pháp, sao cho phù hợp với đặc điểm từng bài toánvà đạt được hiệu quả về thuật toán. 2MỞ ĐẦU Chương 2. Cây sinh ước Cây là một trường hợp riêng của đồ thị, để nghiên cứu hết các tính chất,khái niệm về cây cần cả một khối lượng kiến thức đồ sộ và đã có những đề tàinghiên cứ ...