Một số tính chất trên đồ thị ước của không của vành Z2n

Trường Đại học Vinh<br /> <br /> Tạp chí khoa học, Tập 46, Số 2A (2017), tr. 5-20<br /> <br /> MỘT SỐ TÍNH CHẤT TRÊN ĐỒ THỊ ƯỚC CỦA KHÔNG CỦA VÀNH Z2n<br /> Lê Văn An, Nguyễn Thị Hải Anh, Nguyễn Thị Thu Hằng<br /> Khoa Sư phạm Tự nhiên, Trường Đại học Hà Tĩnh<br /> Ngày nhận bài 29/5/2017, ngày nhận đăng 19/10/2017<br /> <br /> Tóm tắt: Bài báo giới thiệu khái niệm đồ thị ước của không của một vành R<br /> (không nhất thiết giao hoán) và đưa ra một số tính chất của đồ thị ước của không<br /> của vành Z2n .<br /> <br /> 1<br /> <br /> Đặt vấn đề<br /> <br /> 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<br /> và có đơn vị. Ký hiệu Zn để chỉ vành các lớp thặng dư môđulô n. Cho đại lượng s và tập<br /> hợp hữu hạn X, ký hiệu Max{s}, card(X) lần lượt là giá trị lớn nhất của s và số phần tử<br /> của tập hợp X. Cho số thực x, khi đó [x] là ký hiệu phần nguyên của x, tức<br />  nguyên<br />  là số<br /> n<br /> là số tổ<br /> lớn nhất không vượt quá x. Với hai số tự nhiên k, n trong đó k ≤ n, ký hiệu<br /> k<br /> hợp chập k của n phần tử. Cho hai số nguyên dương a, b, ký hiệu ước chung lớn nhất của<br /> chúng là gcd(a, b). Cho vành R, phần tử x ∈ R, x 6= 0 được gọi là ước của không trái (left<br /> zero divisior) của vành R nếu tồn tại phần tử y 6= 0 sao cho xy = 0. Phần tử x ∈ R, x 6= 0<br /> được gọi là ước của không phải (right zero divisior) của vành R nếu tồn tại phần tử z 6= 0<br /> sao cho zx = 0. Phần tử x là ước của không trái (hoặc phải ) của vành R đều được gọi là<br /> ước của không (zero divisior). Phần tử x ∈ R được gọi là ước của không hai phía (left and<br /> right zero divisior) của vành R, nếu nó vừa là ước của không trái và phải của R. Chẳng<br /> hạn, xét R= M2 (Z)<br /> vuông cấp 2 với các phần<br />  là vành các<br />  ma trận <br />  tử trên<br />  vành Z. Xét ma<br /> 1 1<br /> 1<br /> 1<br /> 0 0<br />  và B = <br /> , chúng ta có AB = <br /> . Do đó A là ước<br /> trận A = <br /> 2 2<br /> −1 −1<br /> 0 0<br /> của không trái của M2 (Z) và B là ước của không phải của M2 (Z). Trên vành<br /> R = M2<br /> (Z2 )<br /> 1 1<br />  là<br /> là vành các ma trận vuông cấp 2 với các phần tử trên vành Z2 , phần tử C = <br /> 1 1<br /> <br /> <br /> 0 0<br /> .<br /> ước của không hai phía của vành R vì C 2 = <br /> 0 0<br /> Dĩ nhiên, nếu R là vành giao hoán thì các khái niệm ước của không trái (hoặc phải)<br /> trùng với khái niệm ước của không hai phía. Mặt khác nếu R = Zn là vành các lớp thặng<br /> 1)<br /> <br /> Email: an.levan@htu.edu.vn (L. V. An).<br /> <br /> 5<br /> <br /> Lê Văn An, Nguyễn Thị Hải Anh, Nguyễn Thị Thu Hằng/ Một số tính chất trên đồ thị ước của...<br /> <br /> dư môđulô n với n ≥ 2, thì số ước của không bằng n − 1 − ϕ(n) trong đó ϕ(n) là giá trị<br /> phi hàm Euler của n. Lưu ý rằng, nếu n có sự phân tích tiêu chuẩn ra thừa số nguyên tố<br /> n = pα1 1 pα2 2 ...pαk k (trong đó p1 , p2 , ..., pk là k số nguyên tố khác nhau và α1 , α2 , ..., αk là k<br /> số nguyên dương) thì ϕ(n) = n(1 − p11 )(1 − p12 )(1 − p1k ). Do đó nếu m = 2n (n ≥ 2) thì<br /> ϕ(m) = 2n−1 . Định nghĩa, tính chất và ví dụ về ước của không của một số lớp vành có thể<br /> tìm thấy trong [4], [7].<br /> Năm 1999, trong [3], D. F. Anderson và P. S. Livingston đã sử dụng khái niệm đồ thị<br /> để biểu diễn các ước của không của vành giao hoán hữu hạn R. Trong bài báo đó, tập đỉnh<br /> của đồ thị chính là các ước của không của vành, các cạnh nối với nhau dựa theo quan hệ<br /> phép nhân trong vành (nghĩa là nếu xy = 0 thì đỉnh x nối được với đỉnh y); như vậy khái<br /> niệm ước của không được nghiên cứu theo quan điểm tổ hợp với đồ thị là khái niệm trọng<br /> tâm trong Hình học tổ hợp. Lưu ý rằng, trong bài báo [3], các tác giả xét đến các ước của<br /> không trên vành R với điều kiện xy = 0 nhưng x 6= y, do đó đồ thị được xây dựng sẽ không<br /> xuất hiện các khuyên (tức là các điểm tự nối với chính nó). Hiện nay, nghiên cứu đại số<br /> thông qua tổ hợp và ngược lại là những vấn đề thời sự được nhiều tác giả quan tâm (xem<br /> [1], [2], [3], [6] ...).<br /> Trong bài báo này, chúng tôi giới thiệu khái niệm đồ thị ước của không cho vành R<br /> không nhất thiết giao hoán và các phần tử xy = 0 xét đến cả trường hợp x không nhất thiết<br /> khác y. Do đó đồ thị được biểu diễn sẽ xuất hiện các khuyên ứng với trường hợp x2 = 0.<br /> Như vậy, điểm khác biệt của bài báo này với các nghiên cứu trước đó (bao gồm các kết<br /> quả của trên vành giao hoán và vành không giao hoán) chính là sự xuất hiện các khuyên<br /> trên đồ thị ước của không. Trong mục 2, chúng tôi xây dựng các ví dụ về đồ thị ước của<br /> không của vành không giao hoán. Trong mục 3, chúng tôi xây dựng các ví dụ về đồ thị ước<br /> của không của vành giao hoán nhưng tập trung vào lớp vành Z2n với n là số nguyên dương<br /> không nhỏ hơn 2. Trong mục 4, chúng tôi quan tâm đến các tính chất như số đỉnh, số cạnh,<br /> số các đồ thị con của đồ thị ước của không ứng với vành Z2n .<br /> <br /> 2<br /> <br /> Đồ thị ước của không của vành không giao hoán<br /> <br /> Một đồ thị có hướng (directed graph) là một bộ gồm 4 thành phần G = G(V, E, r, s)<br /> trong đó V là tập các đỉnh (vertices), E là tập các cạnh (edges) và r, s : E −→ V là các<br /> ánh xạ từ tập các cạnh đến tập các đỉnh. Nếu e ∈ E là một cạnh thì s(e), r(e) lần lượt là<br /> điểm đầu và điểm cuối của cạnh e.<br /> Trong trường hợp s(e) = r(e) = v thì ta nói G là đồ thị có khuyên (loop) và e được gọi<br /> là một khuyên của G. Một đường có hướng (directed path) µ = e1 e2 ...ek của đồ thị G (gọi<br /> tắt là đường (path)) là một dãy liên tiếp các cạnh e1 , e2 , ..., ek ∈ E sao cho r(ei ) = s(ei+1 ),<br /> với mọi i = 1, 2, ..., k − 1. Khi đó gọi s(µ) = s(e1 ) là điểm gốc của đường µ, r(µ) = r(ek )<br /> là điểm ngọn của µ và k = l(µ) được gọi là độ dài của µ. Trong trường hợp s(µ) = r(µ)<br /> và s(ei ) 6= s(ej ) với mọi i, j = 1, 2, ..., k − 1, i 6= j, ta nói µ là một chu trình (cycle). Ta gọi<br /> 6<br /> <br /> Trường Đại học Vinh<br /> <br /> Tạp chí khoa học, Tập 46, Số 2A (2017), tr. 5-20<br /> <br /> một khuyên là một chu trình tầm thường; một chu trình không là khuyên được gọi là một<br /> chu trình không tầm thường (non-trivial cycle). Các khái niệm này có thể tìm thấy trong<br /> các tài liệu [1], [6].<br /> Ví dụ 1. Xét đồ thị An là đường thẳng định hướng như hình vẽ.<br /> <br /> Hình 1: Đường thẳng định hướng (An )<br /> Đồ thị trong hình 1 có V = {v1 , v2 , ..., vn }, E = {e1 , e2 , ..., en−1 } và s(e1 ) = v1 , r(e1 ) =<br /> v2 , ..., s(en−1 ) = vn−1 , r(en−1 ) = vn .<br /> Ví dụ 2. Xét đồ thị như hình vẽ:<br /> <br /> Hình 2:<br /> Đồ thị trong hình 2 có tập các đỉnh {A, B, C, D, E}, tập các cạnh {a, b, c, d, e} và có thể<br /> kể tên một số đường như µ = ab, λ = edcb nhưng không có chu trình nào.<br /> Ví dụ 3. Xét đồ thị như hình vẽ:<br /> <br /> Hình 3:<br /> <br /> 7<br /> <br /> Lê Văn An, Nguyễn Thị Hải Anh, Nguyễn Thị Thu Hằng/ Một số tính chất trên đồ thị ước của...<br /> <br /> Đồ thị trong hình 3 xuất hiện chu trình ee∗ .<br /> Cho vành R không giao hoán. Đồ thị G = G(V, E, r, s), được gọi là đồ thị ước của không<br /> (zero divisior graph) của vành R nếu tập đỉnh V của G là tập tất cả các ước của không<br /> trái và ước của không phải của vành R, tập cạnh E của G thoả mãn tính chất với a ∈ E<br /> là đường có hướng nối giữa hai đỉnh x, y ∈ V (trong đó x là ước của không trái và y là ước<br /> của không phải của vành R) sao cho xy = 0 (chú ý rằng vì R không giao hoán nên yx có<br /> thể khác không), tức là s(a) = x, r(a) = y.<br /> Ví dụ 4. Xét T2 (Z2 ) là vành các ma trận tam giác trên cấp 2 của vành Z2<br /> . Vành này<br /> <br /> 1 0<br /> ,<br /> có 8 phần tử trong đó có 5 phần tử là ước của không. Đó là các ma trận v1 = <br /> 0 0<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> 0 1<br /> 1 1<br /> 0 0<br /> 0 1<br />  , v3 = <br />  , v4 = <br />  , v5 = <br />  . Ta thấy v1 v4 = 0,<br /> v2 = <br /> 0 0<br /> 0 0<br /> 0 1<br /> 0 1<br /> v2 v1 = 0, v2 v2 = 0, v2 v3 = 0, v3 v5 = 0, v4 v1 = 0, v4 v2 = 0, v4 v3 = 0, v5 v1 = 0, v5 v2 = 0,<br /> v5 v3 = 0. Do đó đồ thị ước của không của T2 (Z2 ) là:<br /> <br /> Hình 4:<br /> Đồ thị này có 1 khuyên và có các chu trình không tầm thường chẳng hạn chu trình nối<br /> lần lượt các đỉnh v2 v3 v5 . Đây là một chu trình có độ dài bằng 3. Có thể thấy còn có chu<br /> trình nối hai đỉnh v1 v4 với độ dài 2.<br /> 8<br /> <br /> Trường Đại học Vinh<br /> <br /> Tạp chí khoa học, Tập 46, Số 2A (2017), tr. 5-20<br /> <br /> Ví dụ 5. Xét M2 (Z2 ) là vành các ma trận vuông cấp 2 của vành Z2 .<br /> Vành này<br />  có 16<br /> 1 0<br /> ,<br /> phần tử trong đó có 9 phần tử là ước của không. Đó là các ma trận v1 = <br /> 0 0<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> 0 1<br /> 0 0<br /> 0 0<br /> 1 1<br /> 0 0<br />  , v3 = <br />  , v4 = <br />  , v5 = <br />  , v6 = <br /> ,<br /> v2 = <br /> 0 0<br /> 1 0<br /> 0 1<br /> 0 0<br /> 1 1<br /> <br /> <br /> <br /> <br /> <br /> <br /> 1 0<br /> 0 1<br /> 1 1<br />  , v8 = <br />  , v9 = <br />  . Ta thấy v1 v3 = 0, v1 v4 = 0, v1 v6 =<br /> v7 = <br /> 1 0<br /> 0 1<br /> 1 1<br /> 0,<br /> v2 v1 = 0, v2 v2 = 0, v2 v5 = 0, v3 v3 = 0, v3 v4 = 0, v3 v6 = 0, v4 v1 = 0, v4 v2 = 0, v4 v5 = 0,<br /> v5 v7 = 0, v5 v8 = 0, v5 v9 = 0, v6 v7 = 0, v6 v8 = 0, v6 v9 = 0, v7 v3 = 0, v7 v4 = 0, v7 v6 = 0,<br /> v8 v1 = 0, v8 v2 = 0, v8 v5 = 0, v9 v7 = 0, v9 v8 = 0, v9 v9 = 0. Do đó đồ thị ước của không<br /> của M2 (Z2 ) là:<br /> <br /> Hình 5:<br /> <br /> Đồ thị này có 3 khuyên và có các chu trình không tầm thường chẳng hạn chu trình nối<br /> lần lượt các đỉnh v1 v4 v2 . Đây là một chu trình có độ dài bằng 3.<br /> 9<br /> <br />