Luận án tiến sĩ đặc trưng không gian trạng thái và tính ổn định của một số hệ sandpile model mở rộng

Luận án tiến sĩ nghiên cứu đặc trưng không gian trạng thái và tính ổn định của các hệ sandpile model mở rộng, ứng dụng trong lý thuyết hệ động lực.

• Tác giả: Trần Thị Thu Hương
• Người hướng dẫn: PGS. Phan Thị Hà Dương
• Trường học: Viện Hàn Lâm Khoa Học Và Công Nghệ Việt Nam, Viện Toán Học
• Chuyên ngành: Cơ sở Toán học cho Tin học
• Đề tài: Đặc trưng không gian trạng thái và tính ổn định của các hệ Sandpile Model mở rộng
• Loại tài liệu: luận án tiến sĩ
• Năm xuất bản: 2014
• Địa điểm: Hà Nội

Tóm tắt

I. Luận án tiến sĩ

Luận án tiến sĩ này tập trung vào việc nghiên cứu đặc trưng không gian trạng thái và tính ổn định của các hệ Sandpile Model mở rộng. Luận án được thực hiện bởi Trần Thị Thu Hương dưới sự hướng dẫn của PGS. Phan Thị Hà Dương tại Viện Toán học, thuộc Viện Hàn lâm Khoa học và Công nghệ Việt Nam. Nghiên cứu này đóng góp vào lĩnh vực toán học ứng dụng và lý thuyết hệ thống, đặc biệt là trong việc mở rộng và phân tích các mô hình động lực rời rạc.

1.1. Mục tiêu nghiên cứu

Mục tiêu chính của luận án tiến sĩ là nghiên cứu tính ổn định và đặc trưng không gian trạng thái của các hệ Sandpile Model mở rộng. Luận án tập trung vào việc mở rộng các hệ động lực rời rạc như Sandpile Model (SPM) và Chip Firing Game (CFG), đồng thời phân tích cấu trúc không gian trạng thái và thời gian đạt được trạng thái ổn định. Nghiên cứu này nhằm mô tả tốt hơn các hệ thống trong thực tế và cung cấp các công cụ toán học để phân tích chúng.

1.2. Phương pháp nghiên cứu

Luận án sử dụng các phương pháp phân tích toán học và lý thuyết hệ thống để nghiên cứu các hệ Sandpile Model mở rộng. Các phương pháp bao gồm việc mở rộng luật thêm hạt vào hệ SPM, nghiên cứu cấu trúc dàn của các phân hoạch trơn, và đưa ra khái niệm năng lượng để mô tả sự biến thiên của hệ. Ngoài ra, luận án cũng sử dụng các công cụ từ lý thuyết đồ thị và tổ hợp để phân tích các hệ mở rộng như SPM đối xứng song song và CFG có dấu.

II. Đặc trưng không gian trạng thái

Đặc trưng không gian trạng thái là một trong những trọng tâm chính của luận án. Nghiên cứu này tập trung vào việc mô tả cấu trúc và tính chất của không gian trạng thái trong các hệ Sandpile Model mở rộng. Cụ thể, luận án chỉ ra rằng các phân hoạch trơn trong hệ SPM có cấu trúc dàn và là dàn con của dàn Young.

2.1. Cấu trúc dàn của phân hoạch trơn

Luận án chứng minh rằng tập các phân hoạch trơn trong hệ Sandpile Model mở rộng có cấu trúc dàn và là dàn con của dàn Young. Điều này được thực hiện thông qua việc nghiên cứu các luật thêm hạt và sự biến thiên của hệ. Cấu trúc dàn này giúp hiểu rõ hơn về sự ổn định và các trạng thái đạt được trong hệ.

2.2. Khái niệm năng lượng

Luận án đưa ra khái niệm năng lượng để mô tả sự biến thiên của hệ Sandpile Model mở rộng. Năng lượng được sử dụng để tính toán thời gian ngắn nhất và dài nhất để hệ đạt đến trạng thái ổn định. Khái niệm này cung cấp một công cụ hữu ích để phân tích sự ổn định của hệ dưới tác động từ bên ngoài.

III. Tính ổn định của hệ Sandpile Model mở rộng

Tính ổn định là một khía cạnh quan trọng được nghiên cứu trong luận án. Luận án tập trung vào việc phân tích sự ổn định của các hệ Sandpile Model mở rộng dưới tác động từ bên ngoài, đặc biệt là khi hệ được bổ sung luật thêm hạt.

