TOÁN HỌC RỜI RẠC
PHẦN 2
DISCRETE MATHEMATICS
PART TWO
NỘI DUNG
1. PHÉP ĐẾM
a. Nguyên lý cộng, nhân & bù trừ
b. Giải tích tổ hợp
c. Nguyên lý Dirichlet
d. Công thức đệ quy
2. LÝ THUYẾT ĐỒ THỊ
a. Đại cương
b. Đồ thị liên thông
c. Đường đi ngắn nhất
d. Cây khung trọng lượng tối tiểu
e. Luồng cực đại
3. SỐ HỌC
a. Lý thuyết chia hết
b. Lý thuyết đồng dư
2
PHÉP ĐẾM (1)
•
NGUYÊN LÝ CỘNG, NHÂN, BÙ
–
A là một tập hợp, ký hiệu |A| bản số của A, trong trường hợp A
là tập hữu hạn, |A| chính là số phần tử của A
–
|A ∪ B|=|A| + |B| -|A ∩ B|
nếu A ∩ B = ∅ thì |A ∪ B|=|A| + |B|
–
|A x B| = |A| * |B|

m
n
m
−
=








PHÉP ĐẾM (2)
•
CÁC VÍ VỤ
–
Trong một phòng họp có n người, mỗi người bắt tay với mỗi
người khác đúng một lần. Số bắt tay?
–
Dùng n bit để biểu diễn nhị phân cho các số nguyên không âm,
số số nguyên có thể được biểu diễn?
–
Có bao nhiêu số thập phân có 6 chữ số? Bao nhiêu số thập phân
có số chữ số nhỏ hơn sáu?
–
Có bao nhiêu cách sắp xếp chỗ ngồi cho n người xung quanh
một chiếc bàn họp tròn?
Bây giờ giả sử ông chủ tịch cuộc họp được sắp ngồi ở một ghế
xác định, có bao nhiêu cách sắp xếp chỗ ngồi cho các người còn

