Trường Đại học Vinh Tạp chí khoa học, Tập 46, Số 2A (2017), tr. 5-20
MỘT SỐ TÍNH CHẤT TRÊN ĐỒ THỊ ƯỚC CỦA KHÔNG CỦA VÀNH Z2n
Lê Văn An, Nguyễn Thị Hải Anh, Nguyễn Thị Thu Hằng
Khoa Sư phạm Tự nhiên, Trường Đại học Hà Tĩnh
Ngày nhận bài 29/5/2017, ngày nhận đăng 19/10/2017
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
(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
của vành Z2n.
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 Rhữu hạn, kết hợp
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 svà tập
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 svà số phần tử
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 là số nguyên
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 n
klà số tổ
hợp chập kcủa nphần tử. Cho 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). Cho vành R, phần tử x∈R, x 6= 0 được gọi là ước của không trái (left
zero divisior) của vành Rnếu tồn tại phần tử y6= 0 sao cho xy = 0. Phần tử x∈R, x 6= 0
được gọi là ước của không phải (right zero divisior) của vành Rnếu tồn tại phần tử z6= 0
sao cho zx = 0. Phần tử xlà ước của không trái (hoặc phải ) của vành Rđều được gọi là
ướ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
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
hạn, xét R=M2(Z)là vành các ma trận vuông cấp 2với các phần tử trên vành Z. Xét ma
trận A=
1 1
2 2
và B=
1 1
−1−1
, chúng ta có AB =
0 0
0 0
. Do đó Alà ước
của không trái của M2(Z)và Blà ước của không phải của M2(Z). Trên vành R=M2(Z2)
là vành các ma trận vuông cấp 2với các phần tử trên vành Z2, phần tử C=
1 1
1 1
là
ước của không hai phía của vành Rvì C2=
0 0
0 0
.
Dĩ nhiên, nếu Rlà vành giao hoán thì các khái niệm ước của không trái (hoặc phải)
trùng với khái niệm ước của không hai phía. Mặt khác nếu R=Znlà vành các lớp thặng
1)Email: an.levan@htu.edu.vn (L. V. An).
5
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...
dư môđulô nvới n≥2, thì số ước của không bằng n−1−ϕ(n)trong đó ϕ(n)là giá trị
phi hàm Euler của n. Lưu ý rằng, nếu ncó sự phân tích tiêu chuẩn ra thừa số nguyên tố
n=pα1
1pα2
2...pαk
k(trong đó p1, p2, ..., pklà ksố nguyên tố khác nhau và α1, α2, ..., αklà k
số nguyên dương) thì ϕ(n) = n(1 −1
p1)(1 −1
p2)(1 −1
pk). Do đó nếu m= 2n(n≥2) thì
ϕ(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ể
tìm thấy trong [4], [7].
Năm 1999, trong [3], D. F. Anderson và P. S. Livingston đã sử dụng khái niệm đồ thị
để 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
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ệ
phép nhân trong vành (nghĩa là nếu xy = 0 thì đỉnh xnối được với đỉnh y); như vậy khái
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
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
không trên vành Rvới điều kiện xy = 0 nhưng x6=y, do đó đồ thị được xây dựng sẽ không
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ố
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
[1], [2], [3], [6] ...).
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
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 xkhông nhất thiết
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.
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
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
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
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
của không của vành giao hoán nhưng tập trung vào lớp vành Z2nvới nlà số nguyên dương
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,
số các đồ thị con của đồ thị ước của không ứng với vành Z2n.
2 Đồ thị ước của không của vành không giao hoán
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)
trong đó Vlà tập các đỉnh (vertices),Elà tập các cạnh (edges) và r, s :E−→ Vlà các
ánh xạ từ tập các cạnh đến tập các đỉnh. Nếu e∈Elà một cạnh thì s(e), r(e)lần lượt là
điểm đầu và điểm cuối của cạnh e.
Trong trường hợp s(e) = r(e) = vthì ta nói Glà đồ thị có khuyên (loop) và eđược gọi
là một khuyên của G. Một đường có hướng (directed path) µ=e1e2...ekcủa đồ thị G(gọi
tắt là đường (path)) là một dãy liên tiếp các cạnh e1, e2, ..., ek∈Esao cho r(ei) = s(ei+1),
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)
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(µ)
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
6
Trường Đại học Vinh Tạp chí khoa học, Tập 46, Số 2A (2017), tr. 5-20
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
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
các tài liệu [1], [6].
Ví dụ 1. Xét đồ thị Anlà đường thẳng định hướng như hình vẽ.
Hình 1: Đường thẳng định hướng (An)
Đồ thị trong hình 1có V={v1, v2, ..., vn},E={e1, e2, ..., en−1}và s(e1) = v1, r(e1) =
v2, ..., s(en−1) = vn−1, r(en−1) = vn.
Ví dụ 2. Xét đồ thị như hình vẽ:
Hình 2:
Đồ thị trong hình 2có tập các đỉnh {A, B, C, D, E}, tập các cạnh {a, b, c, d, e}và có thể
kể tên một số đường như µ=ab, λ =edcb nhưng không có chu trình nào.
Ví dụ 3. Xét đồ thị như hình vẽ:
Hình 3:
7
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...
Đồ thị trong hình 3xuất hiện chu trình ee∗.
Cho vành Rkhông giao hoán. Đồ thị G=G(V, E, r, s), được gọi là đồ thị ước của không
(zero divisior graph) của vành Rnếu tập đỉnh Vcủa Glà tập tất cả các ước của không
trái và ước của không phải của vành R, tập cạnh Ecủa Gthoả mãn tính chất với a∈E
là đường có hướng nối giữa hai đỉnh x, y ∈V(trong đó xlà ước của không trái và ylà ước
của không phải của vành R) sao cho xy = 0 (chú ý rằng vì Rkhông giao hoán nên yx có
thể khác không), tức là s(a) = x, r(a) = y.
Ví dụ 4. Xét T2(Z2)là vành các ma trận tam giác trên cấp 2của vành Z2. Vành này
có 8phần tử trong đó có 5phần tử là ước của không. Đó là các ma trận v1=
1 0
0 0
,
v2=
0 1
0 0
, v3=
1 1
0 0
, v4=
0 0
0 1
, v5=
0 1
0 1
.Ta thấy v1v4= 0,
v2v1= 0, v2v2= 0, v2v3= 0, v3v5= 0, v4v1= 0, v4v2= 0, v4v3= 0, v5v1= 0, v5v2= 0,
v5v3= 0. Do đó đồ thị ước của không của T2(Z2)là:
Hình 4:
Đồ thị này có 1khuyên và có các chu trình không tầm thường chẳng hạn chu trình nối
lần lượt các đỉnh v2v3v5. Đây là một chu trình có độ dài bằng 3. Có thể thấy còn có chu
trình nối hai đỉnh v1v4với độ dài 2.
8
Trường Đại học Vinh Tạp chí khoa học, Tập 46, Số 2A (2017), tr. 5-20
Ví dụ 5. Xét M2(Z2)là vành các ma trận vuông cấp 2của vành Z2. Vành này có 16
phần tử trong đó có 9phần tử là ước của không. Đó là các ma trận v1=
1 0
0 0
,
v2=
0 1
0 0
, v3=
0 0
1 0
, v4=
0 0
0 1
, v5=
1 1
0 0
, v6=
0 0
1 1
,
v7=
1 0
1 0
, v8=
0 1
0 1
, v9=
1 1
1 1
.Ta thấy v1v3= 0, v1v4= 0, v1v6=
0,
v2v1= 0, v2v2= 0, v2v5= 0, v3v3= 0, v3v4= 0, v3v6= 0, v4v1= 0, v4v2= 0, v4v5= 0,
v5v7= 0, v5v8= 0, v5v9= 0, v6v7= 0, v6v8= 0, v6v9= 0, v7v3= 0, v7v4= 0, v7v6= 0,
v8v1= 0, v8v2= 0, v8v5= 0, v9v7= 0, v9v8= 0, v9v9= 0. Do đó đồ thị ước của không
của M2(Z2)là:
Hình 5:
Đồ thị này có 3khuyên và có các chu trình không tầm thường chẳng hạn chu trình nối
lần lượt các đỉnh v1v4v2. Đây là một chu trình có độ dài bằng 3.
9