3.1. Sự ổn định dưới tác động từ bên ngoài

Luận án nghiên cứu sự ổn định của hệ Sandpile Model mở rộng dưới tác động từ bên ngoài bằng cách bổ sung luật thêm hạt vào các cột hợp lý mỗi khi hệ đạt đến trạng thái ổn định. Nghiên cứu chỉ ra rằng có thể thu được tất cả các phân hoạch trơn bằng cách này, đồng thời chứng minh cấu trúc dàn của các phân hoạch trơn.

3.2. Thời gian đạt đến trạng thái ổn định

Luận án đưa ra các công thức tính thời gian ngắn nhất và dài nhất để hệ Sandpile Model mở rộng đạt đến trạng thái ổn định. Điều này được thực hiện thông qua việc sử dụng khái niệm năng lượng và phân tích các đường đi trong không gian trạng thái.

IV. Mở rộng hệ Sandpile Model

Luận án đề xuất và nghiên cứu các mở rộng của hệ Sandpile Model, bao gồm SPM đối xứng song song và CFG có dấu. Các mở rộng này nhằm mô tả tốt hơn các hệ thống trong thực tế và cung cấp các công cụ toán học để phân tích chúng.

4.1. Hệ SPM đối xứng song song

Luận án nghiên cứu hệ SPM đối xứng song song, trong đó các cột có thể rơi sang cả hai phía và các cột có thể rơi đồng thời. Nghiên cứu chỉ ra rằng hệ này có tập trạng thái ổn định có cùng hình dạng với hệ SPM đối xứng, đồng thời đưa ra các đánh giá về thời gian hội tụ.

4.2. Hệ CFG có dấu

Luận án mở rộng hệ Chip Firing Game thành hệ CFG có dấu, cho phép các đỉnh chứa số âm các chip và các đỉnh đủ âm cũng có thể bắn. Nghiên cứu chỉ ra các đẳng cấu giữa hệ SPM đối xứng và hệ CFG có dấu, đồng thời đặc trưng các trạng thái và tính toán tổ hợp liên quan đến số trạng thái ổn định.

Trích đoạn nội dung tài liệu

Chương 1 Hệ động lực rời rạc Chương này nhắc lại các kiến thức chuẩn bị, một số hướng nghiên cứu và các kết quả đã biết về hai hệ được nghiên cứu chính trong luận án: Hệ SPM (Sandpile model) và hệ CFG (Chip firing game).1 Các kiến thức chuẩn bị Luận án tập trung nghiên cứu hai hệ động lực rời rạc được quan tâm rất nhiều: hệ SPM (Sand pile model) và hệ CFG (Chip firing game). Hai hệ này được định nghĩa trên một đồ thị nền. Các kết quả trên hai hệ có liên quan nhiều đến một số tính toán tổ hợp trên các phân hoạch của số tự nhiên, cấu trúc thứ tự, cấu trúc dàn trên không gian các trạng thái của các hệ. Bởi vậy, trong phần này chúng tôi sẽ trình bày các kiến thức cơ sở về đồ thị, tập thứ tự, dàn, ngôn ngữ,.

được tham khảo chủ yếu trong [2, 13, 18, 37, 44, 45].1 Đồ thị Trước hết, chúng tôi trình bày các khái niệm cho đồ thị vô hướng sau đó sẽ đề cập tương tự cho đồ thị có hướng. Một đa đồ thị vô hướng là một cặp có thứ thự G = (V, E), trong đó V là một tập hợp khác rỗng, được gọi là tập đỉnh 13 của G, và E là một đa tập trong tập các cặp không phân biệt thứ tự {u, v}, với u, v ∈ V , được gọi là tập cạnh của G. Cho G là một đa đồ thị vô hướng. Nếu e = {u, v} ∈ E thì các đỉnh u, v được gọi là các đầu mút của e và u liên thuộc với e, hơn nữa, hai đỉnh u, v được gọi là liền kề, hay hàng xóm của nhau.

Nếu e = {u, u} thì e được gọi là một khuyên. Bậc của một đỉnh u ∈ V , ký hiệu là deg(u), là số các cạnh của G liên thuộc với u, trong đó các khuyên tại u được tính hai lần. Ta cũng thường ký hiệu cạnh {u, v} ngắn gọn là uv. Trong trường hợp tập cạnh E là một đa tập trong tập các cặp có phân biệt thứ tự V × V , thì G = (V, E) được gọi là một đa đồ thị có hướng và các phần tử thuộc E đôi khi còn gọi là các cung.