v
2
, v
1
, v
2
∈ E
•
Đỉnh cô lập: đỉnh không có cạnh đi qua
•
Đỉnh treo: chỉ thuộc một cạnh duy nhất (cạnh treo)
•
Đa đồ thị: tồn tại nhiều hơn 1 cạnh nối hai đỉnh
•
đồ thị đơn: tồn tại nhiều nhất một cạnh nối hai đỉnh
•
Đỉnh kề: chung cạnh
•
Cạnh kề: chung đỉnh
•
Đồ thị đầy đủ: mọi cặp đỉnh (phân biệt) đều có cạnh nối
•
Đồ thị con: A⊆V, E
A
={(v
1
, v
2
) ∈ E | v
1

, v
1
, …, v
n
=v sao cho v
i
v
i+1
∈ E
•
Đường đi sơ cấp: tập ∀i=0, …, n-1: v
i
≠ v
i+1

•
Chu trình: v
0
= v
n
•
Chu trình sơ cấp: ∀i=1, …, n-1: v
i
≠ v
i+1

–
ĐỒ THỊ LIÊN THÔNG
•
Đồ thị vô hướng liên thông: ∀u, v ∈ V, ∃đường đi giữa u, v

•
Nửa bậc ngoài (ra): d
+
(x)
•
Bậc của đỉnh: d(x) = d
-
(x) + d
+
(x)
•
ω
+
(A) = { (i, j)| i∈A, j∉ A }
•
ω
-
(A) = { (i, j)| j∈A, i∉ A }
•
θ(A) = ω
+
(A) ∪ ω
-
(A)
•
Đa đồ thị, đồ thị đơn
•
Đỉnh kề, cung kề
•
Đồ thị có hướng đối xứng, phi đối xứng

i+1

•
Chu trình: v
0
= v
n
•
Chu trình sơ cấp: chu trình & ∀i=1, …, n-1: v
i
≠ v
i+1

–
ĐỒ THỊ LIÊN THÔNG
•
Đồ thị có hướng liên thông: đồ thị vô hướng tương ứng liên
thông
•
Đồ thị có hướng liên thông một chiều: ∀u, v ∈ V, ∃đường đi từ
u đến v hoặc từ v đến u
•
Đồ thị có hướng liên thông mạnh: ∀u, v ∈ V, ∃đường đi từ u
đến v và ∃đường đi từ v đến u
•
Thành phần liên thông: quan hệ R={(u, u)| u ∈E}∪ {(u, v) |
∃đường đi từ u đến v và ∃đường đi từ v đến u}
9
LÝ THUYẾT ĐỒ THỊ (7)
•

Chu trình Hamilton
–
Đồ thị Hamilton
–
Đồ thị nửa Hamilton
–
Các định lý:
•
Đồ thị đơn vô hướng bậc n > 2, nếu ∀x ∈ E, d(x) ≥ n/2 thì là
đồ thị Hamilton
•
Đồ thị có hướng liên thông bậc n, nếu ∀x ∈ E, d
-
(x), d
+
(x) ≥
n/2 thì là đồ thị Hamilton
•
Đồ thị có hướng, đầy đủ là đồ thị nửa Hamilton
•
Đồ thị có hướng, đầy đủ bậc > 2 là đồ thị Hamilton
–
Đồ thị đấu loại
•
Đồ thị đấu loại là nửa Hamilton
•
Đồ thị đấu loại liên thông là Hamilton
11
ĐƯỜNG ĐI NGẮN NHẤT
•

Bài toán
–
Giải thuật Kruskal
–
Giải thuật Prim
13
LUỒNG CỰC ĐẠI (1)
•
MẠNG:
–
Đổ thị có hướng G = (V, A) là một mạng khi:
•
Tồn tại duy nhất một đỉnh phát s, không có cung vào, chỉ có
cung ra
•
Tồn tại duy nhất một đỉnh thu t, không có cung ra, chỉ có
cung vào
•
Mỗi cung a được gắn với một giá trị không âm c(a), được
gọi là băng thông của cung
•
Nếu không tồn tại cung từ u đến v, băng thông của (u, v)
dược quy ước là 0
–
Luồng trong mạng
•
G = (V, A) là một mạng
•
Ánh xạ f: A → R
+

G = (V, A) là một mạng, X
0
⊆ V, Y
0
= V – X
0
•
Lát cắt (X
0
, Y
0
) là tập các cung (i, j) sao cho:
nếu i ∈ X
0
thì j ∈ Y
0

nếu i ∈ Y
0
thì j ∈ X
0

•
Nếu điểm phát và điểm thu thuộc hai phần khác nhau của lát
cắt, lát cắt được gọi là lát cắt tách
15
)(),(),(
),( ),(
fvaltxfvsf
Avs Atx

)
•
Giá trị của luồng cực đại không vượt quá khả năng thông của lát
cắt hẹp nhất
•
Đồ thị tăng luồng:
f là một luồng trong G = (V, A)
Đồ thị tăng luồng G
f
= (V, A
f
) được xây dựng như sau:
–
(u, v) ∈ A: f(u, v)=0 thì (u, v) ∈ A
f
với trọng số p(u, v) = c(u, v)
–
(u, v) ∈ A: f(u, v)=c(u, v) thì (u, v) ∈ A
f
với trọng số p(u, v)=f(u, v)
–
(u, v) ∈ A: 0 <f(u, v)<c(u, v) thi
(u, v) ∈ A
f
với trọng số p(u, v)=c(u, v) – f(u, v)
(v, u) ∈ A
f
với trọng số p(u, v)=f(u, v)
16
∑

δ>0 là giá trị nhỏ nhất trong các trọng số của các cung trên
P. Xây dựng ánh xạ g: A
f
→ R
+
như sau:
–
g(u, v) = f(u, v) + δ nếu (u, v) là cung thuộc P và là cung thuận
–
g(u, v) = f(u, v) - δ nếu (u, v) là cung thuộc P và là cung nghịch
–
G(u, v) = f(u, v) nếu (u, v) không thuộc P
•
f là luồng trong G = (V, A)
Các mệnh đề sau là tương đương:
–
f là luồng cực đại
–
Không tìm được đường tăng luồng P
–
Tồn tại lát cắt (X
0
, Y
0
): Val(f) = c(X
0
, Y
0
)
•

