Nội dung

Trường Đại học Vinh Tạp chí khoa học, Tập 48, Số 4A (2019), tr. 5-22 ĐỒ THỊ LŨY LINH TRÊN VÀNH Zn Lê Văn An (1) , Nguyễn Thị Hải Anh (1) , Nguyễn Thị Thanh Huyền (2) và Latthvone Douangsanga (3) 1 Khoa Sư phạm - Trường Đại học Hà Tĩnh 2 Lớp cao học khóa 26, Đại số và Lý thuyết số - Trường Đại học Vinh 3 Sinh viên K8 Sư phạm Toán - Trường Đại học Hà Tĩnh Ngày nhận bài 18/8/2019, ngày nhận đăng 22/10/2019 Tóm tắt: Trong [4], Basnet-Sharma-Dutta đã giới thiệu và nghiên cứu khái niệm đồ thị lũy linh của một vành giao hoán hữu hạn. Trong bài báo này, chúng tôi tính được số thành phần liên thông của đồ thị lũy linh cho vành Zn . Áp dụng kết quả này, chúng tôi đặc trưng được tính liên thông và tính đầy đủ của đồ thị lũy linh cho vành Zn . Từ khóa: Phần tử lũy linh; đồ thị; đồ thị lũy linh; đồ thị đầy đủ; đồ thị liên thông; thành phần liên thông. 1 Đặt vấn đề Trong toàn bộ bài báo này, chúng tôi quan tâm xem xét các vành R hữu hạn, kết hợp và có đơn vị khác không. Ký hiệu Zn để chỉ vành các lớp thặng dư môđulô n. Cho tập hợp hữu hạn  k, n, ký  ký hiệu card(X) là số phần tử của tập hợp X. Cho hai số tự  nhiên  X, n n = 0. Cho là số tổ hợp chập k của n phần tử với lưu ý nếu n < k thì hiệu k k hai số nguyên dương a, b, ký hiệu ước chung lớn nhất của chúng là gcd(a, b). Lý thuyết đồ thị là đối tượng nghiên cứu quan trọng của Hình học tổ hợp và có nhiều ứng dụng trong thực tế. Hiện nay, Lý thuyết đồ thị còn tác động vào nhiều chuyên ngành khác nhau của Toán học. Một trong những lĩnh vực Toán học mà Lý thuyết đồ thị có nhiều tác động hiện nay là Đại số. Nghiên cứu các cấu trúc đại số thông qua Lý thuyết đồ thị và ngược lại là một trong những vấn đề thời sự đang được nhiều tác giả quan tâm (xem [1], [2], [9]). Trong [4], các tác giả đã sử dụng khái niệm đồ thị để biễu diễn các phần tử lũy linh của một vành giao hoán hữu hạn có đơn vị 1 6= 0. Trong bài báo đó, tập hợp các đỉnh của đồ thị chính là tập hợp các phần tử không lũy linh của vành, một cạnh nối hai đỉnh phân biệt x, y chỉ nếu x + y là một phần tử lũy linh của vành R. Đồ thị G vì vậy sẽ không có khuyên và nếu hai phần tử không lũy linh phân biệt bất kỳ có tổng là một phần tử lũy linh sẽ dẫn đến đồ thị G là đầy đủ. Một câu hỏi được đặt ra là: Câu hỏi 1: "Vành giao hoán R có đặc trưng gì để đồ thị G đầy đủ và ngược lại?" Một số câu hỏi thú vị khác cũng được đặt ra là: Câu hỏi 2: Vành R có đặc trưng gì để đồ thị G liên thông? Câu hỏi 3: Tính số thành phần liên thông của đồ thị lũy linh? 1) Email: an.levan@htu.edu.vn (L. V. An) 5 L. V. An, N. T. H. Anh, N. T. T. Huyền, L. Douangsanga/ Đồ thị lũy linh trên vành Zn Việc giải quyết các câu hỏi trên cho lớp vành giao hoán hữu hạn có đơn vị 1 6= 0 sẽ là vấn đề thú vị nhưng không đơn giản. Trong bài báo này, chúng tôi chỉ xem xét các câu hỏi trên cho một trường hợp đặc biệt. Cụ thể chúng tôi chỉ nghiên cứu một số khía cạnh của đồ thị lũy linh cho vành các lớp thặng dư môđulô n. Định lý 11 của bài báo sẽ trả lời Câu hỏi 1, cho vành các lớp thặng dư môđulô n. Chúng ta biết rằng trên vành giao hoán tổng hai phần tử lũy linh phân biệt x, y có bậc lũy linh lần lượt là m và n sẽ là phần tử lũy linh vì m+n X  m+n  m+n (x + y) = xk y m+n−k = 0, k k=0 xk y m+n−k (do = 0 với k ≥ m và = 0 với k < m). Tuy nhiên tổng hai phần tử không lũy linh phân biệt có thể không là phần tử lũy linh. Vì thế, Định lý 11 cũng sẽ trả lời một phần câu hỏi: "Khi nào tổng hai phần tử không lũy linh phân biệt là phần tử lũy linh?". Định lý 8 và Định lý 10 của bài báo sẽ trả lời Câu hỏi 2 và Câu hỏi 3 cho lớp vành các lớp thặng dư môđulô n. Kỹ thuật cơ bản để giải quyết các vấn đề đặt ra trong bài báo của chúng tôi là các tính toán tổ hợp trên tập hợp hữu hạn cũng như các ý tưởng số học về các số nguyên tố. Một kết quả chúng tôi thường xuyên sử dụng là Định lý cơ bản của số học nói rằng một số tự nhiên lớn hơn 1 có thể biễu diễn một cách duy nhất thành tích các thừa số nguyên tố cùng với số mũ của nó. Tức là, nếu n ≥ 2, thì nó được biễu diễn duy nhất dưới dạng n = pα1 1 pα2 2 ...pαk k trong đó p1 , p2 , ..., pk là các số nguyên tố đôi một phân biệt và α1 , α2 , ..., αk là các số nguyên dương (với k là số nguyên dương). 2 Các khái niệm cơ bản Cho vành R, phần tử x ∈ R được gọi là lũy linh (nilpotent) nếu tồn tại số nguyên dương k sao cho xk = 0, số nguyên dương k nhỏ nhất có tính chất đó gọi là bậc lũy linh của phần tử x. Đối với một vành R bất kỳ, ký hiệu N il(R) là tập tất cả các phần tử lũy linh của nó. Một kết quả quan trọng và đẹp trong Đại số tuyến tính khẳng định rằng nếu A là phần tử trong vành ma trận vuông cấp n trên trường K thì bậc lũy linh của A không vượt quá n. Các khái niệm và tính chất của phần tử lũy linh có thể tìm thấy trong các tài liệu [3], [10]. Các phần tử lũy linh trong vành là đối tượng nghiên cứu của Lý thuyết vành và đang được nhiều tác giả quan tâm. Giả thuyết Kothe liên quan đến các phần tử lũy linh và các iđêan lũy linh được đề xuất từ năm 1930 đến nay vẫn chưa được giải quyết và đang nhận được sự quan tâm của nhiều nhà đại số trên thế giới (xem [5], [7], [8]). Một đồ thị vô hướng (graph) là một bộ gồm 2 thành phần G = G(V, E) trong đó V là tập các đỉnh và E là tập các cạnh, ở đây cạnh AB ∈ E nghĩa là cạnh nối điểm A với điểm B (hay điểm B nối với điểm A). Trong trường hợp cạnh nối điểm A với chính nó được gọi là khuyên (loop). Một đồ thị G không có khuyên, trong đó hai đỉnh được nối với nhau nhiều nhất là một cạnh được gọi là đồ thị đơn (simple graph). Một đồ thị đơn G được gọi là đầy đủ (complete graph) nếu cặp đỉnh bất kỳ của G được nối với nhau bằng đúng 1 cạnh. Xét một đỉnh v ∈ V của đồ thị G = G(V, E) ta nói bậc của v bằng k và ký hiệu k = deg(v) nếu v là đầu mút của đúng k cạnh (tính cả khuyên). 6 Trường Đại học Vinh Tạp chí khoa học, Tập 48, Số 4A (2019), tr. 5-22 Cho G = G(V, E) là một đồ thị, đường đi (path) từ đỉnh A ∈ V đến đỉnh B ∈ V trong đồ thị là dãy các đỉnh v1 v2 ...vk sao cho v1 = A, vk = B và đỉnh vi được nối với đỉnh vi+1 (i = 1, 2, ..., k − 1). Đường đi đơn (simple path) là đường đi mà các đỉnh của nó đôi một phân biệt trừ điểm đầu và điểm cuối không nhất thiết phân biệt. Chu trình (cycle) là đường đi khép kín tức là điểm đầu và điểm cuối trùng nhau. Chu trình và là đường đi đơn được gọi là chu trình đơn (simple cycle). Đồ thị G không có chu trình được gọi là acyclic. Lưu ý rằng một cạnh cũng là đường đi. Tương tự một khuyên cũng là một chu trình và được gọi là chu trình tầm thường (trivial cycle). Một chu trình không phải là khuyên được gọi là chu trình không tầm thường (nontrivial cycle). Đồ thị G được gọi là liên thông (connected) nếu hai đỉnh bất kỳ x, y của G tồn tại đường đi trong G nối x với y. Cho G = G(V, E) là một đồ thị, đồ thị G0 = G0 (V 0 , E 0 ) trong đó V 0 ⊂ V và E 0 ⊂ E được gọi là đồ thị con (subgraph) của đồ thị G. Đồ thị con liên thông tối đại của G (tức là đồ thị con đó là đồ thị liên thông và không thể nhận thêm bất kì một đỉnh nào mà vẫn duy trì tính chất liên thông) được gọi là một thành phần liên thông (connected component) của G. Nếu G là đồ thị liên thông thì nó có đúng một thành phần liên thông (chính là toàn bộ đồ thị). Nếu G là đồ thị không liên thông sẽ được chia nhỏ thành các đồ thị liên thông mà mỗi đồ thị con là một thành phần liên thông của G. Các khái niệm và tính chất của Lý thuyết đồ thị có thể tìm thấy trong các tài liệu [6], [9]. Hình 1: Đồ thị liên thông và có khuyên 7 L. V. An, N. T. H. Anh, N. T. T. Huyền, L. Douangsanga/ Đồ thị lũy linh trên vành Zn Hình 2: Các ví dụ về đồ thị đầy đủ với số đỉnh lần lượt là 2, 3, 4. Nếu gộp ba đồ thị lại chúng ta có một đồ thị gồm 3 thành phần liên thông 3 Đồ thị lũy linh Trong mục này chúng tôi giới thiệu định nghĩa của đồ thị lũy linh cho một vành kết hợp bất kỳ. Lưu ý rằng, khái niệm đồ thị lũy linh mà Basnet-Sharma-Dutta giới thiệu trong [4], chỉ xét R là một vành giao hoán hữu hạn. Trong bài báo này, chúng tôi xét vành R có tính chất kết hợp và có đơn vị 1 6= 0 và vì thế tổng quát hơn trong [4]. Sau đó chúng tôi chỉ ra một số ví dụ về đồ thị lũy linh cho một số lớp vành cụ thể. Định nghĩa. Cho R là một vành kết hợp có đơn vị. Đồ thị G = G(V, E) được gọi là đồ thị lũy linh (nilpotent graph) của vành R nếu tập các đỉnh V của G là tập tất cả các phần tử thuộc R\N il(R) và tập các cạnh E của G là tập tất cả các đường nối giữa hai phần tử x và y phân biệt thuộc V sao cho x + y ∈ N il(R). Tiếp theo chúng tôi giới thiệu một số ví dụ cụ thể về đồ thị lũy linh cho một số lớp vành. Trong trường hợp vành R không giao hoán chúng tôi quan tâm đến lớp vành ma trận vuông cấp 2 (Ví dụ 1 và Ví dụ 2). Trong trường hợp vành R giao hoán chúng tôi quan tâm lớp vành các lớp thặng dư môđulô n. Ví dụ 1. Xét vành R = M2 (Z2 ) là vành các ma trận vuông cấp 2 của vành Z2 . Khi đó chúng ta có  0 0 N il(R) = N il(M2 (Z2 )) = {   ; 0 0    0 1 0 0 ; 0 0 Vì thế tập đỉnh của đồ thị G là: V = {V1     1 0  1 1 0 1  1 1  0 0  ; V3  0 1  }. ;  ; V2  1 1 8 0 1  ; 0 1 Trường Đại học Vinh  0 0  Tạp chí khoa học, Tập 48, Số 4A (2019), tr. 5-22  1 1   1 1   1 0   1 0  V4   ; V5   ; V6   ; V7   ; V8  ; 1 1 0 0 1 0 1 0 0 0         1 0 1 1 0 1 1 0  ; V10   ; V11   ; V12  }. V9  0 1 0 1 1 0 1 1 Do đó đồ thị G là: Hình 3: Đồ thị lũy linh của vành R = M2 (Z2 ). Ví dụ 2. Xét vành R = T2 (Z2 ) là vành các ma trận tam giác trên cấp 2 của vành Z2 . Khi đó chúng ta có     0 0 0 1 ; }. N il(R) = { 0 0 0 0       1 0 1 1 0 0  ; V2   ; V3  ; Vì thế tập đỉnh của đồ thị G là: V = {V1  0 0 0 0 0 1       0 1 1 0 1 1  ; V5   ; V6  }. V4 =  0 1 0 1 0 1 9 L. V. An, N. T. H. Anh, N. T. T. Huyền, L. Douangsanga/ Đồ thị lũy linh trên vành Zn Do đó đồ thị G là: Hình 4: Đồ thị lũy linh của vành R = T2 (Z2 ). Ví dụ 3. Xét vành R = Z12 , suy ra N il(R) = {0, 6}. Do đó chúng ta có V = {1, 2, 3, 4, 5, 7, 8, 9, 10, 11}. Đồ thị G là: Hình 5: Đồ thị lũy linh của vành R = Z12 . Vấn đề chủ yếu mà bài báo này quan tâm là tính số thành phần liên thông của đồ thị lũy linh cho vành các lớp thặng dư môđulô n. Từ đó chỉ ra điều kiện cần và đủ của số nguyên dương n để đồ thị lũy linh của vành Zn là đồ thị liên thông và đồ thị đầy đủ. Các kết quả về những vấn đề này là nội dung của phần tiếp theo sau đây. 10 Trường Đại học Vinh 4 Tạp chí khoa học, Tập 48, Số 4A (2019), tr. 5-22 Tính liên thông và đầy đủ của đồ thị lũy linh cho vành Zn Trong mục này chúng tôi xét đồ thị lũy linh của vành các lớp thặng dư môđulô n. Để bắt đầu cho các kết quả của mục này, chúng tôi đưa ra một số nhận xét sau đây:  n Nhận xét 1. Nếu G = G(V, E) là đồ thị đầy đủ và card(V ) = n thì card(E) = . 2 Nhận xét 2. Nếu G = G(V, E) là đồ thị đơn thì P deg(v) card(E) = v∈V . 2 Nhận xét 3. Cho n là số nguyên dương lớn hơn 1, khi đó n có sự phân tích tiêu chuẩn thành tích các thừa số nguyên tố là n = pα1 1 pα2 2 ...pαk k với p1 , p2 , ..., pk là các số nguyên tố đôi một phân biệt và α1 , α2 , ...αk là các số nguyên dương (và k cũng là số nguyên dương). Xét Zn là vành các lớp thặng dư môđulô n, khi đó: N il(R) = {ip1 p2 ...pk }, với i = 0, 1, ...., pα1 1 −1 pα2 2 −1 ...pkαk −1 − 1. Kết quả đầu tiên chúng tôi đưa ra công thức tính số đỉnh của đồ thị lũy linh của vành các lớp thặng dư môđulô n với n > 1 là số nguyên dương bất kỳ. Mệnh đề 1. Cho số nguyên dương n lớn hơn 1 có sự biểu diễn dưới dạng n = pα1 1 pα2 2 ...pαk k trong đó p1 , p2 , ..., pk là các số nguyên tố phân biệt và α1 , α2 , ..., αk là các số nguyên dương (với k là số nguyên dương). Gọi G = G(V, E) là đồ thị lũy linh của vành R = Zn . Khi đó: card(V ) = (pα1 1 −1 pα2 2 −1 ...pαk k −1 )(p1 p2 ...pk − 1). Chứng minh. Chúng ta có: N il(R) = {ip1 p2 ...pk }, với i = 0, 1, ...., pα1 1 −1 pα2 2 −1 ...pkαk −1 − 1, suy ra, card(N il(R)) = pα1 1 −1 pα2 2 −1 ...pαk k −1 . Do đó: card(V ) = n − card(N il(R)) = (pα1 1 −1 pα2 2 −1 ...pαk k −1 )(p1 p2 ...pk − 1).  Một câu hỏi thú vị được đặt ra nếu n = 2t với t là số nguyên dương và G = G(V, E) là đồ thị lũy linh của vành R = Zn , khi đó G có đặc điểm gì? Từ việc quan sát các ví dụ cụ thể chúng ta có kết quả sau: Mệnh đề 2. Cho vành R = Z2t với t là số nguyên dương và G = G(V, E) là đồ thị lũy linh của vành R. Khi đó G là đồ thị đầy đủ. Chứng minh. Giả sử n = 2t , chúng ta sẽ chứng minh G là đồ thị đầy đủ. Trong trường hợp t = 1 vành Z2 = {0, 1}, suy ra V = {1} và không có cạnh nào. Đồ thị này là đồ thị đầy đủ. 11 L. V. An, N. T. H. Anh, N. T. T. Huyền, L. Douangsanga/ Đồ thị lũy linh trên vành Zn Với t = 2, đồ thị này G gồm hai đỉnh và một cạnh nên cũng là đồ thị đầy đủ. Cuối cùng xét t ≥ 3, chúng ta có: N il(Z2t ) = {2i | i = 0, 1, ..., 2t−1 − 1}. Suy ra V = {1, 3, ..., 2t − 1}. Xét hai đỉnh bất kỳ phân biệt x và y của V . Vì các số nguyên dương x, y là số lẻ nên x + y là số chẵn. Do đó với x + y = z, chúng ta có z là số nguyên dương chẵn, tức là z ∈ N il(Z2t ). Điều này suy ra đỉnh x được nối với đỉnh y. Vậy G là đồ thị đầy đủ.  Trong trường hợp này, số cạnh của đồ thị lũy linh là: Hệ quả 3. Cho vành R = Z2t với t là số nguyên dương và G = G(V, E) là đồ thị lũy linh của vành R. Khi đó:  t−1  2 . card(E) = 2 Chứng minh. Theo Mệnh đề 1, card(V ) = 2t−1 . Mặt khác, theo Mệnh đề 2, G là đồ thị đầy đủ nên chúng ta có:  t−1  2 .  card(E) = 2 Từ những quan sát trên đồ thị lũy linh của các vành Z3t với t = 1, 2, 3 chúng tôi thấy G là đồ thị liên thông. Tổng quát hơn, chúng ta có: Mệnh đề 4. Cho vành R = Z3t với t là số nguyên dương và G = G(V, E) là đồ thị lũy linh của vành R. Khi đó G là đồ thị liên thông. Chứng minh. Giả sử n = 3t , chúng ta sẽ chứng minh G là đồ thị liên thông. Trong trường hợp t = 1 vành Z3 = {0, 1, 2}, suy ra V = {1, 2} và có đúng một cạnh nối 1 với 2. Do đó đồ thị này là đồ thị liên thông. Với t ≥ 2, chúng ta có: N il(Z3t ) = {3i | i = 0, 1, ..., 3t−1 − 1}. Do đó V = {3i + 1, 3i + 2 | i = 0, 1, ..., 3i−1 −1}. Nhận xét rằng với mọi i, j ∈ {1, 2, ..., 3i−1 − 1} chúng ta có 3i + 1 + 3j + 2 ∈ N il(3t ), suy ra đỉnh 3i + 1 luôn được nối với đỉnh 3j + 2. Từ đó chúng ta có chu trình e = 1 2 4 ... 3i − 1 3i + 1 3i + 2 ... 3t − 4 3t − 2 3t − 1 1 đi qua tất các đỉnh của G. Do đó với hai đỉnh bất kỳ x, y ∈ V và x 6= y luôn tồn tại đường đi từ x đến y là một phần của chu trình e.  Hệ quả sau là cách tính số cạnh của đồ thị lũy linh của vành R = Z3t . Hệ quả 5. Cho vành R = Z3t với t là số nguyên dương và G = G(V, E) là đồ thị lũy linh của vành R. Khi đó card(E) = 32t−2 . 12 Trường Đại học Vinh Tạp chí khoa học, Tập 48, Số 4A (2019), tr. 5-22 Chứng minh. Công thức đúng với t = 1 (khi đó card(E) = 1). Với t ≥ 2, xét các tập hợp V1 = {i.3 + 1 : i = 0, 1, ..., 3t−1 − 1} và V2 = {i.3 + 2 : i = 0, 1, ..., 3t−1 − 1}, suy ra V = V1 ∪ V2 và V1 ∩ V2 = ∅. Xét hai đỉnh i.3 + 1 và i0 .3 + 1 của V1 chúng ta có: i.3 + 1 + i0 .3 + 1 6∈ N il(Z3t ), suy ra các đỉnh trong V1 không được nối với nhau. Hoàn toàn tương tự các đỉnh trong V2 cũng không được nối với nhau. Mặt khác xét hai đỉnh i.3 + 1 ∈ V1 và i0 .3 + 2 ∈ V2 chúng ta có: i.3 + 1 + i0 .3 + 2 ∈ N il(Z3t ), suy ra một đỉnh bất kỳ trong V1 sẽ được nối với tất cả các đỉnh trong V2 và ngược lại một đỉnh bất kỳ trong V2 sẽ được nối với tất cả các đỉnh trong V1 . Do đó: card(E) = card(V1 ).card(V2 ) = 3t−1 .3t−1 = 32t−2 .  Một câu hỏi đặt ra đồ thị lũy linh G có bao nhiêu thành phần liên thông? Cụ thể hơn, nếu G là đồ thị lũy linh của vành R = Zn thì chỉ số n liên hệ như thế nào với số thành phần liên thông của G. Bổ đề dưới đây sẽ đưa ra công thức liên hệ cho một trường hợp đặc biệt của số nguyên dương n (với n không có ước chính phương). Bổ đề 6. Cho số nguyên dương n lớn hơn 1 có sự biểu diễn dưới dạng n = p1 p2 ...pk trong đó p1 , p2 , ..., pk là các số nguyên tố phân biệt sao cho p1 < p2 < ... < pk (với k là số nguyên dương). Gọi G = G(V, E) là đồ thị lũy linh của vành R = Zn . Gọi C là số thành phần liên thông của G, khi đó:   nếu n = 2; 1 C = p2 p3 ...pk nếu p1 = 2 và k ≥ 2;   n−1 nếu p1 > 2. 2 Chứng minh. Chúng ta có N il(Zn ) = 0, suy ra, V = {1, 2, ..., n − 1}. Tính toán là tầm thường với n = 2. Chúng ta kiểm tra với n > 2. Nhận xét rằng với mọi x ∈ V tồn tại duy nhất phần tử y = n − x ∈ V sao cho x + y = 0. Do đó các đỉnh của G có bậc 0 hoặc 1 (đỉnh x có bậc 0 nếu x = n − x). Nếu n = 2p2 p3 ...pk (với k ≥ 2 vì n > 2), các thành phần liên thông của G là {1, 2p2 ...pk − 1}, {2, 2p2 ...pk − 2}, ... , {p2 p3 ...pk − 1, p2 p3 ...pk + 1} và {p2 p3 ...pk }. Do đó số thành phần liên thông của G là: C = p2 p3 ...pk . Nếu n = p1 p2 ...pk với p1 > 2 thì n−1 là số chẵn và x 6= n − x. Từ đó tất cả các đỉnh của G đều có bậc 1 và số thành phần liên thông của G là C = n−1 2 . Hệ quả sau đưa ra công thức tính số cạnh của đồ thị G trong trường hợp n không có ước chính phương. 13 L. V. An, N. T. H. Anh, N. T. T. Huyền, L. Douangsanga/ Đồ thị lũy linh trên vành Zn Hệ quả 7. Cho số nguyên dương n lớn hơn 1 có sự biểu diễn dưới dạng n = p1 p2 ...pk trong đó p1 , p2 , ..., pk là các số nguyên tố phân biệt sao cho p1 < p2 < ... < pk (với k là số nguyên dương). Gọi G = G(V, E) là đồ thị lũy linh của vành R = Zn . Khi đó   nếu n = 2; 0 card(E) = p2 p3 ...pk − 1 nếu p1 = 2 và k ≥ 2;   n−1 nếu p1 > 2. 2 Chứng minh. Tính toán là tầm thường với n = 2. Nếu n = 2p2 p3 ...pk với k ≥ 2, các thành phần liên thông của G là: G1 = {1, 2p2 ...pk − 1}, G2 = {2, 2p2 ...pk − 2}, ... , Gp2 p3 ...pk −1 = {p2 p3 ...pk − 1, p2 p3 ...pk + 1} và Gp2 p3 ...pk = {p2 p3 ...pk }. Trong đó các thành phần liên thông của G1 , ... , Gp2 p3 ...pk −1 có đúng một cạnh và thành liên thông Gp2 p3 ...pk chỉ có một đỉnh và không có cạnh nào. Từ đó: card(E) = p2 p3 ...pk − 1. Nếu n = p1 p2 ...pk với p1 > 2 thì n − 1 là số chẵn và tất cả các đỉnh của G đều có bậc 1 và suy ra, n−1 .  card(E) = 2 Định lý sau đây đưa ra công thức tính số thành phần liên thông của đồ thị lũy linh G của vành R = Zn với n > 1 là số nguyên dương bất kỳ. Định lý 8. Cho số nguyên dương n lớn hơn 1 có sự biểu diễn dưới dạng n = pα1 1 pα2 2 ...pαk k trong đó p1 , p2 , ..., pk là các số nguyên tố phân biệt sao cho p1 < p2 < ... < pk và α1 , α2 , ..., αk là các số nguyên dương (với k là số nguyên dương). Gọi G = G(V, E) là đồ thị lũy linh của vành R = Zn . Gọi C là số thành phần liên thông của G, khi đó:   nếu p1 = 2 và k = 1; 1 C = p2 p3 ...pk nếu p1 = 2 và k ≥ 2;   p1 p2 ...pk −1 nếu p1 > 2. 2 Hơn nữa, với p1 = 2 và tồn tại ít nhất αj > 1 với j ∈ {1, ..., k} nào đó luôn có đúng một thành phần liên thông là đồ thị con đầy đủ không tầm thường (tức là số đỉnh của đồ thị đầy đủ này lớn hơn 1). Chứng minh. Bước 1. Nếu α1 = α2 = ... = αk = 1, theo Bổ đề 6, chúng ta có:   nếu p1 = 2 và k = 1; 1 C = p2 ...pk nếu p1 = 2 và k ≥ 2;   p1 p2 ...pk −1 nếu p1 > 2. 2 14