Với e = (u, v) ∈ E thì u được gọi là đỉnh đầu và v được gọi là đỉnh cuối của e và ta nói cạnh e đi từ u đến v. Bậc đi ra và bậc đi vào của đỉnh u ∈ V là số các cạnh đi ra từ u và đi vào u tương ứng, được ký hiệu lần lượt là deg+ (u) và deg− (u). Nếu giữa hai đỉnh u, v ∈ V của đồ thị G = (V, E) (có hướng hoặc vô hướng) có nhiều nhất một cạnh thì đồ thị G được gọi là đơn đồ thị (có hướng hoặc vô hướng tương ứng). Một đồ thị con của G là một đồ thị thu được từ G bằng cách xóa bớt đi một số đỉnh (và các cạnh liên thuộc với các đỉnh đó) và một số cạnh của G.

Một đồ thị con bao trùm của G nếu nó có tập đỉnh trùng với tập đỉnh của G. Đồ thị con cảm sinh bởi tập đỉnh V ′ ⊆ V của G, ký hiệu là G[V ′ ], là một đồ thị con của G với tập đỉnh là V ′ và tập các cạnh là tất cả các cạnh của G mà có hai đầu mút thuộc V ′. Một đường đi có hướng độ dài k từ đỉnh u đến đỉnh v trong G là dãy v0 ,. , vk sao cho v0 = u, vk = v, vi ∈ V và (vi , vi+1 ) ∈ E với mọi i = 0,.

Khi đó, đỉnh u được gọi là đỉnh đầu và đỉnh v được gọi là đỉnh cuối của đường đi. Đường đi đơn là một đường đi mà không có hai cạnh nào được lặp lại. Một chu trình của G là một đường đi sao cho đỉnh đầu và đỉnh cuối của nó là trùng nhau. Các khái niệm đường đi và chu trình trong trường hợp vô hướng được định nghĩa một cách tương tự.

Đồ thị có hướng được gọi là liên thông mạnh nếu giữa hai đỉnh tùy ý của nó có một đường đi có hướng. Tập S ⊆ V được gọi là một thành phần liên thông của đồ thị vô hướng G = (V, E) nếu G[S] là liên thông và với mọi S ′ ) S thì G[S ′ ] không liên thông. Tập S ⊆ V được gọi là một thành phần liên thông mạnh của đồ thị có hướng G = (V, E) nếu G[S] là liên thông mạnh và với mọi S ′ ) S thì G[S ′ ] không liên thông mạnh. Tập S ⊆ V được gọi là một thành phần đóng (closed component) của đồ thị có hướng G nếu S là một thành phần liên thông mạnh và không tồn tại cạnh nào của G đi ra từ một đỉnh trong S.

Tiếp theo, chúng tôi nhắc lại khái niệm của một dạng đồ thị đặc biệt được nghiên cứu và ứng dụng rất nhiều trong tin học bởi cấu trúc đơn giản của nó, được gọi là cây. Một đồ thị vô hướng, liên thông, không có chu trình được gọi là một cây. Dễ thấy rằng trong một cây thì số đỉnh nhiều hơn số cạnh đúng là 1. Hơn nữa, ta có các điều kiện tương đương thường được sử dụng để chứng minh tính chất cây như sau: Định lý 1.

Cho G = (V, E) là một đồ thị vô hướng và |V | = n. Các mệnh đề sau là tương đương: i) G là một cây. ii) G là liên thông và |E| = |V | − 1. iii) G không có chu trình và |E| = |V | − 1.

iv) Giữa hai đỉnh của G tồn tại duy nhất một đường đi đơn. v) G không có chu trình và nếu thêm bất kỳ cạnh nào vào G thì đồ thị nhận được sẽ có một chu trình đơn. 15 vi) G liên thông và nếu xóa bỏ bất kỳ cạnh nào của G thì đồ thị nhận được không còn liên thông nữa. Cho G là một đồ thị vô hướng.

Một cây bao trùm của G là một đồ thị con bao trùm của G sao cho nó là một cây. Có rất nhiều bài toán liên quan đến cây bao trùm của một đồ thị. Trong đó, bài toán nổi tiếng nhất là tính số cây bao trùm của một đồ thị cho trước. Số này thực chất được cho bởi định thức của ma trận biểu diễn đồ thị, được gọi là ma trận Laplace.

