Tài liệu định lý dạng riemann roch cho đồ thị và cách tính hạng trên một số đồ thị đặc biệt

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VN VIỆN TOÁN HỌC ------ VŨ NAM PHONG ĐỊNH LÝ DẠNG RIEMANN-ROCH CHO ĐỒ THỊ VÀ CÁCH TÍNH HẠNG TRÊN MỘT SỐ ĐỒ THỊ ĐẶC BIỆT LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội - 2015 BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VN VIỆN TOÁN HỌC VŨ NAM PHONG ĐỊNH LÝ DẠNG RIEMANN-ROCH CHO ĐỒ THỊ VÀ CÁCH TÍNH HẠNG TRÊN MỘT SỐ ĐỒ THỊ ĐẶC BIỆT Chuyên ngành : Toán ứng dụng Mã số : 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: PGS.TS. Phan Thị Hà Dương Hà Nội - 2015 Mục lục Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Danh mục kí hiệu . . . . . . . . . . . . . . . . . . . . . . . 4 1 CÁC KHÁI NIỆM CƠ BẢN 6 2 CẤU HÌNH TRÊN ĐỒ THỊ 19 2.1 Cấu hình và các khái niệm liên quan . . . . . . . . . . . 19 2.2 Các mô hình CF G . . . . . . . . . . . . . . . . . . . . . 21 2.3 Một số loại cấu hình đặc biệt . . . . . . . . . . . . . . . 22 2.4 Cấu hình trên đồ thị đầy đủ . . . . . . . . . . . . . . . . 34 2.5 Từ Dyck và sự liên hệ với cấu hình trên đồ thị đầy đủ . . 37 3 HẠNG CỦA CẤU HÌNH TRÊN ĐỒ THỊ 45 3.1 Các khái niệm cơ bản và tính chất của hạng . . . . . . . 45 3.2 Định lý dạng Riemann-Roch cho đồ thị . . . . . . . . . . 50 3.3 Tính hạng của cấu hình trên đồ thị đầy đủ không dùng từ Dyck . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Thuật toán tính hạng của cấu hình trên đồ thị đầy đủ . 56 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . 63 3.4 1 Lời nói đầu Trong những năm gần đây, mô hình CF G (Chip-firing game) đã thu hút sự chú ý của rất nhiều nhà nghiên cứu, nhiều công trình đã được công bố. Trong đó, M. Baker và S. Norine đã đưa ra một khái niệm mới, đó là hạng của cấu hình trên đồ thị ở [2] vào năm 2007. Bài toán tính hạng của cấu hình trên đồ thị bất kì là khó, luận văn này sẽ trình bầy một số tính chất chính về hạng của cấu hình trên đồ thị tổng quát và đưa ra cách tính hạng của cấu hình trên đồ thị đầy đủ, một loại đồ thị có tính đối xứng cao. Luận văn gồm ba chương. Chương 1 trình bày một số định nghĩa và kết quả sẽ được sử dụng trong Chương 2 và Chương 3. Đó là các khái niệm và tính chất cơ bản của đồ thị. Chương 2 trình bày các định nghĩa, các tính chất của cấu hình trên đồ thị và các dạng của mô hình CF G. Các kết quả được trình bầy cho đồ thị tổng quát và một dạng đồ thị đặc biệt, đồ thị đầy đủ. Chương 3 trình bày định nghĩa, tính chất và cách tính của hạng của cấu hình trên đồ thị, cả trong đồ thị tổng quát và trong một số dạng đồ thị đặc biệt: đồ thị cây, đơn đồ thị 2-chính quy, đồ thị đầy đủ; trong đó, 2 Lời nói đầu việc tính hạng cho đồ thị đầy đủ sẽ được trình bầy chi tiết. Luận văn được hoàn thành tại Viện Toán học, Viện Hàn lâm Khoa học và Công nghệ Việt Nam, dưới sự hướng dẫn của PGS. TS. Phan Thị Hà Dương. Tác giả chân thành cảm ơn cô Phan Thị Hà Dương đã tận tình hướng dẫn, giúp đỡ tác giả rất nhiều trong quá trình làm luận văn. Tác giả cũng xin bày tỏ lòng biết ơn các thầy cô, các anh chị và các bạn trong nhóm nghiên cứu của cô Phan Thị Hà Dương, các thầy cô và cán bộ công nhân viên của Viện Toán học đã quan tâm giúp đỡ trong suốt quá trình học tập và nghiên cứu tại Viện. Hà Nội, ngày 31 tháng 08 năm 2015 Vũ Nam Phong 3 Danh mục kí hiệu CF G mô hình Chip-firing game Kn đồ thị đầy đủ n đỉnh ∀i = 1, n ∀i ∈ {1, 2, ..., n} ei,j số cạnh có hai đầu là xi , xj deg(v) bậc của đỉnh v di bậc của đỉnh xi d− i bậc đi vào của đỉnh xi deg(f ) bậc của cấu hình f ∆ ma trận Laplace ∆′ ma trận Laplace thu gọn 0 cấu hình có tất cả các vị trí đều là 0 ε(i) cấu hình có vị trí thứ i là 1, các vị trí còn lại là 0 δ cấu hình thỏa mãn δi = di − 1 ∀i = 1, n κ cấu hình thỏa mãn κi = di − 2 ∀i = 1, n ∆(i) cấu hình Laplace f ∼ LG g f, g là hai cấu hình tương đương f ≁ LG g f, g là hai cấu hình không tương đương x i f −→ g cấu hình f bắn chip tại đỉnh xi thì được cấu hình g 4 Danh mục kí hiệu ∗ f → g cấu hình f sau một loạt các phép bắn chip thì được cấu hình g |w|x số lần xuất hiện của chữ cái x trong từ w |w| độ dài của từ w An tập hợp các từ có đúng n − 1 chữ cái a và n chữ cái b P tập hợp các cấu hình hiệu quả trên đồ thị G E tập hợp các cấu hình hiệu quả-LG trên đồ thị G ρ(f ) hạng của cấu hình f 5 Chương 1 CÁC KHÁI NIỆM CƠ BẢN Phần này trình bày cơ bản một số kiến thức về đồ thị, các kiến thức này được tham khảo từ [1], đó là kiến thức cơ sở được sử dụng trong các phần tiếp theo của luận văn. Định nghĩa 1.0.1. (Đồ thị vô hướng) Một đồ thị vô hướng G là một cặp có thứ tự G = (V, E), với V là một tập, còn E là tập với các phần tử là các đa tập lực lượng hai trên V. Các phần tử của V được gọi là đỉnh, còn các phần tử của E được gọi là các cạnh của đồ thị vô hướng G. Nếu e = {a, b} là một cạnh của G thì a,b được gọi là các đỉnh liên thuộc với e. Cạnh có dạng {a, a} với a ∈ V được gọi là khuyên. Định nghĩa 1.0.2. (Đồ thị có hướng) Một đồ thị có hướng G là một cặp có thứ tự G = (V, E), với V là một tập, còn E là một tập con của tích Đề các V × V . Các phần tử của V được gọi là các đỉnh của đồ thị có hướng G, còn các phần tử của E được 6 Chương 1. CÁC KHÁI NIỆM CƠ BẢN gọi là các cung của đồ thị có hướng G. Cụ thể, nếu (a, b) ∈ E thì (a,b) được gọi là cung của G với đỉnh đầu là a, đỉnh cuối là b và có hướng đi từ a đến b. Nếu (a, b) ∈ E thì các đỉnh a và b được gọi là liên thuộc với cung (a,b) cũng được gọi là kề nhau. Cung có dạng (a,a) với a ∈ V được gọi là khuyên. Đỉnh không liên thuộc với cung nào được gọi là đỉnh cô lập. Số các đỉnh của G được gọi là cấp của đồ thị G, còn số cung của G được gọi là cỡ của đồ thị G. Hình 1.1: Đồ thị vô hướng G Hình 1.2: Đồ thị có hướng G Định nghĩa 1.0.3. (Đa đồ thị) Một đa đồ thị vô hướng G là một cặp có thứ tự G = (V, E), trong đó V 7 Chương 1. CÁC KHÁI NIỆM CƠ BẢN là một tập còn E là một đa tập với các phần tử đều là các đa tập lực lượng hai trên V. Các phần tử của V được gọi là các đỉnh, còn các phần tử của E được gọi là các cạnh của đa đồ thị G. Một đa đồ thị có hướng G là một cặp có thứ tự G = (V, E), trong đó V là một tập, còn E là một đa tập với các phần tử đều thuộc tích Đề các V × V . Các phần tử của V được gọi là các đỉnh, còn các phần tử của E được gọi là các cung của đa đồ thị có hướng G. Hình 1.3: Đa đồ thị vô hướng G Hình 1.4: Đa đồ thị có hướng G Định nghĩa 1.0.4. (Bậc của đỉnh của đồ thị) Cho G = (V, E) là một (đa) đồ thị vô hướng. Với đỉnh v ∈ V , đặt NG (v) = {{v, u} ∈ E : u ∈ V }. Lực lượng của NG (v) được gọi là bậc 8 Chương 1. CÁC KHÁI NIỆM CƠ BẢN của đỉnh v trong G, được ký hiệu bởi deg(v) = |NG (v)| với |A| là kí hiệu số phần tử của tập A. Cho G = (V, E) là một (đa) đồ thị có hướng. Với đỉnh v ∈ V , đặt N + (v) = {(v, x) ∈ E : x ∈ V }, và N − (v) = {(y, v) ∈ E : y ∈ V }. Khi đó lực lượng của N + (v) được gọi là bậc đi ra của v, và được ký hiệu là deg + (v) = |N + (v)|. Còn lực lượng của N − (v) được gọi là bậc đi vào của v, và được ký hiệu là deg − (v) = |N − (v)|. Định lý sau đây cho một tính chất cơ bản về bậc của đồ thị. Định lý 1.0.1. [1] Cho G = (V, E) là một (đa) đồ thị vô hướng. Khi đó X deg(v) = 2|E| v∈V Cho G = (V, E) là một (đa) đồ thị có hướng, khi đó: X v∈V + deg (v) = X deg− (v) = |E| v∈V Định nghĩa 1.0.5. (Hành trình, đường, chu trình) Cho (đa) đồ thị có hướng G = (V, E). Một hành trình có hướng trong G là một dãy v0 e1 v1 e2 v2 ...en vn sao cho vi ∈ V ∀i = 1, n, còn ei ∈ E ∀i = 1, n và ei = (vi−1 , vi ). Khi đó, v0 được gọi là đỉnh đầu, vn được gọi là đỉnh cuối và n được gọi là độ dài của hành trình. Một hành trình vô hướng trong G là một dãy v0 e1 v1 e2 v2 ...en vn sao cho vi ∈ V ∀i = 1, n, còn ei ∈ E ∀i = 1, n và có một trong hai điều sau 9 Chương 1. CÁC KHÁI NIỆM CƠ BẢN ei = (vi−1 , vi ) hoặc ei = (vi , vi−1 ). Khi đó v0 được gọi là đỉnh đầu, vn được gọi là đỉnh cuối và n được gọi là độ dài của hành trình Một hành trình có hướng (tương ứng, vô hướng) được gọi là khép kín nếu đỉnh đầu và đỉnh cuối trùng nhau Một hành trình có hướng (tương ứng, vô hướng) mà trong đó các đỉnh đều khác nhanh được gọi là một đường có hướng (tương ứng, vô hướng). Một hành trình có hướng (tương ứng, vô hướng) khép kín mà khi xóa đỉnh cuối thì nó trở thành một đường có hướng (tương ứng, vô hướng) được gọi là chu trình có hướng (tương ứng, vô hướng). Hành trình, đường và chu trình của đồ thị vô hướng được định nghĩa tương tự. Hình 1.5: (a) Đa đồ thị vô hướng G (trái) và (b) Đa đồ thị có hướng G (bên phải) Ví dụ 1.0.1. Trong đa đồ thị vô hướng G như Hình 1.5 (a) (a) v1 e1 v2 e4 v3 e6 v4 e3 v2 là một hành trình của G. (b) v1 e2 v2 e4 v3 e7 v4 là một đường của G. (c) v1 e1 v2 e4 v3 e5 v1 là một chu trình của G. 10 Chương 1. CÁC KHÁI NIỆM CƠ BẢN Trong đa đồ thị có hướng G như Hình 1.5 (b) (a) v1 e10 v5 e8 v4 e6 v1 e5 v3 là một hành trình có hướng của G. (b) v1 e5 v3 e4 v2 là một đường có hướng của G. (c) v1 e1 v2 e3 v3 e7 v5 là một đường vô hướng của G. (d) v1 e10 v5 e8 v4 e6 v1 là một chu trình có hướng của G. Định nghĩa 1.0.6. (Đồ thị con) Đồ thị vô hướng H = (V ′ , E ′ ) được gọi là đồ thị con của đồ thị vô hướng G = (V, E) nếu V ′ ⊆ V và E ⊆ E ′ Đồ thị con H = (V ′ , E ′ ) của đồ thị G = (V, E) được gọi là đồ thị con bao trùm của G nếu V ′ =V. Đồ thị con cảm sinh bởi tập đỉnh V ′ ⊆ V của G, được ký hiệu là G[V ′ ], là một đồ thị con của G với tập đỉnh là V ′ và các cạnh là tất cả các cạnh của G có hai đầu mút thuộc V ′ . Đồ thị con, đồ thị con bao trùm và đồ thị con cảm sinh của đồ thị có hướng được định nghĩa tương tự. Định nghĩa 1.0.7. (Tính liên thông) Đồ thị (đa đồ thị) vô hướng G được gọi là liên thông nếu có đường đi giữa hai đỉnh bất kỳ trong đồ thị G. Đồ thị (đa đồ thị) có hướng G được gọi là liên thông mạnh nếu có đường đi có hướng giữa hai đỉnh bất kỳ trong đồ thị G. Tập S ⊆ V được gọi là 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 11 Chương 1. CÁC KHÁI NIỆM CƠ BẢN liên thông. Tập S ⊆ V được gọi là 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. Hình 1.6: (a) Đồ thị vô hướng G có hai thành phần liên thông S1 = {v1 , v2 , v3 } và S2 = {v4 , v5 , v6 , v7 , v8 } (trái) và (b) Đồ thị có hướng G có hai thành phần liên thông yếu S1 = {v1 , v2 , v3 , v4 , v5 , v6 , v7 }, S2 = {v8 , v9 , v10 , v11 , v12 , v13 , v14 } và có bốn thành phần liên thông mạnh V1 = {v1 , v2 , v3 }, V2 = {v4 , v5 , v6 , v7 }, V3 = {v8 , v9 , v10 , v11 }, V4 = {v12 , v13 , v14 } (bên phải) Định nghĩa 1.0.8. (Cây) Cây là đồ thị vô hướng liên thông, không có khuyên, không có chu trình. Ta thấy rằng, trong một cây thì có số đỉnh nhiều hơn số cạnh là 1. Hơn nữa, ta còn có các điều kiện tương đương với định nghĩa cây thường được sử dụng để chứng minh tính chất cây như sau: Định lý 1.0.2. Cho G = (V, E) là một đồ thị vô hướng, không khuyên. Các mệnh đề sau là tương đương: (1) G là một cây. (2) G là liên thông và |E| = |V | − 1. 12 Chương 1. CÁC KHÁI NIỆM CƠ BẢN (3) G không có chu trình và |E| = |V | − 1. (4) Giữa hai đỉnh của G tồn tại duy nhất một đường đi. (5) Không có chu trình và nếu thêm bất kỳ một cạnh nối hai đỉnh không kề nhau trong G thì đồ thị nhận được có đúng một chu trình. (6) 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. Định nghĩa 1.0.9. (Cây bao trùm) Cây bao trùm của đồ thị liên thông G là một đồ thị con của G chứa tất cả các đỉnh của G, liên thông và không có chu trình. Ví dụ 1.0.2. Hình 1.7: (a) Đa đồ thị vô hướng G (trên) và (b) Các cây bao trùm của G (dưới) Định nghĩa 1.0.10. Cho G = (V, E) là một đa đồ thị vô hướng, không có khuyên, với V = {v1 , v2 , . . . , vn } và E = {e1 , e2 , . . . , em }. Ta xác định một hướng tùy ý O trên G, tức là với mỗi cạnh e nối hai đỉnh vi với vj chúng ta chọn một hướng cho e. Nếu hướng từ vi đến vj thì ta nói vi là 13 Chương 1. CÁC KHÁI NIỆM CƠ BẢN đỉnh đầu còn vj là đỉnh cuối. Ma trận liên thuộc M của G (tương ứng với hướng O đã chọn) là ma trận cỡ n × m với các phần tử được xác định như sau:    1 nếu vi là đỉnh đầu của cạnh ej     Mij = −1 nếu vi là đỉnh cuối của cạnh ej      0 nếu vi không liên thuộc với cạnh ej với 1 ≤ i ≤ n, 1 ≤ j ≤ m. Ma trận kề A của G là ma trận cấp n × n với các phần tử Aij = ei,j , trong đó ei,j là số cạnh nối hai đỉnh vi với vj , 1 ≤ i, j ≤ n. Ma trận Laplace ∆ của đồ thị G là ma trận cỡ n × n mà các phần tử của nó được xác định bởi ∆ij =   −ei,j nếu i 6= j  deg(v ) i , nếu i = j trong đó ei,j là số cạnh của G nối hai đỉnh vi và vj . Cho s là một đỉnh của G. Ma trận Laplace thu gọn ∆′ ứng với đỉnh s của đồ thị G là ma trận cấp (n − 1) × (n − 1) có được từ ma trận Laplace ∆ của G bằng cách xóa hàng và cột tương ứng với đỉnh s. Nhận xét. (1) Mỗi cột của ma trận liên thuộc M của G đều chứa một phần tử 1, một phần tử -1 và n − 2 phần tử 0 nên tổng các phần tử của mỗi cột bằng 0. Do đó, các véc tơ dòng của ma trận M có tổng bằng véc tơ 14 Chương 1. CÁC KHÁI NIỆM CƠ BẢN không, suy ra rank(M ) < n. (2) Gọi M T là ma trận chuyển vị của ma trận M , khi đó M M T = ∆. (3) Ma trận kề A và ma trận Laplace ∆ của G không phụ thuộc vào hướng O. Ma trận A và ∆ là các ma trận đối xứng, ma trận ∆ có tổng các véc tơ dòng bằng véc tơ không. Ví dụ 1.0.3. Cho đa đồ thị vô hướng G như Hình 1.8. Hình 1.8: Đa đồ thị vô hướng G Ma trận kề A, ma trận Laplace ∆ và ma trận Laplace thu gọn ∆′ ứng với đỉnh v4 của  0 3 1   3 0 1 A=  1 1 0  2 0 1 G là:   2      0 ,∆ =     1   0 6 −3 −1 −2     6 −3 −1    −3 4 −1 0  ′   , ∆ =  −3 4 −1  .     −1 −1 3 −1  −1 −1 3 −2 0 −1 3 Định nghĩa 1.0.11. Cho đa đồ thị có hướng G = (V, E), trong đó V = {v1 , v2 , ..., vn } và E = {e1 , e2 , . . . , em }. Ma trận liên thuộc M của G 15 Chương 1. CÁC KHÁI NIỆM CƠ BẢN là ma trận cấp n × m có các phần tử được xác định như sau:     1 nếu vi là đỉnh đầu của cạnh ej    Mij = −1 nếu vi là đỉnh cuối của cạnh ej      0 nếu vi không liên thuộc với cạnh ej với 1 ≤ i ≤ n, 1 ≤ j ≤ m. Ma trận kề A của G là ma trận cấp n × n, với các phần tử Aij = ei,j , trong đó ei,j là số cạnh đi từ đỉnh vi đến đỉnh vj , 1 ≤ i, j ≤ n. Ma trận Laplace ∆ của G là ma trận cỡ n × n với các phần tử của nó được xác định bởi ∆ij =   −ei,j nếu i 6= j  deg + (v ) − e i i,i , nếu i = j Trong đó ei,j là số cạnh đi từ đỉnh vi đến đỉnh vj và deg + (vi ) là số bậc đi ra của đỉnh vi . Cho s là một đỉnh của G. Ma trận Laplace thu gọn ∆′ ứng với đỉnh s của G là ma trận cỡ n × n có được từ ma trận Laplace ∆ bằng cách xóa dòng và cột tương ứng với đỉnh s. Nhận xét. Các phần tử trong cùng một hàng của ma trận Laplace của đồ thị G có tổng bằng 0. Nếu đỉnh vi là đỉnh không có bậc đi ra của đồ thị G thì dòng thứ i của ma trận Laplace là không. Ví dụ 1.0.4. Cho đa đồ thị G như Hình 1.9. Ma trận liên thuộc M , ma trận kề A, ma trận Laplace ∆ và ma trận 16 Chương 1. CÁC KHÁI NIỆM CƠ BẢN Hình 1.9: Đa đồ thị G Laplace thu   1   −1   M =  0   0   0       ∆=      gọn ∆′ ứng với đỉnh v5 của đa đồ thị G trong Hình   0 0 1 −1 0 0 0 1  0 1   0 0 1 1 0 0 0 0 0 0       0 0 , A = 0 0 0 0 1 1 −1 −1     1 0 0 0 0 1 0 −1 1 0      −1 −1 −1 0 −1 0 0 0 0 0 3 −1 −1 0 2 0 0 −1 0 0 0  1.9 là: 1 0 1  0 0 2   0 1 1 ,  1 0 0   0 0 0   −1  3 −1 −1 0     0 0 −2     ′  0 2 0 0  .  2 −1 −1  ,∆ =     0 0 2 −1    −1 2 0    −1 0 −1 2 0 0 0 0 Định nghĩa 1.0.12. (Đồ thị đầy đủ) Đồ thị đầy đủ n đỉnh, kí hiệu Kn là đơn đồ thị mà hai đỉnh bất kì trong đồ thị luôn có cạnh nối chúng. Trong luận văn này chủ yếu xét Kn với n ≥ 3. 17  Chương 1. CÁC KHÁI NIỆM CƠ BẢN Nhận xét. Dễ thấy ma trận Laplace ∆ của Kn có:   n − 1 nếu i = j . ∆ij =  −1 nếu i 6= j Ví dụ 1.0.5. Hình sau là một đồ thị đầy đủ. Hình 1.10: Đồ thị đầy đủ 5 đỉnh K5 Ma trận Laplace của K5 là:   4   −1   ∆=  −1   −1   −1  −1 −1 −1 −1   4 −1 −1 −1    −1 4 −1 −1  .  −1 −1 4 −1    −1 −1 −1 4 18