–
Gãn nhãn cho mỗi ảnh u của x chưa được gán nhãn mà f(x, u)<c(x, u):
u : [+x, σ(u) ] / σ(u) = min{ σ(x), c(x, u) – f(x, u) }
–
Gán nhãn cho mỗi tạo ảnh v của x chưa được gán nhãn mà f(v, x) > 0
v : [-x, σ(v) ] / σ(v) = min{ σ(x), f(v, x) }
x được duyệt
18
LUỒNG CỰC ĐẠI (4)
•
B3:
Lặp lại B2 cho đến khi
–
Hoặc đỉnh thu được gán nhãn t : [ ±y, σ(t) ]: chuyển sang B4
–
Hoặc không thể gán nhãn cho đỉnh thu t: thuật toán kết thúc. Đặt X
0

tập các đỉnh được gán nhãn, Y
0
tập các đỉnh không được gán nhãn, khi
đó (X
0
, Y
0
) là lát cắt hẹp nhất
•
B4:
đặt x = t : [ ±y, σ(t) ], chuyển sang B5
•

2
, …, a
n
) = d ⇒ ∃x
1
, x
2
, …, x
n
/ a
1
x
1
+ a
2
x
2
+ …+a
n
x
n
=d
•
∀m nguyên dương: (ma
1
, ma
2
, …, ma
n
) =m (a

aaa
d
a
d
a
d
a
n
n
)21
21
, ,,(
), ,,( =
1), ,,(
21
=
d
a
d
a
d
a
n
SỐ HỌC (2)
•
Nếu (a, b)=1, (a, c)=1 thì (a, bc)=1
•
Nếu a=pb + r (0 ≤ r < b) thì (a, b) = (b, r)
–
BCNN

]
•
(a
1
, a
2
, …, a
n
) =d
•
a
1
, a
2
, …, a
n
nguyên tố sánh đôi [a
1
, a
2
, …, a
n
] = a
1
a
2
… a
n
21
[ ]

), ,,(
, ,,
2121
=






SỐ HỌC (3)
•
SỐ NGUYÊN TỐ, HỢP SỐ
–
Số nguyên tố
–
Hợp số
–
p nguyên tố, n ≥ 0 thì p | n hoặc (n, p)=1
–
p | a
1
a
2
…a
k
thì ∃i / p | a
i
–
p | p

k
k
pppd
β
ββ

21
21
=
k
k
pppn
α
αα

21
21
=
SỐ HỌC (4)
•
PHƯƠNG TRÌNH NGUYÊN
–
ax + by =c
•
d=(a, b)
•
Nếu d không là ước của c thì phương trình vô nghiệm
•
Nếu d | c thì nghiệm của phương trình có dạng:
–

t
d
b
xx
+=
+=
0
0
Trong đó, x
0
, y
0
là một nghiệm
(nguyên) của phương trình
SỐ HỌC (5)
–
Quan hệ đồng dư là quan hệ tương đương
–
Các mệnh đề tương đương:
•
a = b (mod m)
•
a = b + mt
•
(a-b) = 0 (mod m)
–
Các tính chất:
•
a
i

a = b (mod m) thì (a+c) = (b+c) (mod m)
•
a = b (mod m) thì a = (b +km) (mod m), (a+km) = b (mod
m)
•
a = b (mod m) thì a
n
= b
n
(mod m)
•
a = b (mod m) thì ac = bc (mod m)
•
(c, m)=1, a = b (mod m) iif ac = bc (mod m)
•
d = (a, b, m) thì (a/d) = (b/d) (mod (m/d))
•
d=(a, b), (d, m)=1 thì (a/d) = (b/d) (mod m)
•
a = b (mod m
i
) i=1, 2, …, n thì a = b (mod [m
1
, m
2
, …, m
n
])
24
SỐ HỌC (6)

)(mod)1(

)(mod0
0
0
m
d
m
dxx
m
d
m
xx
x
0
là một giá trị
thỏa mãn phương
trình