Bên cạnh đó, ma trận Laplace cùng với ma trận liền kề (ma trận biểu diễn sự liền kề nhau của các đỉnh trong đồ thị) cũng được dùng như là một công cụ để nghiên cứu nhiều bất biến cũng như các tính chất của đồ thị.2, chúng tôi cũng sẽ sử dụng các ma trận này để mô tả luật vận động của hệ CFG và dùng để nghiên cứu các tính chất nhóm cho hệ CFG này. Ma trận liền kề của G là ma trận A = (aij )n×n , trong đó aij là số các cạnh đi từ vi tới vj. Ma trận Laplace của G được cho bởi: ∆ = D − A, trong đó D là ma trận đường chéo với các phần tử trên đường chéo dii là số bậc (bậc đi ra) của đỉnh vi và A là ma trận liền kề của G. Từ định nghĩa, ta thấy tổng các phần tử trong một hàng của ma trận Laplace luôn bằng 0.

Do vậy, ∆ luôn có một vector riêng là 0 ứng với giá trị riêng là (1, 1,. Hơn nữa, trong trường hợp G là vô hướng thì các ma trận liền kề và ma trận Laplace của G là các ma trận đối xứng. Ta ký hiệu ma trận ∆∗ là ma trận rút gọn của ∆ bằng cách xóa đi hàng và cột thứ n. Định lý sau còn được gọi là định lý Kirchhoff.

Cho G là một đa đồ thị vô hướng có ma trận Laplace ∆. Khi đó, số cây bao trùm của G đúng bằng định thức của ma trận Laplace rút gọn ∆∗. 16 Một cách tương tự, chúng ta cũng có một phiên bản khác của Định lý 1.2 cho trường hợp G là đa đồ thị có hướng và có một đỉnh đặc biệt s (thường gọi là đỉnh chìm) mà không có cạnh đi ra từ nó. Trong đó, cây bao trùm sẽ có gốc tại s.

Cây bao trùm có gốc s là cây bao trùm của G (khi bỏ qua hướng) sao mọi đỉnh khác s đều có đường có hướng đi duy nhất tới s. Ký hiệu ∆(s) là ma trận Laplace rút gọn theo s của G bằng cách xóa hàng và cột tương ứng với s. Định lý được phát biểu lại như sau: Định lý 1. Cho G là một đa đồ thị có hướng và có duy nhất một đỉnh chìm s.

Khi đó, số cây bao trùm có gốc tại s của G đúng bằng định thức của ma trận Laplace rút gọn ∆(s). Với đồ thị đầy đủ bốn đỉnh K4 như Hình 1. −1 −1 −1 3 −1   −1 −1 3 −1 −1 −1 3 Ta có |∆∗ | = 9 và do đó K4 có 9 cây bao trùm.1: Đồ thị đầy đủ K4 17 Hình 1.2: Biểu đồ Ferrer của phân hoạch (4, 3, 2, 2, 2, 1) 1.2 Phân hoạch của số tự nhiên, tập thứ tự bộ phận và dàn Trong phần này chúng tôi sẽ trình bày các kiến thức cơ sở về phân hoạch, tập thứ tự và cấu trúc dàn của một tập thứ tự [2, 13, 44]. (i) Một phân hoạch (partition) là một dãy các số nguyên không âm a = (a1 , a2 ,.

, ak ) sao cho a1 ≥ a2 ≥. Khi đó, ai là các phần của a; và k là độ dài của a, ký hiệu l(a) = k. Chúng ta nói rằng a là một phân hoạch của một số P tự nhiên n, hay n là trọng số của a, và viết w(a) = n, nếu ki=1 ai = n. (ii) Một phân hoạch a được gọi là trơn nếu ai − ai+1 ≤ 1 với mọi i = 1, 2,.

(iii) Một phân hoạch a được gọi là chặt nếu ai − ai+1 ≥ 1 với mọi i = 1, 2,. Các biểu diễn hình học cho các phân hoạch thì không chỉ hữu ích về mặt trực quan mà còn được sử dụng để giải thích một cách dễ dàng cho nhiều tính chất của phân hoạch. Một trong những cách biểu diễn phổ biến được trình bảy ở đây là biểu đồ Ferrer. , ak ) là một phân hoạch.

Biểu đồ Ferrer biểu diễn a thành các cột liên tiếp nhau, trong đó cột thứ i gồm ai ô vuông xếp chồng lên nhau.2 minh họa biểu đồ Ferrer của phân hoạch (4, 3, 2, 2, 2, 1).