Tài liệu Toán học - Tập hợp, ánh xạ: 1. Lý thuyết tập hợp
2. Ánh xạ
Tập hợp là khái niệm cơ bản của toán học dùng
để biểu diễn 1 lực lượng nào đó
Ví dụ : Tập hợp số thực
Sơ đồ Ven :
Ký hiệu : a A ;
Tập hợp rỗng không chứa bất kỳ phần tử nào. Ký
hiệu : Ø
Liệt kê :
A={1, 2, 3, 4, a, b}
Theo tính chất :
B={ n N | n là số chính phương}
Hai tập hợp bằng nhau khi chúng có cùng các
phần tử
Cho tập hợp: và
Hỏi A, B và C có bằng nhau hay không ?
}012|{ 2 xxRxB}4,3{ A
}2,3{ C
Nếu mọi phần tử của tập A đều là phần tử của
tập B thì A là tập hợp con của B.
Ký hiệu :
Ta luôn có : ;
Chứng minh hai tập hợp bằng nhau ?
BA
AA AØ
Cho X là một tập hợp. Khi đó tập tất cả các
tập con của X được ký hiệu là P(X)
Ví dụ : Cho tập X = {a, b}
Với tập hợp |X|=k. P(X)=?
( ) { ,{ },{ },{ , }}P X a b a b
{1,2,3}, ( ) ?Y P Y
a. Phép hợp : Cho 2 tập hợp A và B. Ta nói A
hợp B. Ký hiệu :
Ví dụ : A = { 1, 2 , 3}; B = { a, b, c }
Xác ...
268 trang |
Chia sẻ: Khủng Long | Lượt xem: 1423 | Lượt tải: 0
Bạn đang xem trước 20 trang mẫu tài liệu Toán học - Tập hợp, ánh xạ, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
1. Lý thuyết tập hợp
2. Ánh xạ
Tập hợp là khái niệm cơ bản của toán học dùng
để biểu diễn 1 lực lượng nào đó
Ví dụ : Tập hợp số thực
Sơ đồ Ven :
Ký hiệu : a A ;
Tập hợp rỗng không chứa bất kỳ phần tử nào. Ký
hiệu : Ø
Liệt kê :
A={1, 2, 3, 4, a, b}
Theo tính chất :
B={ n N | n là số chính phương}
Hai tập hợp bằng nhau khi chúng có cùng các
phần tử
Cho tập hợp: và
Hỏi A, B và C có bằng nhau hay không ?
}012|{ 2 xxRxB}4,3{ A
}2,3{ C
Nếu mọi phần tử của tập A đều là phần tử của
tập B thì A là tập hợp con của B.
Ký hiệu :
Ta luôn có : ;
Chứng minh hai tập hợp bằng nhau ?
BA
AA AØ
Cho X là một tập hợp. Khi đó tập tất cả các
tập con của X được ký hiệu là P(X)
Ví dụ : Cho tập X = {a, b}
Với tập hợp |X|=k. P(X)=?
( ) { ,{ },{ },{ , }}P X a b a b
{1,2,3}, ( ) ?Y P Y
a. Phép hợp : Cho 2 tập hợp A và B. Ta nói A
hợp B. Ký hiệu :
Ví dụ : A = { 1, 2 , 3}; B = { a, b, c }
Xác định :
( ) ( )x A B x A x B
A B
A B
1. Tính lũy đẳng :
2. Tính giao hoán :
3. Tính kết hợp :
4. Hợp với tập rỗng :
A A A
A B B A
( ) ( )A B C A B C
A A A
b. Phép giao : Giao của 2 tập hợp A và B là tập hợp tạo
bởi các phần tử vừa thuộc A vừa thuộc B.
Ký hiệu :
Ví dụ : Xác định giao của hai tập hợp sau :
A = { 1, 0 , 2, a, } B = { 2, 0, 1 }
( ) ( )x A B x A x B
A B
1. Tính lũy đẳng :
2. Tính giao hoán :
3. Tính kết hợp :
4. Giao với tập rỗng :
Tính phân phối của phép giao và phép hợp :
A A A
A B B A
( ) ( )A B C A B C
A A
1) ( ) ( ) ( )
2) ( ) ( ) ( )
A B C A B A C
A B C A B A C
c. Phép hiệu : Hiệu của hai tập hợp là tập tạo bởi tất
cả các phần tử thuộc tập A mà không thuộc tập B
Ký hiệu A\B
( \ ) ( )x A B x A x B
Phần bù : Khi thì B\A gọi là bù của A
trong B. Ký hiệu hay
A B
A
BC A
Tích Đề các của tập hợp A với tập hợp B (theo thứ tự
lấy) là tập hợp bao gồm tất cả các cặp thứ tự (x,y) với
Ký hiệu AxB hoặc A.B
Chú ý: Tích của 2 tập hợp không có tính chất giao
hoán.
Ví dụ : A ={1, 2} B={a, b}
A x B = { (1,a), (1,b), (2,a), (2,b)}
,x A y B
( , ) ( )x y A B x A y B
Chứng minh :
và
1)
2)
A B A B
A B A B
)( BAxBAx
Ax Bx
BxAx
BxAx
Các phép toán trên tập hợp có thể mở rộng
cho nhiều hơn 2 tập hợp tạo thành 1 phân
hoạch :
i i
i I
A {x i I, x A }
i i
i I
A {x i I, x A }
i i i I i i
i I
A (x ) i I, x A
Cho hai tập hợp X, Y . Ánh xạ giữa hai tập
X và Y là một qui tắc sao cho mỗi x thuộc X
tồn tại duy nhất một y thuộc Y để y = f(x)
Ta viết :
:
( )
f X Y
x f x
, ! : ( )x X y Y y f x
Cho :
X là miền xác định của ánh xạ.
Y là đích của ánh xạ.
YB
XA
YXf
:
f(A) = {f(x) x A} = {y Y x A, y = f(x)}
Như vậy y f(A) x A, y = f(x);
y f(A) x A, y f(x)
f–1(B) = {x X f(x) B} được gọi là ảnh
ngược của B
f–1(B)
x f –1(B) f(x) B
f gọi là đơn ánh nếu f(x1)=f(x2) thì x1=x2, hay
hai phần tử khác nhau sẽ có ảnh khác nhau
Ví dụ : là một đơn ánh từ
3)( xxfx RR
gọi là toán ánh nếu hay
đều tồn tại sao cho
Khi đó người ta cũng gọi f là ánh xạ từ X lên Y
Yy
Xx yxf )(
f )()( YfXf
Song ánh là ánh xạ vừa là đơn ánh, vừa là
toàn ánh
Song ánh Đơn ánh Toàn ánh
Cho hai ánh xạ f : X Y và g : Y' Z
trong đó Y Y'. Ánh xạ tích h của f và g là ánh xạ từ X vào Z xác
định bởi: h : X Z
x h(x) = g(f(x))
Ta viết: h = gof : X Y Z
Ví dụ :
)sin()(
)(sin)(
)(,sin)(
2
0
2
0
2
xygf
xxfg
yygxxf
fg0Nếu đơn ánh thì f là đơn ánh
Nếu song ánh thì g và f đều là song ánh fg0
Nếu toàn ánh thì g là toàn ánh fg0
1. Định nghĩa và tính chất
2. Biểu diễn quan hệ
3. Quan hệ tương đương. Đồng dư
4. Quan hệ thứ tự.
2
Một quan hệ hai ngôi từ tập A đến tập B là tập con của tích
Descartes R A x B.
Chúng ta sẽ viết a R b thay cho (a, b) R
Quan hệ từ A đến chính nó được gọi là quan hệ trên A
3
R = { (a1, b1), (a1, b3), (a3, b3) }
A = tập sinh viên; B = các lớp học.
R = {(a, b) | sinh viên a học lớp b}
4
Cho A = {1, 2, 3, 4}, và
R = {(a, b) | a là ước của b}
Khi đó
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4,4)}
5
1 2 3 4
1 2 3 4
Định nghĩa. Quan hệ R trên A được gọi là phản xạ nếu:
(a, a) R với mọi a A
Ví dụ. Trên tập A = {1, 2, 3, 4}, quan hệ:
R1 = {(1,1), (1,2), (2,1), (2, 2), (3, 4), (4, 1), (4, 4)}
không phản xạ vì (3, 3) R1
R2 = {(1,1), (1,2), (1,4), (2, 2), (3, 3), (4, 1), (4, 4)} phản
xạ vì (1,1), (2, 2), (3, 3), (4, 4) R2
6
7
Quan hệ trên Z phản xạ vì a a với mọi a Z
Quan hệ > trên Z không phản xạ vì 1 > 1
Quan hệ R trên A được gọi là đối xứng nếu:
a A b A (a R b) (b R a)
Quan hệ R được gọi là phản xứng nếu
a A b A (a R b) (b R a) (a = b)
8
Ví dụ.
Quan hệ R1 = {(1,1), (1,2), (2,1)} trên tập
A = {1, 2, 3, 4} là đối xứng
Quan hệ trên Z không đối xứng.
Tuy nhiên nó phản xứng vì
(a b) (b a) (a = b)
Định nghĩa. Quan hệ R trên A có tính bắc cầu nếu
a A b A c A (a R b) (b R c) (a R c)
Ví dụ.
Quan hệ R = {(1,1), (1,2), (2,1), (2, 2), (1, 3), (2, 3)}
trên tập A = {1, 2, 3, 4} có tính bắc cầu.
Quan hệ và “|”trên Z có tính bắc cầu
(a b) (b c) (a c)
(a | b) (b | c) (a | c)
9
1. Ma trận
2. Biểu diễn Quan hệ
10
Cho R là quan hệ từ A = {1,2,3,4} đến B = {u,v,w}:
R = {(1,u),(1,v),(2,w),(3,w),(4,u)}.
Khi đó R có thể biễu diễn như sau
11
Đây là ma trận cấp 4×3 biễu diễn cho quan hệ R
u v w
1 1 1 0
2 0 0 1
3 0 0 1
4 1 0 0
Định nghĩa. Cho R là quan hệ từ A = {a1, a2, , am} đến B = {b1,
b2, , bn}. Ma trận biểu diễn của R là ma trận cấp m × n MR =
[mij] xác định bởi
12
mij =
0 nếu (ai , bj) R
1 nếu (ai , bj) R
Ví dụ. Nếu R là quan hệ từ
A = {1, 2, 3} đến B = {1, 2} sao cho a R b
nếu a > b.
Khi đó ma trận biểu diễn của R là
1 2
1 0 0
2 1 0
3 1 1
Khi đó R gồm các cặp:
{(a1, b2), (a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3), (a3, b5)}
mij =
1 nếu (ai , bj) R
0 nếu (ai , bj) R
Ví dụ. Cho R là quan hệ từ A = {a1, a2, a3} đến
B = {b1, b2, b3, b4, b5} được biễu diễn bởi ma trận
13
10101
01101
00010
RM
b1 b2 b3 b4 b5
a1
a2
a3
Biểu diễn Quan hệ
Cho R là quan hệ trên tập A, khi đó MR là ma trận vuông.
R là phản xạ nếu tất cả các phần tử trên đường chéo của
MR đều bằng1: mii = 1 với mọi i
14
u v w
u 1 1 0
v 0 1 1
w 0 0 1
R là đối xứng nếu MR là đối xứng
15
u v w
u 1 0 1
v 0 0 1
w 1 1 0
mij = mji
R là phản xứng nếu MR thỏa:
16
u v w
u 1 0 1
v 0 0 0
w 0 1 1
mij = 0 hoặc mji = 0 nếu i j
1. Giới thiệu
2. Quan hệ tương đương
3. Biểu diễn số nguyên
4. Lớp tương đương
17
Ví dụ:
Cho S = {sinh viên của lớp}, gọi
R = {(a,b): a có cùng họ với b}
Hỏi
18
R phản xạ?
R đối xứng?
R bắc cầu?
Định nghĩa. Quan hệ R trên tập A được gọi là tương
đương nếu nó có tính chất phản xạ, đối xứng và bắc
cầu :
19
Ví dụ. Quan hệ R trên các chuỗi ký tự xác định bởi aRb
nếu a và b có cùng độ dài. Khi đó R là quan hệ tương
đương.
Ví dụ. Cho R là quan hệ trên R sao cho aRb nếu a – b
nguyên. Khi đó R là quan hệ tương đương
Ví dụ. Cho m là số nguyên dương và R quan hệ trên Z
sao cho aRb nếu a – b chia hết m, khi đó R là quan hệ
tương đương.
Rõ ràng quan hệ này có tính phản xạ và đối xứng.
Cho a, b, c sao cho a – b và b – c chia hết cho m, khi đó
a – c = a – b + b – c cũng chia hết cho m. Suy ra R có tính
chất bắc cầu.
Quan hệ này được gọi là đồng dư modulo m và chúng ta
viết
a b (mod m)
thay vì aRb
Cho a và b là hai số nguyên. A được gọi là ước của b hay
b chia hết cho nếu tồn tại số nguyên k sao a = kb
20
21
Định nghĩa. Cho R là quan hệ tương đương trên A và
phần tử a A . Lớp tương đương chứa a được ký hiệu
bởi [a]R hoặc [a] là tập
[a]R = {b A| b R a}
Ví dụ. Tìm các lớp tương đương modulo 8 chứa 0 và 1?
Giải. Lớp tương đương modulo 8 chứa 0 gồm tất cả các
số nguyên a chia hết cho 8. Do đó
[0]8 ={ , – 16, – 8, 0, 8, 16, }
Tương tự
[1]8 = {a | a chia 8 dư 1}
= { , – 15, – 7, 1, 9, 17, }
22
Chú ý. Trong ví dụ cuối, các lớp tương đương [0]8 và [1]8 là
rời nhau.
Tổng quát, chúng ta có
23
Định lý. Cho R là quan hệ tương đương trên tập A và a,
b A, Khi đó
(i) a R b nếu [a]R = [b]R
(ii) [a]R [b]R nếu [a]R [b]R =
Chú ý. Các lớp tương đương theo một quan hệ tương
đương trên A tạo nên một phân họach trên A, nghĩa là
chúng chia tập A thành các tập con rời nhau.
Định nghĩa. Quan hệ R trên tập A là quan hệ thứ tự (thứ
tự) nếu nó có tính chất phản xạ, phản xứng và bắc cầu.
Người ta thường ký hiệu quan hệ thứ tự bởi
Cặp (A, ) đựợc gọi là tập sắp thứ tự hay poset
Phản xạ: a a
Phản xứng: (a b) (b a) (a = b)
Bắc cầu: (a b) (b c) (a c)
Giả sử A1, A2,,An là n tập hợp. Quan hệ n-
ngôi xác định trên các tập A1, A2,An là một
tập con của tích Descartes A1xA2xA3x..An.
Hay R A1 x A2 x A3 x..x An.
Ví dụ : A=A1=A2=A3={1, 2, 3, 4} và quan hệ (a,
b, c) R A1x A2x A3 sao cho a<b<c thì
R={(1,2,3), (1,3,4),(2,3,4)} và (3,1,2)
Company Logo
1. Mệnh đề
2. Dạng mệnh đề
3. Qui tắc suy diễn
4. Vị từ, lượng từ
Là một khẳng định và có giá trị đúng hoặc sai
Câu hỏi, câu cảm thán, mệnh lệnh không là mệnh đề.
Ví dụ :
Mấy giờ rồi ?
Hôm nay là thứ 3
- Paris là thành phố của Mỹ
- n là số tự nhiên
- con nhà ai mà xinh thế!
- 3 là số nguyên tố.
- Bạn có khỏe không?
- luôn dương.
2 1x
Ký hiệu: người ta dùng các ký hiệu P, Q, R để chỉ mệnh đề.
Chân trị của mệnh đề:
Một mệnh đề chỉ có thể đúng hoặc sai, không thể đồng thời vừa
đúng vừa sai. Khi mệnh đề P đúng ta nói P có chân trị đúng, ngược
lại ta nói P có chân trị sai.
Chân trị đúng và chân trị sai sẽ được ký hiệu lần lượt là 1(hay Đ,T)
và 0(hay S,F)
Ví dụ:
- 2 không là số nguyên tố
- 2 là số nguyên tố
- Nếu 3>4 thì trời mưa
- An đang xem phim hay An đang học bài
- Hôm nay trời đẹp và 1 +1 =3
Mệnh đề sơ cấp : Là mệnh đề không thể xây
dựng từ các mệnh đề khác thông qua liên từ
hoặc trạng từ “không”
Mệnh đề phức hợp :là mệnh đề được xây
dựng từ các mệnh đề khác nhờ liên kết bằng
các liên từ (và, hay, khi và chỉ khi,) hoặc
trạng từ “không”
- Ví dụ : 2 không là số nguyên tố
2 là số nguyên tố (sơ cấp)
3>4 thì trời mưa
1. Phủ định
2. Hội
3. Giao
4. Kéo theo (suy ra)
5. Tương đương
Phép phủ định : phủ định của mệnh đề P được
ký hiệu là P hay (đọc là “không” P hay
“phủ định của” P.
Bảng chân trị :
P
P P
1 0
0 1
Ví dụ :
• 2 là số nguyên tố
Phủ định: 2 không là số nguyên tố
• - 1 >2
Phủ định : -1≤ 2
Phép hội (nối liền , giao): của hai mệnh đề P, Q
được kí hiệu bởi P Q (đọc là “P và Q”), là
mệnh đề được định bởi : P Q đúng khi và chỉ
khi P và Q đồng thời đúng.
p q pq
0 0 0
0 1 0
1 0 0
1 1 1
Ví dụ:
- 3>4 và 5<6 (S)
- 2 là số nguyên tố và là số chẵn (Đ)
- An đang hát và uống nước (S)
Phép tuyển (nối rời , hợp): của hai mệnh đề P, Q
được kí hiệu bởi P Q (đọc là “P hay Q”), là mệnh đề
được định bởi : P Q sai khi và chỉ khi P và Q đồng
thời sai.
P Q P Q
0 0 0
0 1 1
1 0 1
1 1 1
Ví dụ:
- p >4 hay p >5 (S)
- 2 là số nguyên tố hay là số chẵn (Đ)
Phép kéo theo: Mệnh đề P kéo theo Q của hai mệnh đề P và
Q, kí hiệu bởi P Q (đọc là “P kéo theo Q” hay “Nếu P thì
Q” hay “P là điều kiện đủ của Q” hay “Q là điều kiện cần của
P”) là mệnh đề được định bởi:
P Q sai khi và chỉ khi P đúng mà Q sai.
Bảng chân trị
P Q PQ
0 0 1
0 1 1
1 0 0
1 1 1
Ví dụ:
- Nếu 1 = 2 thì 3+5 =6 (Đ)
p >4 kéo theo 5>6 (Đ)
Phép kéo theo hai chiều: Mệnh đề P kéo theo Q và ngược
lại của hai mệnh đề P và Q, ký hiệu bởi P Q (đọc là
“P nếu và chỉ nếu Q” hay “P khi và chỉ khi Q” hay “P là
điều kiện cần và đủ của Q”), là mệnh đề xác định bởi:
P Q đúng khi và chỉ khi P và Q có cùng chân trị
Bảng chân trị :
P Q PQ
0 0 1
0 1 0
1 0 0
1 1 1
Ví dụ:
- 2=4 khi và chỉ khi 2+1=0
- 6 chia hết cho 3 khi và chi khi 6 chia hết cho 2
- London là thành phố nước Anh nếu và chỉ
nếu thành phố HCM là thủ đô của VN
- p >4 là điều kiện cần và đủ của 5 >6
T
T
F
T
Định nghĩa: là một biểu thức được cấu tạo từ:
- Các mệnh đề (các hằng mệnh đề)
- Các biến mệnh đề p, q, r, , tức là các biến lấy giá trị là
các mệnh đề nào đó
- Các phép toán , , , , và dấu đóng mở ngoặc ().
Ví dụ:
E(p,q) = (p q)
F(p,q,r) = (p q) (q r)
Bảng chân trị của dạng mệnh đề E(p,q,r): là bảng ghi tất cả
các trường hợp chân trị có thể xảy ra đối với dạng mệnh
đề E theo chân trị của các biến mệnh đề p, q, r. Nếu có n
biến, bảng này sẽ có 2n dòng, chưa kể dòng tiêu đề.
Ví dụ:
E(p,q,r) =(p q) r . Ta có bảng chân trị sau
p q r p q (p q) r
1 1 1 1 1
1 1 0 1 0
1 0 1 1 1
0 1 1 1 1
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
0 0 0 0 1
Hai dạng mệnh đề E và F được gọi là tương đương logic nếu chúng
có cùng bảng chân trị.
Ký hiệu E F.
Ví dụ (p q) p q
Dạng mệnh đề được gọi là hằng đúng nếu nó luôn lấy giá trị 1
Dạng mệnh đề gọi là hằng sai (hay mâu thuẫn ) nếu nó luôn lấy giá
trị 0.
Định lý: Hai dạng mệnh đề E và F tương đương với nhau khi và chỉ
khi EF là hằng đúng.
Các qui tắc thay thế
Qui tắc thay thế 1. Trong dạng mệnh đề E, nếu ta thay thế biểu
thức con F bởi một dạng mệnh đề tương đương logic thì dạng
mệnh đề thu được vẫn còn tương đương logic với E.
Qui tắc thay thế 2 Giả sử dạng mệnh đề E(p,q,r) là một hằng
đúng. Nếu ta thay thế những nơi p xuất hiện trong E bởi một
F(p’,q’,r’) thì dạng mệnh đề nhận được theo các biến
q,r,p’,q’,r’, vẫn còn là một hằng đúng.
1. Phủ định của phủ định
p p
2. Qui tắc De Morgan
(p q) p q
(p q) p q
3. Luật giao hoán p q q p
p q q p
4. Luật kết hợp (p q) r p (q r)
(p q) r p (q r)
5. Luật phân phối
p (q r) (p q) (p r)
p (q r) (p q) (p r)
6. Luật lũy đẳng p p p
p p p
7. Luật trung hòa p 0 p
p 1 p
8. Luật về phần tử bù
p p 0
p p 1
9. Luật thống trị p 0 0
p 1 1
10. Luật hấp thu p (p q) p
p (p q) p
11. Luật về phép kéo theo:
p q p q
q p
Qui tắc khẳng định (Modus Ponens)
Qui tắc này được thể hiện bằng hằng đúng:
p q
p
q
®
\
Hoặc dưới dạng sơ đồ :
Nếu A học tốt thì A thi điểm cao
Mà A học tốt
Suy ra : A thi điểm cao
Qui tắc tam đoạn luận :
Qui tắc này được thể hiện bằng hằng đúng:
Hoặc dưới dạng sơ đồ :
Nếu trời mưa thì đường ướt
Nếu đường ướt thì đường trơn
Suy ra nếu trời mưa thì đường trơn
Phương pháp phủ định
Qui tắc này được thể hiện bằng hằng đúng:
Hoặc dưới dạng sơ đồ :
Nếu A học tốt thì A thi đậu môn TT
A không thi đậu
Suy ra : A học không tốt
Qui tắc tam đoạn luận rời rạc
Qui tắc này được thể hiện bằng hằng đúng:
Hoặc dưới dạng sơ đồ :
p q
q
p
Ú
Ø
\
Ý nghĩa của qui tắc: nếu trong hai trường hợp có thể xảy ra, chúng
ta biết có một trường hợp sai thì chắc chắn trường hợp còn lại sẽ
đúng.
Chủ nhật, An thường lên thư viện hoặc về quê
Chủ nhật này, An không về quê
Suy ra: An lên thư viện
( ) ( )1 2 1 2... ... 0n np p p q p p p qÙ Ù Ù ® Û Ù Ù Ù ÙØ ®é ù é ùë û ë û
Qui tắc mâu thuẫn
Ta có tương đương logic
Để chứng minh vế trái g là một hằng đúng ta chứng minh nếu
thêm phủ định của q vào các tiền đề thì được một mâu thuẫn.
Vị từ là một khẳng định p(x,y,..), trong đó x,y...là các biến
thuộc tập hợp A, B,.. Cho trước sao cho:
- Bản thân p(x,y,..) không phải là mệnh đề
- Nếu thay x,y,.. Thành giá trị cụ thể thì p(x,y,..) là mệnh
đề.
Ví dụ :
- p(n) = “n +1 là số nguyên tố”
- q(x,y) = “x2 + y = 1”
- r(x,y,z) = “x2 + y
2 >z”
Cho trước các vị từ p(x), q(x) theo một biến x A.
Khi ấy
- Phủ định của vị từ p(x) kí hiệu là p(x) là vị từ
mà khi thay x bởi 1 phần tử cố định của A thì ta
được mệnh đề (p(a))
- Phép hội (tương ứng tuyển, kéo theo) của p(x)
và q(x) được ký hiệu bởi p(x)q(x) (tương ứng là
p(x)q(x), p(x)q(x)) là vị từ theo biến x mà khi
thay x bởi phần tử cố định a của A ta được mệnh đề
p(a)q(a) (tương ứng là p(a) q(a), p(a)q(a))
Khi xét một mệnh đề p(x) với x A. Ta có các trường hợp sau :
- TH1. Khi thay x bởi 1 phần tử a tùy ý A, ta có p(a) đúng.
- TH2. Với một số giá trị a A, ta có p(a) đúng.
- TH3. Khi thay x bởi 1 phần tử a tùy ý A, ta có p(a) sai.
Ví dụ. Cho vị từ p(x) với xR
- p(x) = “x2 +1 >0”
- p(x) = “x2 -2x+1=0”
- p(x) = “x2 -2x+3=0”
Định nghĩa : Cho p(x) là một vị từ theo một biến xác định
trên A. Ta định nghĩa các mệnh đề lượng từ hóa của p(x) như
sau:
- Mệnh đề “Với mọi x thuộc A, p(x) ”, kí hiệu bởi “x A,
p(x)”, là mệnh đề đúng khi và chỉ khi p(a) luôn đúng với mọi
giá trị a A.
- Mệnh đề “Tồn tại (ít nhất )hay có (ít nhất) một x thuộc A,
p(x))” kí hiệu bởi : “x A, p(x)” , là mệnh đề đúng khi và
chỉ khi có ít nhất một giá trị x = a0 nào đó sao cho mệnh đề
p(a0) đúng.
: được gọi là lượng từ phổ dụng
: được gọi là lượng từ tồn tại
Ví dụ. Các mệnh đề sau đúng hay sai
- “x R, x2 + 3x + 1 0” (S)
- “x R, x2 + 3x + 1 0” (Đ)
- “x R, x2 + 1 2x” (Đ)
- “x R, x2 + 1 < 0” (S)
Cho p(x, y) là một vị từ theo hai biến x, y xác định trên AB.
Ta định nghĩa các mệnh đề lượng từ hóa của p(x, y) như sau:
“x A,y B, p(x, y)” = “x A, (y B, p(x, y))”
“x A, y B, p(x, y)” = “x A, (y B, p(x, y))”
“x A, y B, p(x, y)” = “x A, (y B, p(x, y))”
“x A, y B, p(x, y)” = “x A, (y B, p(x, y))”
Ví dụ.
- Mệnh đề “x R, y R, x + 2y < 1” đúng hay sai?
Mệnh đề sai vì tồn tại x0 = 0, y0 = 1 R mà x0 + 2y0 1.
- Mệnh đề “x R, y R, x + 2y < 1” đúng hay sai?
Mệnh đề đúng vì với mỗi x = a R, tồn tại ya R như
ya = –a/2, sao cho a + 2ya < 1.
Mệnh đề “x R, y R, x + 2y < 1” đúng hay sai?
Mệnh đề đúng vì với mỗi x = a R, tồn tại ya R như
ya = –a/2, sao cho a + 2ya < 1.
Mệnh đề “x R, y R, x + 2y < 1” đúng hay sai?
Mệnh đề đúng vì tồn tại x0 = 0, y0 = 0 R chẳng hạn thỏa
x0 + 2y0 < 1.
Định lý. Cho p(x, y) là một vị từ theo hai biến x, y xác định trên
AB. Khi đó:
1) “x A, y B, p(x, y)” “y B, x A, p(x, y)”
2) “x A, y B, p(x, y)” “y B, x A, p(x, y)”
3) “x A, y B, p(x, y)” “y B, x A, p(x, y)”
Phủ định của mệnh đề lượng từ hóa vị từ p(x,y,..) có được bằng các
thay thành , thay thành và vị từ p(x,y,..) thành p(x,y,..)
Với vị từ theo 1 biến ta có :
( ( , ,x A p x x A p x
( ( , ,x A p x x A p x
( ( , , , , , ,x A y B p x y x A y B p x y
( ( , , , , , ,x A y B p x y x A y B p x y
( ( , , , , , ,x A y B p x y x A y B p x y
( ( , , , , , ,x A y B p x y x A y B p x y
“x A, 2x + 1 0”
“ > 0, > 0, x R, x – a < f(x) – f(a) < ”.
Trả lời :
“x A, 2x + 1 > 0”
“ > 0, > 0, x R, x – a < (f(x) – f(a) )”.
Nếu một mệnh đề đúng có dạng lượng từ hóa trong đó
một biến x A bị buộc bởi lượng từ phổ dụng , khi ấy
nếu thay thế x bởi a A ta sẽ được một mệnh đề đúng
Ví dụ:
“Mọi người đều chết”
“Socrate là người”
Vậy “Socrate cũng chết”
, ( )
( )
x A p x
a A
p a
1. Các nguyên lý
2. Giải tích tổ hợp
3. Hoán vị lặp, tổ hợp lặp
1. Nguyên lý cộng :
Giả sử để làm công việc A có 2 phương pháp
- Phương pháp 1 có n cách làm
- Phương pháp 2 có m cách làm
Khi đó số cách làm công việc A là n+m
Ví dụ : Danh bạ điện thoại có 3 số ở sim 1. 5 số ở sim 2.
Vậy có bao nhiêu cách để gọi một số bất kỳ từ danh bạ
trên ?
Cho A1, A2,.., An là các tập hữu hạn, không giao
nhau từng đôi một. Khi đó :
Company Logo
n
i
i
n
i
AN
i
N UA
11
)(
2. Nguyên lý nhân
Giả sử để làm công việc A cần thực hiện 2 bước
- Bước 1 có n cách làm
- Bước 2 có m cách làm
Khi đó số cách làm công việc A là n.m
Ví dụ:
A B C
Có 3.2 =6 con đường đi từ A đến C
Ví dụ: Cho tập X ={1,2,3,4,5,0}
Hỏi có bao nhiêu số tự nhiên có 3 chữ số khác nhau mà chia
hết cho 2
Giải. Gọi số có 3 chữ số là
abc
TH1 . c=0. Khi đó
c có 1 cách chọn
a có 5 cách chọn ( aX\{0} )
b có 4 cách chọn ( bX\{a, 0} )
TH1 có 1.4.5 =20
TH2 . c≠0. Khi đó
c có 2 cách chọn
a có 4 cách chọn ( aX\{c, 0} )
b có 4 cách chọn ( bX\{a, c} )
TH2 có 2.4.4 =32
Vậy có 20+32 =52
Một hệ thống yêu cầu đăng ký password
dạng như sau :
Từ 4 – 8 chữ cái
Phân biệt chữ hoa và thường
Hỏi ?
Có bao nhiêu passwords có thể ?
Sử dụng nguyên lý gì ?
Nếu password có 4 ký tự thì tỷ lệ phần trăm là bao
nhiêu ?
87654 PPPPPP
Gọi Pi là tập hợp các password gồm i chữ cái. Và P là tập hợp
tất cả các passwords có thể
Ta có Pi rời nhau :
8
4
||||
i
iPP
Với mỗi Pi ta có 52 chữ cái (26 hoa và 26 thường). Ta có : 52
i
Tập hợp tất cả passwords có thể : 524 + 525 + 526 + 527 + 528
3. Nguyên lý chuồng bồ câu (Derichlet)
Giả sử có n chim bồ câu ở trong k chuồng đặt vào k hộp.
Khi đó tồn tại ít nhất một chuồng chứa từ bồ câu trở lên,
trong đó là số nguyên nhỏ nhất lớn hơn hay bằng n/k.
/n k
/n k
Có 20 chim bồ câu ở trong 7 cái chuồng. Khi đó sẽ có ít
nhất 1 chuồng có 3 con bồ câu trở lên
Trong 1 nhóm có 367 người thì ít nhất có 2 người sinh
cùng ngày
4. Nguyên lý bù trừ.
Cho A và B là hai tập hữu hạn. Khi đó
|A B|= |A|+|B| - |A B|
A B B A
Định nghĩa : Cho A1, A2,.., An là các tập hữu
hạn. Khi đó :
n
i
i
n
k
nji
ji
nji
ji
n
i
i
n
i
i
AN
AAANAANANAN
1
1
1111
()1(
...)()()()(
A B
A C BC
A B C
A B
C
|A B C|=?
Ví dụ. Trong một lớp ngoại ngữ Anh Pháp. Có 24 HS học
Tiếng Pháp, 26 học sinh học Tiếng Anh. 15 học sinh học
Tiếng Anh và Tiếng Pháp. Hỏi lớp có bao nhiêu người
Gọi A là những học sinh học Tiếng Pháp
B là những học sinh học Tiếng Anh
Khi đó. Số học sinh của lớp là |A B |. Theo nguyên lý
bù trừ ta có |A B|= |A|+|B| - |A B|=24+26-15=35
1. Hoán vị : Cho tập hợp A gồm n phần tử. Mỗi cách sắp đặt có thứ
tự n phần tử của A được gọi là một hoán vị của n phần tử. Số
các hoán vị của n phần tử ký hiệu là Pn
Pn = n! = n.(n-1).(n-2)1
Quy ước 0! =1
Phép đếm
Ví dụ. Cho A ={a,b,c}. Khi đó A có các hoán vị sau
abc, acb, bac, bca, cab, cba
Nếu A là tập hợp n phần tử thì số song ánh từ A vào A là
n!
Cho X ={1,2,3,4,5}. Hỏi có bao nhiêu số tự nhiên gồm
5 chữ số khác nhau được tạo từ tập X?
2. Chỉnh hợp : Cho A là tập hợp gồm n phần tử. Mỗi bộ gồm k
phần tử (1 k n) sắp thứ tự của tập hợp A được gọi là một
chỉnh hợp chập k của n phần tử.
Số các chỉnh hợp chập k của n ký hiệu là
- Công thức
!
!
k
n
n
A
n k
k
nA
Ví dụ : Cho X ={abc}. Khi đó X có các chỉnh hợp chập 2
của 3 là: ab, ba, ac, ca, bc, cb.
Ví dụ. Có bao nhiêu số tự nhiên gồm 3 chữ số được tạo
thành từ 1,2,3,4,5,6.
Kết quả: 3
6A
3.Tổ hợp : Cho tập hợp A gồm n phần tử. Mỗi tập con gồm k
phần tử của A được gọi là một tổ hợp chập k của n phần tử.
Số tổ hợp chập k của n phần tử được kí hiệu là hay
k
nC
k
n
!
! !
k
n
n
C
k n k
Tính chất : n k k
n nC C
1
1
k k k
n n nC C C
Ví dụ : Cho X = {1,2,3,4}. Tổ hợp chập 3 của 4 phần tử của
X là {1,2,3}, {1,2,4}, {1,3,4} , {2,3,4}
Một lớp có 30 học sinh. Hỏi có bao nhiêu cách chọn 10 bạn
- Số cách chọn là tổ hợp chập 10 của 30.
10
30C
1. Hoán vị lặp : Cho n đối tượng trong đó có ni đối tượng
loại i giống hệt nhau (i =1,2,,k ; n1+ n2,+ nk= n).
Mỗi cách sắp xếp có thứ tự n đối tượng đã cho gọi là một
hoán vị lặp của n.
Số hoán vị của n đối tượng, trong đó có
n1 đối tượng giống nhau thuộc loại 1,
n2 đối tượng giống nhau thuộc loại 2,,
nk đối tượng giống nhau thuộc loại k, là
1 2
!
! !... !k
n
n n n
Ví dụ : Có bao nhiêu chuỗi kí tự khác nhau bằng cách sắp xếp các
chữ cái của từ SUCCESS?
Giải : Trong từ SUCCESS có 3 chữ S, 1 chữ U, 2 chữ C và 1 chữ
E. Do đó số chuỗi có được là
.
7!
420
3!1!2!1!
2. Tổ hợp lặp : Mỗi cách chọn ra k vật từ n loại vật khác
nhau (trong đó mỗi loại vật có thể được chọn lại nhiều
lần) được gọi là tổ hợp lặp chập k của n
Số các tổ hợp lặp chập k của n được ký hiệu là
k
nK
1
k k
n n kK C
Ví dụ. Có 3 loại nón A, B, C. An mua 2 cái nón. Hỏi An có bao
nhiêu cách chọn.
Ta có mỗi cách chọn là mỗi tổ hợp lặp chập 2 của 3. Cụ thể
AA, AB, AC, BB, BC, CC
2 2 2
3 3 2 1 4 6K C C
Nội dung
1. Đại Số Bool
2. Hàm Bool
3. Biểu đồ Karnaugh
4. Mạch logic
Xét mạch điện như hình vẽ
Tùy theo cách trạng thái cầu dao A, B, C mà ta sẽ có dòng
điện đi qua MN. Như vậy ta sẽ có bảng giá trị sau
Mở đầu
A B C MN
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
Một đại số Bool (A,,) là một tập hợp A với hai phép
toán , , với hai ánh xạ:
5
: AA A
(x,y) xy
và : AA A
(x,y)xy
thỏa 5 tính chất sau:
Tính giao hoán: x, y A
xy = yx;
xy = yx;
6
Tính kết hợp: x, y, z A
(xy) z = x(y z);
(xy) z = x (y z).
Tính phân phối : x, y, z A
x(y z) = (xy) (xz);
x (y z) = (xy) (xz).
Có các phần tử trung hòa 1 và 0: x A
x 1 = 1 x = x;
x 0 = 0 x = x.
7
Mọi phần tử đều có phần tử bù: x A,
A,
x = x = 0;
x = x = 1.
x
x
x
x
x
8
Xét F là tập hợp tất cả các dạng mệnh đề theo n biến p1,
p2,,pn với hai phép toán hội , phép toán tuyển , trong đó
ta đồng nhất các dạng mệnh đề tương đương
E
. Khi đó F là một đại số Bool với phần tử 1 là hằng đúng
1, phần tử 0 là hằng sai 0, phần tử bù của dạng mệnh đề
E là dạng mệnh đề bù
9
Xét tập hợp B = {0, 1}. Trên B ta định nghĩa hai
phép toán , như sau:
Khi đó, B trở thành một đại số Bool
0 1
0 0 0
1 0 1
0 1
0 0 1
1 1 1
10
Hàm Bool n biến là ánh xạ
f : Bn B , trong đó B = {0, 1}.
Hàm Bool n biến là một hàm số có dạng :
f = f(x1,x2,,xn), trong đó mỗi biến trong x1, x2,, xn chỉ nhận
hai giá trị 0, 1 và f nhận giá trị trong B = {0, 1}.
Ký hiệu Fn để chỉ tập các hàm Bool n biến.
Ví dụ. Dạng mệnh đề E = E(p1,p2,,pn) theo n biến p1,
p2,, pn là một hàm Bool n biến.
11
Xét hàm Bool n biến f(x1,x2,,xn)
Vì mỗi biến xi chỉ nhận hai giá trị 0, 1 nên chỉ có 2
n
trường hợp của bộ biến (x1,x2,,xn).
Do đó, để mô tả f, ta có thể lập bảng gồm 2n hàng ghi tất
cả các giá trị của f tùy theo 2n trường hợp của biến. Ta gọi
đây là bảng chân trị của f
12
Xét kết qủa f trong việc thông qua một quyết định dựa
vào 3 phiếu bầu x, y, z
Mỗi phiếu chỉ lấy một trong hai giá trị: 1 (tán thành) hoặc
0 (bác bỏ).
Kết qủa f là 1 (thông qua quyết định) nếu được đa số
phiếu tán thành, là 0 (không thông qua quyết định) nếu đa
số phiếu bác bỏ.
Khi đó f là hàm Bool theo 3 biến x, y, z có bảng chân trị như
sau:
x y z f
1 1 1 1
1 1 0 1
1 0 1 1
1 0 0 0
0 1 1 1
0 1 0 0
0 0 1 0
0 0 0 0
14
Các phép toán trên Fn được định nghĩa như sau:
Phép cộng Bool :
Với f, g Fn ta định nghĩa tổng Bool của f và g:
f g = f + g – fg
15
Phép nhân Bool :
Với f, g Fn ta định nghĩa tích Bool của f và g
f g = fg
x=(x1,x2,,xn)B
n, (f g)(x) = f(x)g(x)
Ta thường viết fg thay cho f g
16
Phép lấy hàm bù:
Với f Fn ta định nghĩa hàm bù của f như sau:
1f f
Xét tập hợp các hàm Bool của n biến Fn theo n biến x1,
x2,,xn
Mỗi hàm bool xi hay được gọi là từ đơn.
Đơn thức là tích khác không của một số hữu hạn từ
đơn.
Từ tối tiểu là tích khác không của đúng n từ đơn.
Công thức đa thức là công thức biểu diễn hàm Bool
thành tổng của các đơn thức.
Dạng nối rời chính tắc là công thức biểu diễn hàm Bool
thành tổng của các từ tối tiểu.
ix
ttzzyyxx ,,,,,,,
tyxtzyx ;
tzyx
zyzxyf
là các từ đơn
là các đơn thức
là một đơn thức tối tiểu
Đơn giản hơn
Cho hai công thức đa thức của một hàm Bool :
f = m1 m2 . mk (F)
f =M1 M2 Ml (G)
Ta nói rằng công thức F đơn giản hơn công thức G nếu
tồn tại đơn ánh h: {1,2,..,k} → { 1,2,, l} sao cho với mọi
i {1,2,..,k} thì số từ đơn của mi không nhiều hơn số từ
đơn của Mh(i)
19
Đơn giản như nhau
Nếu F đơn giản hơn G và G đơn giản hơn F thì ta
nói F và G đơn giản như nhau
Công thức đa thức tối tiểu:
Công thức F của hàm Bool f được gọi là tối tiểu
nếu với bất kỳ công thức G của f mà đơn giản
hơn F thì F và G đơn giản như nhau
20
Phương pháp biểu đồ Karnaugh
Xét f là một hàm Bool theo n biến x1,x2,,xn với n = 3 hoặc 4.
f là hàm Bool theo 3 biến x, y, z. Khi đó bảng chân trị của f
gồm 8 hàng. Thay cho bảng chân trị của f ta vẽ một bảng chữ
nhật gồm 8 ô, tương ứng với 8 hàng của bảng chân trị, được
đánh dấu như sau:
Trường hợp n = 3:
Quy ước
Các ô tại đó f bằng 1 sẽ được đánh dấu (tô đậm
hoặc gạch chéo). Tập các ô được đánh dấu được gọi
là biểu đồ Karnaugh của f, ký hiệu là kar(f).
Khi một ô nằm trong dãy được đánh dấu bởi x thì
tại đó x =1, bởi thì tại đó x =0, tương tự cho y, z. x
f là hàm Bool theo 4 biến x, y, z, t. Khi đó bảng chân trị của
f gồm 16 hàng. Thay cho bảng chân trị của f ta vẽ một bảng
chữ nhật gồm 16 ô, tương ứng với 16 hàng của bảng chân
trị, được đánh dấu như sau:
Trường hợp n = 4:
Với qui ước:
Các ô tại đó f bằng 1 sẽ được đánh dấu (tô đậm hoặc
gạch chéo). Tập các ô được đánh dấu được gọi là biểu đồ
karnaugh của f, ký hiệu là kar(f).
Trong cả hai trường hợp, hai ô được gọi là kề nhau (theo
nghĩa rộng), nếu chúng là hai ô liền nhau hoặc chúng là ô
đầu, ô cuối của cùng một hàng (cột) nào đó. Nhận xét rằng,
do cách đánh dấu như trên, hai ô kề nhau chỉ lệch nhau ở
một biến duy nhất.
Khi một ô nằm trong dãy được đánh dấu bởi x thì tại
đó x =1, bởi thì tại đó x =0, và tương tự cho y, z, t. x
Định lý
Cho f, g là các hàm Bool theo n biến x1,x2,,xn.
Khi đó:
a) kar(fg) = kar(f)kar(g).
b) kar(fg) = kar(f)kar(g).
c) kar(f) gồm đúng một ô khi và chỉ khi f là một từ
tối tiểu
Tế bào là hình chữ nhật (theo nghĩa rộng) gồm 2n-k ô
Tế bào
Nếu T là một tế bào thì T là biểu đồ karnaugh của một
đơn thức duy nhất m, cách xác định m như sau: lần lượt
chiếu T lên các cạnh, nếu toàn bộ hình chiếu nằm trọn trong
một từ đơn nào thì từ đơn đó mới xuất hiện trong m.
Ví dụ : Xét các hàm Bool theo 4 biến x, y, z, t.
Ví dụ :
Xét các hàm Bool theo 4 biến x, y, z, t.
Là biểu đồ Karnaugh của đơn thức nào?
Ví dụ
Xét các hàm Bool theo 4 biến x, y, z, t.
Là biểu đồ Karnaugh của đơn thức nào?
Ví dụ :
Xét các hàm Bool theo 4 biến x, y, z, t.
Là biểu đồ Karnaugh của đơn thức nào?
Tế bào sau:
Ví dụ:
Xét các hàm Bool theo 4 biến x, y, z, t.
Tế bào sau:
Là biểu đồ Karnaugh của đơn thức nào?
Cho hàm Bool f. Ta nói T là một tế bào lớn của kar(f) nếu T
thoả hai tính chất sau:
Tế bào lớn.
a) T là một tế bào và T kar(f).
b) Không tồn tại tế bào T’ nào thỏa T’ T và
T T’ kar(f).
Hay tế bào lớn là một tế bào mà không bị phủ bởi bất kỳ
một tế bào nào khác
Ví dụ : Xét hàm Bool f theo 4 biến x, y, z, t có biểu đồ karnaugh
như sau
Kar(f) có 6 tế bào lớn như sau:
Thuật toán : Biểu đồ Karnaugh
1. Vẽ biểu đồ karnaugh của f.
2. Xác định tất cả các tế bào lớn của kar(f).
3. Xác định các tế bào lớn m nhất thiết phải chọn.
Ta nhất thiết phải chọn tế bào lớn T khi tồn tại một ô
của kar(f) mà ô này chỉ nằm trong tế bào lớn T và không
nằm trong bất kỳ tế bào lớn nào khác.
Bước 4: Xác định các phủ tối tiểu gồm các tế bào lớn
Nếu các tế bào lớn chọn được ở bước 3 đã phủ
được kar(f) thì ta có duy nhất một phủ tối tiểu gồm các tế
bào lớn của kar(f).
Nếu các tế bào lớn chọn được ở bước 3 chưa phủ
được kar(f) thì:
Xét một ô chưa bị phủ, sẽ có ít nhất hai tế bào lớn
chứa ô này, ta chọn một trong các tế bào lớn này. Cứ
tiếp tục như thế ta sẽ tìm được tất cả các phủ gồm các tế
bào lớn của kar(f).
Loại bỏ các phủ không tối tiểu, ta tìm được tất cả các
phủ tối tiểu gồm các tế bào lớn của kar(f).
Biểu đồ Karnaugh
Bước 5: Xác định các công thức đa thức tối tiểu của f.
Từ các phủ tối tiểu gồm các tế bào lớn của kar(f)
tìm được ở bước 4 ta xác định được các công thức đa
thức tương ứng của f
Loại bỏ các công thức đa thức mà có một công thức
đa thức nào đó thực sự đơn giản hơn chúng.
Các công thức đa thức còn lại chính là các
công thức đa thức tối tiểu của f.
Biểu đồ Karnaugh
Cho bảng chân trị của hàm Bool.
Tìm công thức đa thức tối tiểu
xxxx
z
z
y y y y
Các tế bào lớn
xy
yz
xz
xz yz xy f
Cho hàm Bool
Hãy tìm công thức đa thức tối tiểu
zxy.y x yx zf
Tế bào lớn :
zx yx zy.
Tế bào lớn :
zx yx zy.
Chỉ cần 2 tế bào và là phủ được hàm Bool zx zy.
zxy.y x yx zf
Tìm tất cả các công thức đa thức tối tiểu của hàm Bool:
( , , , ) ( )f x y z t xyzt xy xz yz xy z t
xyzt xy xz yz xyz xyt
( , , , )f x y z t xy xzx yyzt z xyz xyt
( , , , ) xf x y z t xyzt xz yz z x ty xy y
( , , , )f x y z t xyzt xy yz x zz y xytx
( , , , )f x y z t xyzt x yzy xz xyz xyt
( , , , )f x y z t xyzt xy xz yz xyz xyt
( , , , )f x y z t xyzt xy xz yz xyz xyt
Bước 1:Vẽ kar(f):
( , , , )f x y z t xyzt xy xz yz xyz xyt
Bước 2: Kar(f) có các tế bào lớn như sau:
x
yz
( , , , )f x y z t xyzt xy xz yz xyz xyt
1 2 3
4 5 6
7 8
9 10
1 2
4 5
7 8
9 10
Bước 3: Xác định các tế bào lớn nhất thiết phải chọn:
x
2 3
5 6
yz
- Ô 1 nằm trong một tế bào lớn duy nhất x. Ta chọn x.
- Ô 3 nằm trong một tế bào lớn duy nhất yz. Ta chọn yz.
( , , , )f x y z t xyzt xy xz yz xyz xyt
1 2 3
4 5 6
7 8
9 10
Bước 4: Xác định các phủ tối tiểu gồm các tế bào lớn
x
yz
1 2 3
4 5 6
7 8
9 10
1 2 3
4 5 6
7 8
9 10
Ta được duy nhất một phủ tối tiểu
gồm các tế bào lớn của kar(f):
x ν yz.
Bước 5: Xác định các công thức đa thức tối tiểu của f.
Ứng với phủ tối tiểu gồm các tế bào lớn tìm được ở
bước 4 ta tìm được duy nhất một công thức đa thức
tối tiểu của f:
x yz
( , , , )f x y z t xyzt xy xz yz xyz xyt
1 2
3 4 5
6 7 8 9
B1: Vẽ Kar(f)
f yzt yzt yzt xyzt xzt
1 2
3 4 5
6 7 8 9
B2: Xác định tế bào lớn
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
f yzt yzt yzt xyzt xzt
1 2
3 4 5
6 7 8 9
B3: Xác định các tế bào lớn nhất thiết phải chọn
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
f yzt yzt yzt xyzt xzt
Bước 3: Xác định các tế bào lớn nhất thiết phải chọn
Ô 6 nằm trong một tế bào lớn duy nhất . Ta
chọn
Ô 1 nằm trong một tế bào lớn duy nhất . Ta
chọn
Ô 4 nằm trong một tế bào lớn duy nhất xzt . Ta
chọn xzt
zt
zt
xt
xt
f yzt yzt yzt xyzt xzt
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
f yzt yzt yzt xyzt xzt
zt xt xzt
B4: Xác định các phủ tối tiểu gồm các tế bào lớn
1 2
3 4 5
6 7 8 9
B4: Xác định các phủ tối tiểu gồm các tế bào lớn
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
Còn lại ô 5 chưa bị phủ
Ô 5 nằm trong 2 tế bào lớn: 2 cách chọn
f yzt yzt yzt xyzt xzt
zt xt xzt
1 2
3 4 5
6 7 8 9
B4: Xác định các phủ tối tiểu gồm các tế bào lớn
1 2
3 4 5
6 7 8 9
Còn lại ô 5 chưa bị phủ
Ô 5 nằm trong 2 tế bào lớn: 2 cách chọn
f yzt yzt yzt xyzt xzt
zt xt xzt xyz
1 2
3 4 5
6 7 8 9
B4: Xác định các phủ tối tiểu gồm các tế bào lớn
1 2
3 4 5
6 7 8 9
Còn lại ô 5 chưa bị phủ
Ô 5 nằm trong 2 tế bào lớn: 2 cách chọn
f yzt yzt yzt xyzt xzt
zt xt xzt yzt
Bước 5: Xác định các công thức đa thức tối tiểu của f
f yzt yzt yzt xyzt xzt
zt xt xzt xyz
zt xt xzt yzt
Haõy xaùc ñònh caùc coâng thöùc ña thöùc toái tieåu
cuûa haøm Bool:
)()( yxytztzxtyzxf
Bieåu ñoà Karnaugh:
Caùc teá baøo lôùn:
Caùc teá baøo lôùn baét buoäc phaûi choïn laø
Coøn laïi oâ (1,4) coù theå naèm trong 2 teá baøo lôùn
tyxtzxztzyxz ,,,,
tzxztxz ,,
tyxzy ,
Do ñoù coù 2 coâng thöùc ña thöùc töông öùng vôùi
phuû toái tieåu:
Trong ñoù chæ coù coâng thöùc thöù hai laø toái tieåu
zytzxztxzf
tyxtzxztxzf
1. Khái niệm cơ bản
2. Đồ thị có hướng & vô hướng
3. Đồ thị đặc biệt
4. Chu trình & Đường đi
5. Các bài toán liên quan
3
Định nghĩa 1: Đồ thị vô hướng G = (V, E) gồm:
i) V là tập hợp khác rỗng mà các phần tử của nó gọi
là đỉnh (vertex) của G.
ii) E là đa tập hợp gồm các cặp không sắp thứ tự của
hai đỉnh. Mỗi phần tử của E được gọi là một cạnh
(edge) của G. Ký hiệu uv.
Nếu uv là một cung (cạnh) thì ta nói:
Đỉnh u và v kề nhau.
Đỉnh u gọi là đỉnh đầu (gốc), đỉnh v là đỉnh cuối (ngọn) của cung
uv. Đỉnh v là đỉnh sau của đỉnh u.
Hai cung có cùng gốc và ngọn gọi là cung song song.
Cung có điểm gốc và ngọn trùng nhau gọi là khuyên.
5
6
b
d a
k
e
h
g
c
a
b
c
d
b
c
a
d
Định nghĩa 2. Đồ thị vô hướng không có cạnh song
song và không có khuyên gọi là đơn đồ thị vô
hướng.
Định nghĩa 3. Đồ thị vô hướng cho phép có cạnh
song song nhưng không có khuyên gọi là đa đồ thị
vô hướng.
Định nghĩa 4. Đồ thị vô hướng cho phép có cạnh
song song và có khuyên gọi là giả đồ thị
7
8
Đa đồ thị có hướng G =(V,E) gồm:
i) V là tập hợp khác rỗng mà các phần tử của nó gọi là
đỉnh của G.
ii) E là đa tập hợp gồm các cặp có sắp thứ tự của hai đỉnh.
Mỗi phần tử của E được gọi là một cung (cạnh) của G. Ký
hiệu uv.
Ta nói cung uv đi từ u đến v, cung uv kề với u,v
9
b
c
a
d
a
b
c d
Định nghĩa 6. Đa đồ thị có hướng không chứa các cạnh song
song gọi là đồ thị có hướng
10
Cho hai đồ thị G1=(V1,E1) và G2=(V2,E2). Ta nói
G2 là đồ thị con của G1 nếu V2 V1 và E2 E1.
Trong trường hợp V1=V2 thì G2 gọi là con bao
trùm của G1.
G1, G2, G3 và G4 là các đồ thị con của G, trong đó G2 và G4 là đồ
thị con bao trùm của G, còn G5 không phải là đồ thị con của G.
Đơn đồ thị G’=(V,E’) được gọi là đồ thị bù của
đơn đồ thị G=(V,E) nếu G và G’ không có cạnh
chung nào (E E’=) và G G’là đồ thị đầy
đủ.
Cho đồ thị vô hướng G = (V,E). Bậc của đỉnh v, ký hiệu
deg(v), là số cạnh kề với v, trong đó một khuyên tại một
đỉnh được đếm hai lần cho bậc của đỉnh ấy.
15
Bậc của đỉnh
16
c
a
b
d
Bậc đỉnh a: deg(a) = 2
Bậc đỉnh b: deg(b) = 5
Bậc đỉnh c: deg(c) = 3
Bậc đỉnh d: deg(d) = 2
1) deg-(v):= số cung có đỉnh cuối là v, gọi là bậc vào của v.
2) deg +(v):= số cung có đỉnh đầu là v,gọi là bậc ra của v
3) deg(v):= deg- (v) + deg+(v)
Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 gọi là đỉnh treo
17
Cho đồ thị có hướng G = (V, E), vV
18
a b
d
c
f
e
Bậc của các đỉnh?
19
a b
d
c
f
e
Bậc đỉnh a:
Bậc đỉnh b:
Bậc đỉnh c:
Bậc đỉnh d:
Bậc đỉnh e:
Bậc đỉnh f:
deg-(a)= 1 ; deg+(a)=1
deg-(b)= 1 ; deg+(b)=3
deg-(c)= 1 ; deg+(c)=2
deg-(d)= 0 ; deg+(d)=0
deg-(e)= 1 ; deg+(e)=0
deg-(f)= 2 ; deg+(f)=0
Cho đồ thị G = (V,E), m là số cạnh (cung)
2 deg( )
v V
m v
20
Định lí
1)
2) Nếu G có hướng thì:
deg ( ) deg ( )m v v
v V v V
3) Số đỉnh bậc lẻ của đồ thị là số chẵn
Ta sử dụng ma trận kề.
Cho G = (V,E) với V={1,2,,n}.
Ma trận kề của G là ma trận A = (aij)n xác định như sau:
aij = số cạnh (số cung) đi từ đỉnh i đến đỉnh j
21
Biểu diễn ma trận của đồ thị.
22
c
a
b
d
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0
b a c d
a
b
c
d
Tìm ma trận kề
23
a b
d c
f
e
0 2 1 0 0 0
2 0 1 0 1 1
1 1 0 0 0 1
0 0 0 0 0 0
0 1 0 0 1 0
0 1 1 0 0 0
a b c d e f
a
b
c
d
e
f
Tìm ma trận kề
Với mỗi đỉnh của đồ thị ta xây dựng một danh sách
móc nối chứa các đỉnh kề với đỉnh này: Danh sách
này được gọi là danh sách kề.
Một đồ thị được biểu diễn bằng một mảng các danh
sách kề
a
b
e d
c
Cho hai đơn đồ thị G = (V,E) và G’= (V’,E’). Ta nói rằng G đẳng
cấu G’, ký hiệu G G’, nếu tồn tại song ánh f :V→ V’sao cho:
uv là cạnh của G f(u)f(v) là cạnh của G’
26
Đẳng cấu
27
Nếu G và G’ là các đơn đồ thị vô hướng đẳng cấu qua
ánh xạ f thì chúng có:
Cùng số đỉnh
Cùng số cạnh
Cùng số đỉnh với bậc cho sẵn (vd: số đỉnh bậc 2 của
G và G’ bằng nhau)
deg v = deg f(v)
Đẳng cấu
28
Đẳng cấu
a
b
c
d e
a
b
c
d
e
deg(e) = 1 Không có đỉnh bậc 1
Không đẳng cấu
29
Ví dụ
a
b
c d
e
f
1
2
3
6
5 4
30
Đẳng cấu
a
b
4
d
e
1
2
3
c
5
31
Không đẳng cấu
32
a
b
c
d
e
Đồ thị đầy đủ
Đồ thị phẳng
Đồ thị thành phần, đồ thị con
Đồ thị đầy đủ n đỉnh, ký hiệu là Kn, là đơn đồ
thị mà hai đỉnh phân biệt bất kỳ của nó luôn
liền kề. Kn có cạnh và mỗi đỉnh của Kn
có bậc là n1.
2
)1( nn
Đơn đồ thị n đỉnh v1, v2, ..., vn (n3) và n cạnh
(v1,v2), (v2,v3), ..., (vn-1,vn), (vn,v1) được gọi là
đồ thị vòng, ký hiệu là Cn. Như vậy, mỗi đỉnh
của Cn có bậc là 2.
Từ đồ thị vòng Cn, thêm vào đỉnh vn+1 và các
cạnh (vn+1,v1), (vn+1,v2), ..., (vn+1,vn), ta nhận
được đơn đồ thị gọi là đồ thị bánh xe, ký hiệu
là Wn. Như vậy, đồ thị Wn có n+1 đỉnh, 2n
cạnh, một đỉnh bậc n và n đỉnh bậc 3.
Đơn đồ thị 2n đỉnh, tương ứng với 2n xâu nhị phân
độ dài n và hai đỉnh kề nhau khi và chỉ khi 2 xâu nhị
phân tương ứng với hai đỉnh này chỉ khác nhau
đúng một bit được gọi là đồ thị lập phương, ký hiệu
là Qn.
Mỗi đỉnh của Qn có bậc là n và số cạnh của Qn là n.2
n-
1 (từ công thức 2|E| = ).
Vv
v)deg(
Đơn đồ thị G=(V,E) sao cho V=V1V2,
V1V2=, V1, V2 và mỗi cạnh của G
được nối một đỉnh trong V1 và một đỉnh trong
V2 được gọi là đồ thị phân đôi.
Nếu đồ thị phân đôi G=(V1V2,E) sao cho với
mọi v1V1, v2V2, (v1,v2)E thì G được gọi là
đồ thị phân đôi đầy đủ. Nếu |V1|=m, |V2|=n thì
đồ thị phân đôi đầy đủ G ký hiệu là Km,n. Như
vậy Km,n có m.n cạnh, các đỉnh của V1 có bậc n
và các đỉnh của V2 có bậc m.
Bài toán : 3 nhà có 3 cái giếng
Một đồ thị được gọi là phẳng nếu nó có thể vẽ
được trên một mặt phẳng mà không có các
cạnh nào cắt nhau
Định lý : Trong một đồ thị phẳng liên thông
tuỳ ý, luôn tồn tại ít nhất một đỉnh có bậc
không vượt quá 5.
Định nghĩa. Cho G = (V,E). Trên V ta định nghĩa quan hệ tương
đương như sau:
u~v u = v hay có một đường đi từ u đến v
a) Nếu u~v thì ta nói hai đỉnh u và v liên thông với nhau
b) Mỗi lớp tương đương được gọi là một thành phần liên
thông của G
c) Một đồ thị (vô hướng) được gọi là liên thông nếu có
đường đi giữa mọi cặp đỉnh phân biệt của đồ thị.
44
45
Liên thông Không liên thông
Cho G = (V,E) là đồ thị vô hướng liên thông
a) Đỉnh v được gọi là đỉnh khớp nếu G – v không liên thông
(G – v là đồ thị con của G có được bằng cách xoá v và các
cạnh kề với v)
b) Cạnh e được gọi là cầu nếu G- e không liên thông( G-e
là đồ thị con của G có được bằng cách xoá cạnh e).
46
Trong đồ thị trên, các đỉnh khớp là v, w, s và các cầu là (x,v), (w,s).
Đỉnh khớp là v, w, s và các cầu là (x,v), (w,s).
Mệnh đề 1 : Đơn đồ thị mà bậc của mỗi đỉnh của
nó không nhỏ hơn một nửa số đỉnh là đồ thị liên
thông.
Mệnh đề 2: Nếu một đồ thị có đúng hai đỉnh bậc
lẻ thì hai đỉnh này phải liên thông, tức là có một
đường đi nối chúng.
Mệnh đề 3 : Cho G=(V,E) là một đồ thị liên
thông. Khi đó một đỉnh của G là điểm khớp khi
và chỉ khi trong G tồn tại hai đỉnh u và v sao cho
mỗi đường đi nối u và v đều phải đi qua đỉnh này.
Cho G là một đơn đồ thị có n đỉnh, m cạnh và
k thành phần liên thông. Khi đó :
2
)1)((
knkn
mkn
2
)1)((
knkn
mkn
Đồ thị có hướng G được gọi là liên thông
mạnh nếu với hai đỉnh phân biệt bất kỳ u và v
của G đều có đường đi từ u tới v và đường đi
từ v tới u.
Đồ thị có hướng G được gọi là liên thông yếu
nếu đồ thị vô hướng nền của nó là liên thông.
Đồ thị có hướng G được gọi là liên thông một
chiều nếu với hai đỉnh phân biệt bất kỳ u và v
của G đều có đường đi từ u tới v hoặc đường
đi từ v tới u.
Đồ thị G là liên thông mạnh nhưng đồ thị G’ là liên thông
yếu (không có đường đi từ u tới x cũng như từ x tới u).
Cho G = (V,E) là đồ thị vô hướng u,vV
a) Đường đi (dây chuyền) có chiều dài k nối hai đỉnh u,v
là dãy đỉnh và cạnh liên tiếp nhau
v0e1v1e2vk-1ekvk sao cho:
v 0=u ,v k = v, e i=v i-1v i , i=1,2,,k
52
a) Đường đi không có cạnh nào xuất hiện quá một lần gọi
là đường đi đơn
b) Đường đi không có đỉnh nào xuất hiện quá một lần gọi là
đường đi sơ cấp
c) Đường đi được gọi là chu trình nếu nó bắt đầu và kết
thúc tại cùng một đỉnh
53
54
• x, y, z, w, v, y là đường đi đơn (không sơ cấp) độ dài 5;
• x, w, v, z, y không là đường đi vì (v, z) không là cạnh;
• y, z, w, x, v, u, y là chu trình sơ cấp độ dài 6.
Bài toán. Thị trấn Königsberg chia thành 4 phần bởi
các nhánh của dòng sông Pregel
Bốn phần này được nối kết bởi 7 cây cầu
55
Đường đi Euler
Câu hỏi. Có thể đi qua bảy cây cầu mà không có cây cầu
nào đi quá 1 lần
Định nghĩa.
1. Đường đi Euler là đường đi qua tất cả các cạnh mỗi cạnh
(cung) đúng một lần. Chu trình Euler là chu trình đi qua tất cả
các cạnh của đồ thị mỗi cạnh đúng một lần.
2. Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler
57
Điều kiện cần và đủ.
Cho G = (V,E) là đồ thị vô hướng liên thông. G là đồ thị
Euler Mọi đỉnh của G đều có bậc chẵn.
Nếu G có hai đỉnh bậc lẻ còn mọi đỉnh khác đều có bậc
chẵn thì G có đường đi Euler
58
Nhận xét.
- Nếu đồ thị G có 2 đỉnh bậc lẻ thì G có 1 đường đi Euler
- Nếu đồ thị G có 2k đỉnh bậc chẵn thì ta có thể vẽ đồ thị
bằng k nét
Chu trình Euler Không có Euler
Đường đi Euler
Không có Euler Chu trình Euler Đường đi Euler
Ta có thể vạch được một chu trình Euler trong đồ thị liên
thông G có bậc của mọi đỉnh là chẵn theo thuật toán Fleury.
Xuất phát từ một đỉnh bất kỳ của G và tuân theo hai quy tắc
sau:
1. Mỗi khi đi qua một cạnh nào thì xoá nó đi; sau đó xoá đỉnh
cô lập (nếu có);
2. Không bao giờ đi qua một cầu, trừ phi không còn cách đi
nào khác.
60
•Xuất phát từ u, ta có thể đi theo cạnh (u,v) hoặc (u,x), giả sử là (u,v) (xoá (u,v)).
•Từ v có thể đi qua một trong các cạnh (v,w), (v,x), (v,t), giả sử (v,w) (xoá (v,w)).
•Tiếp tục, có thể đi theo một trong các cạnh (w,s), (w,y), (w,z), giả sử (w,s) (xoá
(w,s)).
•Đi theo cạnh (s,y) (xoá (s,y) và s). Vì (y,x) là cầu nên có thể đi theo một trong hai
cạnh (y,w), (y,z), giả sử (y,w) (xoá (y,w)).
• Đi theo (w,z) (xoá (w,z) và w) và theo (z,y) (xoá (z,y) và z).
•Tiếp tục đi theo cạnh (y,x) (xoá (y,x) và y). Vì (x,u) là cầu nên đi theo cạnh (x,v)
hoặc (x,t), giả sử (x,v) (xoá (x,v)).
• Tiếp tục đi theo cạnh (v,t) (xoá (v,t) và v), theo cạnh (t,x) (xoá cạnh (t,x) và t), cuối
cung đi theo cạnh (x,u) (xoá (x,u), x và u).
Nếu G là một đồ thị liên thông có q cạnh thì hành
trình ngắn nhất trong G có chiều dài :
q + m(G)
Với m(G) là số cạnh mà hành trình đi qua hai lần và
được xác định như sau:
Gọi V0(G) là tập hợp các đỉnh bậc lẻ (2k đỉnh) của G. Ta
phân 2k phần tử của G thành k cặp, mỗi tập hợp k cặp gọi
là một phân hoạch cặp của V0(G).
Ta gọi độ dài đường đi ngắn nhất từ u đến v là khoảng
cách d(u,v). Đối với mọi phân hoạch cặp Pi, ta tính
khoảng cách giữa hai đỉnh trong từng cặp, rồi tính tổng
d(Pi). Số m(G) bằng cực tiểu của các d(Pi):
Tập hợp các đỉnh bậc lẻ VO(G)={B, G, H, K} và tập hợp các
phân hoạch cặp là P={P1, P2, P3}, trong đó :
P1 = {(B, G), (H, K)} d(P1) = d(B, G)+d(H, K) = 4+1 = 5,
P2 = {(B, H), (G, K)} d(P2) = d(B, H)+d(G, K) = 2+1 = 3,
P3 = {(B, K), (G, H)} d(P3) = d(B, K)+d(G, H) = 3+2 = 5.
m(G) = min(d(P1), d(P2), d(P3)) = 3.
Do đó GT có được từ G bằng cách thêm vào 3 cạnh: (B, I),
(I, H), (G, K) và GT là đồ thị Euler. Vậy hành trình ngắn
nhất cần tìm là đi theo chu trình Euler trong GT:
A, B, C, D, E, F, K, G, K, E, C, J, K, H, J, I, H, I, B, I, A.
Đường đi Hamilton là một đường đi trong đồ thị
vô hướng đi qua tất cả các đỉnh của đồ thị, mỗi
đỉnh đúng một lần.
Một Chu trình Hamilton là một đường đi
Hamilton sau đi qua tất cả các đỉnh của đồ thị
thì trở về đỉnh xuất phát.
Chu trình Hamilton
Đường đi Hamilton
Không Hamilton
Định lý Dirac : Nếu G là một đơn đồ thị có n
đỉnh và mọi đỉnh của G đều có bậc không nhỏ
hơn n/2 thì G là một đồ thị Hamilton.
Hệ quả : Nếu G là đơn đồ thị có n đỉnh và mọi
đỉnh của G đều có bậc không nhỏ hơn (n-1)/2
thì G là đồ thị nửa Hamilton.
Định lý Ore : Nếu G là một đơn đồ thị có n
đỉnh và bất kỳ hai đỉnh nào không kề nhau
cũng có tổng số bậc không nhỏ hơn n thì G là
một đồ thị Hamilton.
Định lý: Nếu G là đồ thị 2 phe(phân đôi) với hai
tập đỉnh là V1, V2 có số đỉnh cùng bằng n (n 2)
và bậc của mỗi đỉnh lớn hơn n/2 thì G là một đồ
thị Hamilton
Đồ thị đầy đủ Kn với n lẻ và n 3 có đúng (n-1)/2
chu trình Hamilton phân biệt.
Đồ thị G này có 8 đỉnh, đỉnh nào cũng có bậc
4, nên G là đồ thị Hamilton
Đồ thị G này có 5 đỉnh bậc 4 và 2 đỉnh bậc 2
kề nhau nên tổng số bậc của hai đỉnh không
kề nhau bất kỳ bằng 7 hoặc 8, nên G là đồ thị
Hamilton
Đồ thị phân đôi này có bậc của mỗi đỉnh bằng
2 hoặc 3 (> 3/2), nên nó là đồ thị Hamilton.
Đồ thị Hamilton với chu trình Hamilton A, B, C, D, E,
F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, A
Cây là một đồ thị vô hướng liên thông, không
chứa chu trình và có ít nhất hai đỉnh.
Một đồ thị vô hướng không chứa chu trình và
có ít nhất hai đỉnh gọi là một rừng. Trong một
rừng, mỗi thành phần liên thông là một cây.
Trong đồ thị liên thông G, nếu ta loại bỏ cạnh
nằm trên chu trình nào đó thì ta sẽ được đồ
thị vẫn là liên thông.
Nếu cứ loại bỏ các cạnh ở các chu trình khác
cho đến khi nào đồ thị không còn chu trình
(vẫn liên thông) thì ta thu được một cây nối
các đỉnh của G. Cây đó gọi là cây khung hay
cây bao trùm của đồ thị G.
Trước hết sắp xếp các cạnh của đồ thị G theo thứ
tự không giảm của trọng số. :
1. Bắt đầu từ đồ thị rỗng T có n đỉnh.Sắp xếp các
cạnh của G theo thứ tự tăng dần về trọng số.
2. Bắt đầu từ cạnh đầu tiên của dãy này, ta cứ
thêm dần các cạnh của dãy đã được xếp vào T
theo nguyên tắc cạnh thêm vào không được
tạo thành chu trình trong T.
3. Lặp lại Bước 3 cho đến khi nào số cạnh trong T
bằng n1, ta thu được cây khung nhỏ nhất cần
tìm.
Sắp xếp các cạnh của đồ thị theo thứ tự trọng số tăng dần :
{(v3, v5), (v4, v6), (v4, v5), (v5, v6), (v3, v4), (v1, v3), (v2, v3), (v2, v4), (v1, v2)}.
Các file đính kèm theo tài liệu này:
- tailieu.pdf