I. Kiến thức chuẩn bị về đồ thị
Phần này trình bày các khái niệm cơ bản về đồ thị, bao gồm định nghĩa và các loại đồ thị khác nhau. Đồ thị được định nghĩa là một tập hợp các đỉnh và các cạnh nối giữa chúng. Các loại đồ thị như đồ thị đơn, đa đồ thị, và đồ thị có hướng được mô tả chi tiết. Đặc biệt, các khái niệm như chu trình, đồ thị đầy đủ, và đồ thị hai phía cũng được giới thiệu. Những kiến thức này là nền tảng cho việc hiểu mô hình trò chơi chip firing trong các phần sau của luận văn. Việc nắm vững các khái niệm này giúp người đọc có cái nhìn tổng quát về cấu trúc và tính chất của đồ thị, từ đó áp dụng vào các thuật toán và mô hình phức tạp hơn.
1.1. Các khái niệm cơ bản
Trong phần này, các khái niệm cơ bản về đồ thị được trình bày. Đồ thị G = (V, E) được xác định bởi tập hợp các đỉnh V và tập hợp các cạnh E. Đồ thị đơn có không quá một cạnh giữa hai đỉnh, trong khi đa đồ thị có thể có nhiều hơn một cạnh. Đồ thị có hướng được xác định bởi các cạnh có hướng từ đỉnh này đến đỉnh khác. Các khái niệm như bậc của đỉnh, lân cận của đỉnh, và các định lý liên quan đến đồ thị cũng được thảo luận. Những khái niệm này là rất quan trọng trong việc phân tích và xây dựng các mô hình trong trò chơi chip firing.
1.2. Một số dạng đồ thị và ví dụ
Phần này giới thiệu một số dạng đồ thị phổ biến như chu trình, đồ thị đầy đủ, và đồ thị bánh xe. Chu trình Cn là đồ thị đơn có n đỉnh với bậc của mỗi đỉnh bằng 2. Đồ thị đầy đủ Kn là đồ thị mà mọi cặp đỉnh đều được nối với nhau. Đồ thị bánh xe Wn có một đỉnh trung tâm nối với tất cả các đỉnh khác. Những ví dụ này giúp người đọc hình dung rõ hơn về cấu trúc của các loại đồ thị khác nhau và cách chúng có thể được áp dụng trong các mô hình toán học, đặc biệt là trong trò chơi chip firing.
II. Chip firing game trên đồ thị
Chương này trình bày mô hình trò chơi chip firing (CFG) trên đồ thị, bao gồm các quy tắc và tính chất của trò chơi. Mô hình CFG được định nghĩa là một hệ động lực rời rạc, trong đó mỗi đỉnh của đồ thị chứa một số chip. Khi một đỉnh được bắn, số chip tại đỉnh đó giảm đi và các đỉnh kề nhận thêm chip. Trò chơi kết thúc khi không còn đỉnh nào có thể bắn. Tính hữu hạn của CFG được phân tích, cho thấy rằng trò chơi có thể kết thúc sau một số bước hữu hạn hoặc có thể kéo dài vô hạn tùy thuộc vào cấu hình ban đầu của chip. Điều này có ý nghĩa quan trọng trong việc hiểu cách thức hoạt động của CFG và ứng dụng của nó trong các lĩnh vực khác nhau.
2.1. Mô hình CFG trên đồ thị
Mô hình trò chơi chip firing được giới thiệu với các quy tắc cụ thể. Mỗi đỉnh có thể bắn nếu số chip tại đỉnh đó lớn hơn hoặc bằng bậc của nó. Khi bắn, chip từ đỉnh đó được phân phối cho các đỉnh kề. Cấu hình ban đầu của chip được xác định và các bước bắn được thực hiện cho đến khi không còn đỉnh nào có thể bắn. Điều này tạo ra một chuỗi các cấu hình chip, và việc phân tích các cấu hình này giúp hiểu rõ hơn về động lực của trò chơi. Mô hình này không chỉ có giá trị lý thuyết mà còn có thể được áp dụng trong các bài toán thực tiễn liên quan đến phân phối tài nguyên.
2.2. Tính hữu hạn của CFG
Tính hữu hạn của CFG được phân tích thông qua các điều kiện cụ thể. Nếu số chip lớn hơn một ngưỡng nhất định, trò chơi có thể kéo dài vô hạn. Ngược lại, nếu số chip nhỏ hơn một ngưỡng khác, trò chơi sẽ kết thúc sau một số bước hữu hạn. Điều này cho thấy mối liên hệ giữa cấu hình ban đầu và kết quả của trò chơi. Việc hiểu rõ tính hữu hạn của CFG không chỉ giúp trong việc dự đoán kết quả của trò chơi mà còn có thể áp dụng trong các lĩnh vực như tối ưu hóa và lý thuyết đồ thị.
III. CFG song song trên đồ thị
Chương này tập trung vào mô hình trò chơi chip firing song song (CFG song song) trên đồ thị. Mô hình này mở rộng từ CFG cơ bản, cho phép nhiều đỉnh có thể bắn đồng thời. Điều này tạo ra một động lực phức tạp hơn và có thể dẫn đến các chu kỳ khác nhau trong trò chơi. Phân tích chu kỳ của CFG song song cho thấy rằng số lần bắn của mỗi đỉnh trong một chu kỳ là như nhau, điều này có ý nghĩa quan trọng trong việc hiểu cách thức hoạt động của trò chơi trong các điều kiện khác nhau.
3.1. Mô hình CFG song song trên đồ thị
Mô hình CFG song song được định nghĩa với các quy tắc cho phép nhiều đỉnh bắn đồng thời. Điều này tạo ra một cấu hình phức tạp hơn so với CFG cơ bản. Các đỉnh có thể tương tác với nhau, dẫn đến sự thay đổi trong cấu hình chip nhanh chóng. Việc phân tích mô hình này giúp hiểu rõ hơn về cách thức hoạt động của các hệ thống phức tạp và có thể áp dụng trong nhiều lĩnh vực khác nhau, từ lý thuyết mạng đến tối ưu hóa.
3.2. Chu kỳ của chips trên cây
Chu kỳ của CFG song song trên cây được phân tích để hiểu rõ hơn về động lực của trò chơi. Các chu kỳ này cho thấy rằng trong một chu kỳ, mỗi đỉnh được bắn số lần như nhau. Điều này có thể được chứng minh thông qua các tính chất của ma trận Laplace. Việc hiểu rõ chu kỳ của CFG song song không chỉ có giá trị lý thuyết mà còn có thể áp dụng trong các bài toán thực tiễn liên quan đến phân phối tài nguyên và tối ưu hóa.
