Luận văn Thạc sĩ Toán học: Chu kỳ của chip-firing game song song trên đồ thị

Trong những năm gần đây, mô hình Chip-firing game (CFG) đã thu hút rất nhiều nhà nghiên cứu, nhiều công trình đã được công bố. CFG đã trở thành một phần quan trọng trong cấu trúc tổ hợp (structural combinatoric). Trong khuôn khổ của luận văn chỉ trình bày các kết quả trên đồ thị hữu hạn, liên thông, đơn và vô hướng.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Toán học: Chu kỳ của chip-firing game song song trên đồ thị 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Ệ ----------------------------- Mai Thu HuyềnCHU KỲ CỦA CHIP-FIRING GAME SONG SONG TRÊN ĐỒ THỊ 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Ệ ----------------------------- Mai Thu HuyềnCHU KỲ CỦA CHIP-FIRING GAME SONG SONG TRÊN ĐỒ THỊ Chuyên ngành: Toán ứng dụng Mã số: 8460112 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC TS. Nguyễn Hoàng Thạch Hà Nội - 2019 iLời cam đoan Tôi xin cam đoan mọi kết quả của đề tài: Chu kỳ của chip-firing gamesong song trên đồ thị được trình bày lại từ hai bài báo [3] và [4]. Các ví dụ vàsố liệu trong luận văn là trung thực và chưa được công bố trong các công trìnhkhác. Nếu không đúng như đã nêu trên, tôi xin hoàn toàn chịu trách nhiệm vềđề tài của mình. Hà Nội, ngày 25 tháng 11 năm 2019 Mai Thu HuyềnLời cảm ơn Tôi xin bày tỏ lòng biết ơn tới TS. Nguyễn Hoàng Thạch, thầy đã hướngdẫn, tạo mọi điều kiện thuận lợi và giúp đỡ tôi rất nhiều trong quá trình họctập và làm luận văn. Thầy đã truyền cảm hứng và giúp tôi hoàn thiện bản thânrất nhiều sau quá trình làm việc cùng thầy. Tôi xin gửi lòng cảm ơn tới tất cả thầy cô của Viện Toán Học đã truyền đạtcác kiến thức chuyên sâu và ý nghĩa của việc học Toán trong hai năm học. Tôixin cảm ơn tới tất cả thầy cô và các anh chị của Học viện Khoa học và Côngnghệ đã giúp đỡ và quan tâm tôi rất nhiều trong quá trình học tập. Cuối cùng, tôi xin gửi lời tri ân tới bố mẹ, những người thân trong gia đìnhvà bạn bè đã luôn ủng hộ, khích lệ và động viên tinh thần trong suốt quá trìnhhọc tập để hoàn thành tốt luận văn thạc sĩ của mình. Hà Nội, ngày 25 tháng 11 năm 2019 Mai Thu HuyềnDanh mục kí hiệu CF G Mô hình chip-firing game Cn Chu trình n đỉnh Kn Đồ thị đầy đủ n đỉnh Wn Đồ thị bánh xe n đỉnh C(t) Cấu hình chip tại thời điểm t Cv (t) Cấu hình chip của đỉnh v tại thời điểm t L Ma trận Laplace fvi (t) Vết của đỉnh vi tại thời điểm t trong chu kỳ T Ski Tập lớn nhất của các kí tự 1 Dki Tập lớn nhất của các kí tự 0Danh sách hình vẽ 1.1 Một ví dụ về đồ thị đơn . . . . . . . . . . . . . . . . . . . . . 4 1.2 Một ví dụ về đa đồ thị . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Một ví dụ về đồ thị có khuyên . . . . . . . . . . . . . . . . . 5 1.4 Một ví dụ về đồ thị có hướng . . . . . . . . . . . . . . . . . . 5 1.5 Một ví dụ về đồ thị đơn có hướng (a), đa đồ thị có hướng (b) . 6 1.6 Một ví dụ về chu trình: (a) C3 , (b)C4 , (c) C5 . . . . . . . . . . 8 1.7 Một ví dụ về đồ thi đầy đủ: (a) K4 , (b) K5 . . . . . . . . . . . 8 1.8 Đồ thị hai phía đầy đủ: (a) K2,3 , (b) K3,3 . . . . . . . . . . . . 9 1.9 Đồ thị bánh xe: (a) W3 , (b) W4 , (c) W5 . . . . . . . . . . . . . 9 1.10 Đồ thi liên thông . . . . . . . . . . . . . . . . . . . . . . . . 10 1.11 Đồ thị không liên thông . . . . . . . . . . . . . . . . . . . . . 10 1.12 Cây . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1 Cấu hình ban đầu của chip trên đồ thị . . . . . . . . . . . . . 14 2.2 Bắn chip trên chu trình C3 . . . . . . . . . . . . . . . . . . . 14 2.3 Bắn chip trên đồ thị . . . . . . . . . . . . . . . . . . . . . . . 17 2.4 Đồ thị cho ma trận Laplace . . . . . . . . . . . . . . . . . . . 18 2.5 Cấu hình chip ban đầu trên chu trình C6 . . . . . . . . . . . . 20 3.1 Cấu hình ban đầu của chip trên đường đi . . . . . . . . . . . . 22 3.2 Cấu hình ban đầu của chip trên đồ thị . . . . . . . . . . . . . 23 3.3 Cấu hình ban đầu của chip trên chu trình . . . . . . . . . . . . 25 3.4 Cây có chu kỳ T = 2 . . . . . . . . . . . . . . . . . . . . . . 30 3.5 Chu trình có chu kỳ T = 5 . . . . . . . . . . . . . . . . . . . 31Danh sách bảng 2.1 Bắn chip trên chu trình C6 . . . . . . . . . . . . . . . . . . . 20 3.1 Bắn chip song song trên đường đi . . . . . . . . . . . . . . . . 22 3.2 CFG song song trên chu trình . . . . . . . . . . . . . . . . . . 25 3.3 CFG song song trên chu trình 5 đỉnh . . . . . . . . . . . . . . 31 1Mục lục1 KIẾN THỨC CHUẨN BỊ VỀ ĐỒ THỊ 3 1.1 CÁC KHÁI NIỆM CƠ BẢN . . . . . . . . . . . . . . . . . . 3 1.2 MỘT SỐ DẠNG ĐỒ THỊ VÀ VÍ DỤ . . . . . . . . . . . . . 7 1.3 ĐƯỜNG ĐI, CHU TRÌNH VÀ TÍNH LIÊN THÔNG . . . . . 8 1.4 CÂY . . . . . . . . . . . . . . . . . . . . . . . . . . . ...