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 e 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 0 ⊆ V của G, ký hiệu là G[V 0 ], là một đồ thị con của G với tập đỉnh là V 0 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 0. 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 0 ) S thì G[S 0 ] 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 0 ) S thì G[S 0 ] 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 e 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 e 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 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 e 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ố 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. P (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).