Có bao nhiêu quan hệ có tính phản xạ trên một tập hợp có n phần tử
- 1 Khái niệm
- 1.1 Định nghĩa
- 1.2 Ví dụ
- 1.3 Ma trận logic của quan hệ hai ngôi
- 1.4 Quan hệ n ngôi
- 2 Quan hệ tương đương và quan hệ thứ tự
- 2.1 Một số tính chất của quan hệ trên một tập
- 2.2 Quan hệ tương đương
- 2.3 Quan hệ thứ tự
- 2.4 Các phần tử đặc biệt trong tập được sắp
- 3 Tích các quan hệ và bao đóng bắc cầu
- 3.1 Quan hệ tích
- 3.2 Tính chất của quan hệ bắc cầu
- 4 Biểu diễn đồ thị của quan hệ hai ngôi
- 5 Quan hệ và ánh xạ
- 6 Quan hệ như là cấu xạ
- 7 Tham khảo
- 8 Thư mục
- 9 Liên kết ngoài
Bài giảng toán rời rạc pptx
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây [885.15 KB, 88 trang ]
Tr−êng §¹i häc Vinh
NguyÔn Trung Hßa
To¸n rêi r¹c
Vinh - 2010
0
Chơng 1. Quan hệ
1.1. Quan hệ hai ngôi v các tính chất
1.1.1. Định nghĩa v các ví dụ
Trongcuộcsốngtathờng gặp rất nhiều hi ện tợng đợc diễn tả bởi
thuật ngữ quan hệ, chẳng hạn quan hệ bạn bè, quan hệ đồng hơng, quan hệ
thầy trò, Hoặc cuối năm học ta thờng quan tâm đến điểm trung bình chung
học tập của các thnh viên trong lớp, khi đó ta có mối quan hệ giữa sinh viên
của lớp v số thực l điểm trung bình chung học tập của các sinh viên. Hay
cuối học kỳ ta phải xếp lịch thi học kỳ, khi đó ta thờng xét quan hệ giữa
lớp trong khoa v môn đợc lớp đó học trong học kỳ, gọi tắt l quan hệ Học,
chẳng hạn 45A Học xác suất; 44B Học toán rời rạc; 44B Học kinh tế, 44A
Học tâm lý học, 44A Học kinh tế Có nghĩa l ta phải ghép cặp [lớp x, môn
y] v hiểu l lớp x học môn y. Nh vậy, tập tất cả các cặp [lớp x, môn y] sao
cho lớp x học môn y đặc trng cho quan hệ Học,v ta có thể coi quan hệ Học
l tập con của tích đề-các của hai tập các lớp v các môn học. Hình thức hoá
các hiện tợngấytacókháiniệmquanhệ,l một khái niệm rất quan trọng
của toán học v đợc ứng dụng trong nhiều lĩnh vực, đặc biệt l trong tin học.
Một quan hệ hai ngôi từ tập A đến tập B l một tập con R của tích đề
các A
ì B.Nếu[a, b] R thì ta nói rằng a có quan hệ R với b v ký hiệu
aRb thay thế cho ký hiệu [a, b].
Ví dụ 1. Quan hệ Họckỳ4= {[a, b] với a l một lớp nođócủakhoá
44, còn b l một môn m lớp a học trong học kỳ 4 [năm học 2004-2005]}.
Rõ rng quan hệ Họckỳ4l một tập con của quan hệ Học đã nói ở trên.
Ví dụ 2. Quan hệ trực thuộc [hnh chính] l tập con I c ủa tích đề-các
của tập H tất cả các huyện của V iệt nam v tập T l tập tất cả các tỉnh của
Việt nam. Khi đó [Hng nguyên, Nghệ an], [Tĩnh gia, Thanh hoá], [Hơng
sơn, H tĩnh], [Nam đn, Nghệ an] l nhữngphầntửcủatậpIv ta th ờng
nói Hng nguyên trực thuộc Nghệ an, Tĩnh gia trực thuộc Thanh hoá, Hơng
sơn trực thuộc H tĩnh, Nam đn trực thuộc Nghệ an.
Ví dụ 3. Một hm số bất kỳ trên miền xác định D l một quan hệ từ D
đến R,m mỗi phần tử của quan hệ nyl một cặp [x, f[x]],v đây l một
loại quan hệ hai ngôi đặc biệt, ở chỗ mọi x D đềucóv chỉ có duy nhất
một f[x] tơng ứng.
1
Trong số các quan hệ hai ngôi, ta quan tâm đặc biệt đến các quan hệ hai
ngôi trên một tập:
Một quan hệ hai ngôi R trên tập A l một quan hệ từ A đến A,nghĩa
l R l tập con của bình phơng đề các A ì A.
Ví dụ 4. Xét tập A tất cả sinh viên lớp 48K, ta có các quan hệ hai ngôi
sau:
a. Quan hệ đồng hơng, gồm tất cả các cặp hai sinh viên [a, b] sao cho
a có gia đình cùng huyện với b.
b. Quan hệ công tác, gồm tất cả các cặp h ai sinh viên [a, b] sao cho a
có công việc cần trao đổi với b.
c. Quan hệ bạn thân, gồm tất cả các cặp hai sinh viên [a, b] sao cho a
chơi thân với b.
d. Quan hệ lớn tuổi hơn, gồm tất cả các cặp hai sinh viên [a, b] sao cho
a sinh trớc b.
Ví dụ 5. Xét tập các số nguyên Z:
a. Quan hệ đồng d theo mô đun 5 trên tập các số nguyên Z đợc định
nghĩa nh sau: a đợc gọi l đồng d với b theo mô đun 5 khi v chỉ khi a
v b
có cùng số d khi chia cho 5.
b. Quan hệ < trên tập Z.
1.1.2. Các phép toán trên tập các quan hệ
Giả sử có các quan hệ hai ngôi từ tập X đến tập Y , khi đó chúng đều l
các tập con của tích đề-các X ì Y , nên có thể xét các phép toán tập hợp l
phép hợp, phép giao, phép trừ, phép lấy hiệu đối xứng. Chúng đợc xem l
các phép toán trên các quan hệ v kết quả của chúng đều l cácquanhệhai
ngôi từ X đến Y .
Ta sẽ xây dựng viphéptoánmới.
Phép nghịch đảo: Giả sử R l một quan hệ hai ngôi từ tập X đến tập
Y . Quan hệ ngợc [nghịch đảo] của quan hệ R l quan hệ S từ Y đến X sao
cho S = {[y,x]|[x, y] R}.Quanhệngợc của R đợc ký hiệu bởi R
1
.
Ví dụ 1. Nếu X = {1, 2, 3, 4}, Y = {a, b, c}, R = {[1,b], [2,a], [4,c]}
thì R
1
= {[b, 1], [a, 2], [c, 4]}.
Phép hợp thnh: Giả sử R l một quan hệ hai ngôi từ tập X đến tập Y ,
S l một quan hệ hai ngôi từ tập Y đến tập Z. Hợp thnh của các quan hệ
2
R v S l quan hệ T từ X đến Z với T = {[x, z]|y Y sao cho [x, y]
R v [y, z] S}. Quan hệ hợp thnh T đợc ký hiệu bởi R S hoặc RS.
ChúýrằngRS có thể l tập rỗng mặc dầu R v S đều khác rỗng v phép
hợp thnh có tính chất kết hợp, nghĩa l [R S] V = R [S V ].
Ví dụ 2. Giả sử X = {1, 2, 3, 4}, Y = {a, b, c
}, Z = {, , },
R = {[1,b], [2,a], [3,b], [4,c]}, S = {[a, ], [b, ], [c, ]}, khi đó
RS = {[1, ], [2, ], [3, ], [4, ]}.
Phép luỹ thừa: Giả sử R l một quan hệ hai ngôi trên tập X. Luỹ thừa
bậc n của quan hệ R ,kýhiệul R
n
,vớin =1, 2, l quan hệ đợc xác
định bởi hệ thức truy hồi R
n
= R
n1
R với R
1
= R.
Ví dụ 3. Giả sử X = {1, 2, 3, 4}, R = {[1, 2], [2, 1], [3, 2], [4, 3]}.Ta
có
R
2
= RR = {[1, 1], [2, 1], [3, 1], [4, 2]},
R
3
= R
4
= {[1, 1], [2, 1], [3, 1], [4, 1]},
v do đó R
n
= R
3
với mọi n 3.
1.1.3. Các tính chất có thể có của quan hệ hai ngôi trên một tập
a. Quan hệ hai ngôi R trên một tập X đợc gọi l có tính chất phản xạ
nếu với mọi a X đều có aRa.
Ví dụ 1. Quan hệ đồng hơng ở ví dụ 4, quan hệ đồng d ởvídụ5
[mục 1.1.1] l cácquanhệcótínhphảnxạ.
b. Quan hệ hai ngôi R trên một tập X đợc gọi l có tính chất đối xứng
nếu với mọi a, b X, aRb khi v chỉ khi bRa.
Ví dụ 2. Cácquanhệđồnghơng, bạn thân ở ví dụ 4; quan hệ đồng d
ởvídụ5[mục1.1.1]l các quan hệ có tính đối xứng.
c. Quan hệ hai ngôi R trên một tập X đợc gọi l có tính chất phản
xứng nếu với mọi a, b X sao cho aRb v bRa thì a = b.
Ví dụ 3. Quan hệ < trên tập Z [ví dụ 5 mục 2.1.1] có tính phản xứng.
d. Quan hệ hai ngôi R trên một tập X đợc gọi l có
tính chất bắc cầu
nếu với mọi a, b, c X sao cho aRb v bRc thì aRc.
Ví dụ 4. Các quan hệ đồng hơng,lớntuổihơnởvídụ4;cácquanhệ
đồng d, < ở ví dụ 5 [mục 1.1.1] có tính chất bắc cầu.
Sau đây ta có định lý về mối liên hệ giữa quan hệ bắc cầu R v các luỹ
thừa của R.
3
Định lý 1. Qu an hệ R trên tập A có tính bắc cầu khi v chỉ khi R
n
R với
mọi n =1, 2, 3,
Chứng minh. Cần: Rõ rng R
1
R, tức l với n =1điều kiện cần đã
đúng.
Giả sử R
n
R ta sẽ chứng minh R
n+1
R. Thật vậy, theo định nghĩa
của luỹ thừa bậc n củaquanhệtacóR
n+1
= R
n
R nghĩa l với mọi [x, z],
[x, z] R
n+1
khi v chỉ khi tồn tại y A sao cho [x, y] R
n
v [y,z] R.
Theo giả thiế quy nạp, [x, y ] R
n
kéo theo [x, y] R v do R có tính chất
bắc cầu nên từ [x, y] R v [y, z ] R suy ra [x, z] R.VậyR
n+1
R.
Đủ: Giả sử [x, y] R v [y, z] R,khiđó[x, z] R
2
. Theo giả thiết
R
n
R với mọi n =1, 2, nên ta có ngay R
2
R,suyra[x, z] R,tức
l R có tính bắc cầu.
Bitập:
1. Có bao nhiêu quan hệ khác nhau từ tập có m phần tử đến tập có n phần
tử?
Quan hệ bù của quan hệ R,kýhiệul
R,l tập các cặp đợc sắp
{[a, b]|[a, b] / R}.TìmR
1
v R trong các trờng hợp sau:
2. R l quan hệ < trên Z.
3. R l quan hệ chia hết trên N
+
4. R l quan hệ hm , nghĩa l R = {[a, f[a]] f[a] l ảnh của a qua
ánh xạ f.
5. Liệt kê 16 quan hệ khác nhau trên tập {0, 1}
6. Trongsố16quanhệkhácnhautrêntập{0, 1}, những quan hệ nol
a. Phản xạ
b. Đối xứng.
c. Phản xứng.
d. Bắc cầu.
7. Có bao nhiêu quan hệ trên tập gồm n phần tử l
a. Phản xạ
b. Đối xứng.
c. Phản xứng.
8. Cho R l quan hệ có tính phản xạ trên tập A. Chứng minh rằng R
n
cũng
cótínhphảnxạvớimọisốnguyêndơng n.
4
9. Cho R l quan hệ có tính đối xứng trên tập A. Chứng minh rằng R
n
cũng có tính đối xứng với mọi số nguyên dơng n.
10. Chỉ ra một ví dụ về một quan hệ bắc cầu R sao cho R
2
= R
1.2. Biểu diễn quan hệ
1.2.1. Ma trận logic v các phép toán trên các ma trận logic
Giả sử a, b l các biến [biến boolean] chỉ nhận một trong hai g iá trị 0
hoặc 1 [giá trị logic].
Ta gọi tuyển của a v b l giá trị
c = a b :=
1 nếu a =1hoặc b =1
0 nếu a = b =0,
ký hiệu tuyển của a v b bởi a b.
Ta gọi hội của a v b l giá trị
c = a b :=
1 nếu a = b =1
0 nếu a =0hoặc b =0,
ký hiệu hội của a v b bởi a b.
Ma trận logic cỡ m ì n l một ma trận có
m dòng v n cột, trong đó
các phần tử của nó chỉ nhận một trong hai giá trị 0 hoặc 1.
Giả sử cho hai ma trận A =[a
i,j
] v B =[b
i,j
] cũng cỡ.
a. Tuyển [tổng boolean] của hai ma trận A v B,kýhiệuA B,l ma trận
C =[c
i,j
] trong đó c
i,j
= a
i,j
b
i,j
.
b. Hội của hai ma trận A v B,kýhiệuA B,l ma trận C =[c
i,j
] trong
đó c
i,j
= a
i,j
b
i,j
.
c. Tích boolean của ma trận A cỡ m ì n v ma trận B cỡ n ì p l ma trận
C = A B := [c
i,j
] cỡ m ì p trong đó
c
i,j
=[a
i,1
b
1,j
] ããã [a
i,k
b
k,j
] ããã [a
i,n
b
n,j
]
[các dấu ngoặc có thể đợc bỏ đi]. Ta ký hiệu tích boolean của hai ma trận
A v B l A B
Dễ thấy rằng ma trận vuông I
n
=[
i,j
] cấp n trong đó
i,j
=
1 nếu i = j
0 nếu i = j
5
l ma trận đơn vị đối với phép nhân boolean, nghĩa l với mọi ma trận A cỡ
mìn [hoặc mọi ma trận B cỡ nìp] ta đều có AI
n
= A [hoặc I
n
B = B].
Đồng thời tích boolean có tính chất kết hợp, nghĩa l A[B C]=[AB]C
nếu một trong hai vế của đẳng thức nytồntại.
ThuậttoántínhtíchboolecủamatrậnA cỡ m ì n v ma trận B cỡ
n ì p,lu trữ kết quả vomatrậnC.
Với i := 1 đến m
Với j := 1 đến p
c
i,j
:= 0
với k := 1 đến n
c
i,j
:= c
i,j
[a
i,k
b
k,j
].
Vì tích boolean của các ma trận logic có tính chất kết hợp nên ta có thể
định nghĩa luỹ thừa boolean nh sau:
d. Luỹ thừa boole bậc r của một ma trận vuông logic A cấp n,kýhiệu
bởi A
[r]
đợc định nghĩa bằng truy hồi nh sau:
A
[r]
= A A
[r1]
, với r =1, 2, v A
[0]
= I
n
.
hoặc đợc xác định bởi
A
[r]
= A A ãããA
rlần
1.2.2. Biểu diễn quan hệ bằng ma trận
a. Xây dựng biểu diễn
Cho A l tập hợp hữu hạn có m phần tử đã đợc đánh số thứ tự A =
{a
1
,a
2
, a
m
} v B l tập hợp hữu hạn có n phần tử đã đợc đánh số thứ tự
B = {b
1
,b
2
, b
n
} . Khi đó tích đề các A ì B có m ì n phần tử v một cách
tự nhiên ta có thể biểu diễn chúng nh l một bảng gồm m dòng v n cột,
trongđóvịtríởdòngi cột j l cặp [a
i
,b
j
].VìR l một tập con của tích đề
các Aì B, nên biểu diễn của R sẽ đợctạonêntừbảngởtrênbằngcáchcặp
no thuộc R sẽ đợc thay bởi 1, cặp no không thuộc R sẽ đợc thay bởi 0.
Từ đó ta có định nghĩa biểu diễn sau: Giả sử R l mộtquanhệtừtậpA đến
tập B v cácphầntửcủaA, B đã đợc sắp xếp theo một thứ tự cố định no
6
đó A = {a
1
,a
2
, a
m
}, B = {b
1
,b
2
, b
n
}. Matrậnlogicbiểudiễnquanhệ
R l ma trận M
R
=[r
i,j
],trongđó
r
i,j
=
1 nếu [a
i
,b
j
] R
0 nếu [a
i
,b
j
] / R
Để ý rằng thứ tự của các phần tử của A v B honton tuỳ ý, tuy nhiên
phải đợc cho trớc cố định. Nói cách khác ứng với một thứ tự của các phần
tử trong A hoặc B ta sẽ có một biểu diễn ma trận của quan hệ R.Đặcbiệt
khi A = B ta quy định thứ tự của các phần tử của A v của B l nh nhau.
b. Các ví dụ.
c. Ma trận biểu diễn các quan hệ phản xạ, đối xứng, phản xứng
Biểu diễn quan hệ bởi ma trận logic cho ta một cách nhìn trực quan hơn
các quan hệ. Khi A = B, với biểu diễn nytadễdng kiểm tra các tính chất
của quan hệ R.
Quan hệ R trên tập A có tính chất phản xạ khi v chỉ khi M
R
l ma trận
cómọiphầntửtrênđờng chéo chính bằng 1.
Quan hệ R trên tập A có tính chất đối xứng khi v chỉ khi M
R
l ma
trận đối xứng qua đờng chéo chính.
Quan hệ R trên tập A có tính chất phản xứng khi v chỉ khi M
R
l ma
trận có r
i,j
=0hoặc r
j,i
=0khi i = j.
d. Ma trận biểu diễn hợp, giao của hai quan hệ.
Từ định nghĩa ma trận biểu diễn quan hệ v các định nghĩa hợp v giao
của hai quan hệ [nh l hợp v giao của hai tập hợp], tuyển, hội của các ma
trận logic ta dễ dngsuyrarằngmatrậnbiểudiễnhợpcủahaiquanhệl
tuyển của hai ma trận logic biểu diễn các quan hệ đã cho v ma trận biểu diễn
giao của hai quan hệ l hội của hai ma trận logic biểu diễn các quan hệ đã
cho.
e. Ma trận biểu diễn hợp thnh của hai quan hệ.
Định lý. Giả sử A, B, C l các tập hữu hạn có số các phần tử tơng ứng
l m, n, p.GiảsửR, S l các quan hệ hai ngôi từ A đến B v từ B đến C
tơng ứng. Gọi M
R
=[r
i,k
],M
S
=[s
k,j
],M
RS
=[t
i,j
] l cácmatrậnbiểu
diễn R, S, RS tơng ứng. Khi đó ta có
M
RS
= M
R
M
S
7
Chứng minh:
Xét t
i,j
l phầntửbấtkỳ[ởdòngi cột j]củaM
RS
.Tacót
i,j
=1khi
v chỉ khi a
i
RSc
j
,điềuđócónghĩal tồn tại b
k
no đó thuộc B để a
i
Rb
k
v b
k
Sc
j
, nghĩa l tồn tại k để r
i,k
=1v s
k,j
=1, nghĩa l
[r
i,1
s
1,j
] [r
i,k
s
k,j
] [r
i,n
s
n,j
]=1,
nghĩa l phầntửởdòngi cột j của ma trận tích M
R
M
S
bằng 1. Vậy
M
RS
= M
R
M
S
.
1.2.3. Biểu diễn quan hệ bằng đồ thị có hớng.
a. Định nghĩa đồ thị có hớng
Đồ thị có hớng l một bộ đôi G =[V,E] trong đó V l một tập hợp,
gọi l tập các đỉnh; E V
2
,l tập các cặp sắp thứ tự các phần tử của V ,
đợc gọi l tập các cạnh. Với mỗi cạnh [a, b] E,đỉnha đợc gọi l đỉnh
đầu, b gọi l đỉnh cuối của cạnh. Nếu a trùng b, cạnh [a, a] đợc gọi l một
khuyên. Đồ thị có hớng thờng đợc biểu diễn [minh hoạ] một cách trực
quan nh hình vẽ dới đây: Ví dụ.
b. Đồ thị có hớngbiểudiễnquanhệ
Từ định nghĩa đồ thị có hớng ở trên, nếu R l một quan hệ hai ngôi
trên tập hợp A,tacóthểbiểudiễnR nh l một đồ thị G =[A, R] [với tập
A đóng vai trò của tập V ;TậpR đóng vai trò của tập E]. Do đó có thể đồng
nhất một quan hệ R trên tập A vớimộtđồthịcóhớng G v cách tiếp cận
nychotamộtcáchnhìntrựcquanhơn.
8
Ví dụ. Cho tập A = {1, 2, 3, 4}, R l quan hệ < t hông thờng, khi đó
đồ thị biểu diễn R đợc minh hoạ bởi hình sau:
Ví dụ. Cho đồ thị G =[V,E] đợc minh hoạ bởi hình:
Khi đó ta xác định đợc quan hệ hai ngôi E tơng ứng trên tập V =
{1, 2, 3, 4} nh sau: E = {[1, 1], [1, 3], [2, 2], [2, 4], [3, 3], [4, 4]}. Quan hệ
ny cũng có thể diễn đạt l quan hệ đồng d theo môđun 2, hoặc l quan
hệ cùng chẵn, cùng lẻ.
c. Đồ thị biểu diễn quan hệ phản xạ, đối xứng, phản xứng, bắc cầu.
Theo biểu diễn quan hệ bởi đồ thị có hớng nh trên,tanhậnthấyrằng
Quan hệ R trên tập A có tính chất phản xạ khi v chỉ khi đồ thị G =
[A, R] có khuyên ở tất cả các đỉnh của nó.
Quan hệ R trên tập A có tính chất đối xứng khi v chỉ khi trên đồ thị
G =[A, R] nếucócạnhcóđỉnhđầul a,đỉnhcuốil b, thì sẽ có cạnh ngợc
lại, có đỉnh đầu l b v có đỉnh cuối l a.
Quan hệ R trên tập A có tính chất phản đối xứng khi v chỉ khi trên đồ
thị G =[A, R] nếucócạnhcóđỉnhđầul a,đỉnhcuốil b, thì sẽ không có
cạnh ngợc lại, có đỉnh đầu l b v có đỉnh cuối l a,nghĩal với mỗi cặp
đỉnh chỉ có nhiều nhất một cạnh giữa chúng.
Quan hệ R trên tập A có tính chất bắc cầu khi v chỉ khi trên đồ thị
G =[A, R] nếucócạnhcóđỉnhđầul a,đỉnhcuốil b v có cạnh có đỉnh
đầu l b,đỉnhcuốil c thì sẽ có cạnh có đỉnh đầu l a v đỉnh cuối l c.Tuy
nhiên việc kiểm tra một quan hệ có tính bắc cầu hay không thờng khó khăn
hơn việc kiểm tra các tính chất trên.
9
Ví dụ: Kiểm tra tính bắc cầu của quan hệ sau đây:
Bitập.
1. Cho tập A = {1, 2, 3, 4}. BiểudiễncácquanhệR, S trên A bằng ma
trận với thứ tự của các phần tử của A đợc liệt kê tăng dần v R, S cho
sau đây:
a. R = {[1, 1], [1, 2], [2, 3], [4, 2]}.
b. S = {[1, 1], [1, 3], [2, 1], [2, 3], [2, 4], [3, 1], 3, 2], [4, 1]}
2. Cho tập A = {a, b, c, d} v các quan hệ P, Q trên tập A đợc biểu diễn
bởi ma trận sau [t
ơng ứng vớ i thứ tự đã đợc liệt kê của phần tử của
A]: a. M
P
=
1010
0101
1100
0011
;b.M
Q
=
1001
0110
1010
0011
.Hãy
liệt kê các cặp thuộc mỗi quan hệ P, Q.
3. Các quan hệ đã cho trong các bitập1v 2 có những tính chất gì trong
các tính chất phản xạ, đối xứng, phản xứng, bắc cầu.
4. Tìm các ma trận biểu diễn của các quan hệ P
1
, P,P
2
với P l quan
hệ tìm đợc trong bitập2.
5. Tìm các ma trận biểu diễn của các quan hệ P Q, P Q, P Q, QP, P
2
,P
3
,P
4
với P v Q l cácquanhệcómatrậnbiểudiễnM
P
,M
Q
cho trong bi
tập 2.
6. Vẽ các đồ thị biểu diễn các quan hệ R, S cho trong bitập1v các đồ
thịbiểudiễncácquanhệP, Q tìm đợc trong bitập2.
7.ChứngminhrằngnếuM
R
l ma trận biểu diễn quan hệ R thì M
[k]
R
l
ma trận biểu diễn quan hệ R
k
,vớik =1, 2, 3,
1.3. Các bao đóng của quan hệ.
1.3.1. Định nghĩa bao đóng.
Một quan hệ R trên một tập A có th ể có hoặc k hông có một tính c hất P
no đó [chẳng hạn tính chất đối xứng]. Nếu có một quan hệ S trên A có tính
10
chất P , chứa R sao cho mọi quan hệ có tính chất P chứa R đều chứa S thì
S sẽ đợc gọi l bao đóng của R đối với P . Chẳng hạn nếu P l tính chất
phản xạ, [đối xứng, phản xứng, bắc cầu] thì các bao đóng của R đối với P sẽ
đợc gọi l bao đóng phản xạ, [bao đóng đối xứng, bao đóng phản xứng, bao
đóng bắc cầu]. Có thể nhận thấy rằng bao đóng S của một quan hệ R đối với
tính chất P l giao của mọi quan hệ chứa R v có tính chất P .
a. Xác định Bao đóng phản xạ
Bao đóng phản xạ của một quan hệ hai ngôi R trên tập A l hợp R
của R v quan hệ bằng nhau = {[a, a]|a A} trên A [Hãy chứng minh?].
b. Xác định Bao đóng đối xứng.
Bao đóng đối xứng của một quan hệ hai ngôi R trên tập A l hợp RR
1
của R v quan hệ ngợc R
1
= {[b, a]|[a, b] R} trên A [Hãy chứng minh?].
Để xác định bao đóng bắc cầu của một quan hệ R ta cần đaramộtsố
khái niệm v kết quả bổ trợ.
1.3.2. Đờng đi trong đồ thị có hớng
a. Định nghĩa. Đờng đi từ a đến b,độdi n trongđồthịcóhớng G
l một dãy có thứ tự gồm n cạnh [x
0
,x
1
], [x
1
,x
2
], ,[x
n1
,x
n
] trong G,
trong đó x
0
= a , x
n
= b v đỉnh cuối của cạnh thứ i l đỉnh đầu của cạnh
thứ i +1, [i =1, 2, n 1]. Để đơn giản hơn ta c ó thể sử dụng ký hiệu
x
0
,x
1
, ,x
n1
,x
n
.Đỉnhx
0
đợc gọi l đỉnh khởi đầu v x
n
đợc gọi l
đỉnh kết thúc của đờng đi. Đờng đi có đỉnh khởi đầu v đỉnh kết thúc trùng
nhau thì đợc gọi l một chu trình. Để tránh nhầm lẫn ta quy ớc không có
đờngđiđộdi 0, nghĩa l đờng đi [a, a] l một khuyên v có độ di1.
Chú ý rằng một đờng đi thì tơng ứng với một dãy các đỉnh, tuy nhiên,
một dãy các đỉnh chachắcđãxácđịnhmộtđờng đi.
11
b. Vi dụ. Trongcácdãyđỉnhchodới đây, dãy đỉnh nol một
đờng đi trong đồ thị G chotrênhìnhvẽ? [a, b, d, c, b, a, e]; [a, c, d, e, b, a, d];
[a, d, g, b],
c. Đờng đi trong quan hệ R.Địnhlývềđờng đi độ di n v quan hệ
R
n
.
Bởivìmộtđồthịcóhớng G có thể tơng ứng 1-1 với một quan hệ hai
ngôi R trên tập các đỉnh của nó, do đó từ định nghĩa đờng đi ở trên, ta có
thể định nghĩa đờng đi từ a đến b trongquanhệR l một dãy các phần tử
[x
0
,x
1
], [x
1
,x
2
], ,[x
n1
,x
n
] của quan hệ R , trong đó x
0
= a , x
n
= b
Định lý 1. Giả sử R l một quan hệ hai ngôi trên tập A.Cómộtđờng đi
chiều di n từ a đến b trong quan hệ R khi v chỉ khi [a, b] R
n
.
Chứng minh. [bằng quy nạp].
Với n =1,tacóđờng đi chiều di1từa đến b trong R nghĩa l
[a, b] R
1
, tức l [a, b] R.
Giảsửđịnhlýđúngvớin 1,nghĩal có đờngđiđộdi n 1 từ a
đến b trong R khi v chỉ khi [a, b] R
n1
.
Với n,tacóđờngđiđộdi n từ a đến b trong R khi v chỉ khi tồn
tại một dãy n phần tử thuộc R: [a, x
1
], [x
1
,x
2
], ,[x
n2
,x
n1
], [x
n1
,b].
Với n 1 phần tử đầu ta xác định một đờng đi trong R có độ di n 1,
do đó theo giả thiết quy nạp ta có [a, x
n1
] R
n1
. Kết hợp biểu thức liên
thuộc ny với phần tử thứ n của đờng đi, ta có [a, b] R R
n1
, nghĩa l
[a, b] R
n
.
1.3.3. Xác định bao đóng bắc cầu
a. Định nghĩa quan hệ liên thông. Cho R l mộtquanhệtrêntậpA.
Quan hệ liên thông R
tơng ứng với R l quan hệ bao gồm các cặp [a, b]
12
sao cho có một đờng đi trong R từ a đến b.
R
= {[a, b]|a = x
0
,x
1
, ,x
n
= b sao cho [x
i1
,x
i
] R, i =1, n}.
Từ định lý ở cuối mục trớc ta nhân thấy ngay rằng R
l hợp của tất cả các
tập R
n
, n =1, 2, , tức l
R
=
n=1
R
n
b. Các ví dụ
Định lý 2. Bao đóng bắc cầu của quan hệ R chính l quan hệ liên thông R
tơng ứng với R.
Để chứng minh các định lý tiếp theo ta sử dụng khái niệm đỉnh trong
của một đờng đi:
Giả sử a = x
0
,x
1
, ,x
m1
,x
m
= b l một đờng đi trong R từ a đến
b. Khi đó các đỉnh x
i
với 0