TOÁN RỜI RẠC

Đặng Cao Cường

Bộ môn Khoa học và Kỹ thuật tính toán, Khoa CNTT, ĐHQGHN
(cuongdc@vnu.edu.vn)

1
 ĐỒ THỊ (8 TIẾT)
1. Đồ thị, phân loại đồ thị
2. Các thuật ngữ về đồ thị
3. Biểu diễn đồ thị và tính đẳng cấu
4. Đường đi và tính liên thông
5. Đường đi EULER và đường đi HAMILTON
6. Bài toán đường đi ngắn nhất
7. Đồ thị phẳng
8. Tô màu đồ thị
2
 ĐỒ THỊ, PHÂN LOẠI ĐỒ THỊ
• Lý thuyết đồ thị là ngành khoa học được phát triển từ lâu
nhưng lại có nhiều ứng dụng hiện đại
• Đồ thị được dùng để giải các bài toán trong nhiều lĩnh vực
khác nhau (mạch điện, cấu trúc của hợp chất hóa học, mạng
máy tính, …)
• Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối
các đỉnh đó
• Người ta phân loại đồ thị theo đặc tính của cạnh nối các cặp
đỉnh của đồ thị
3
 PHÂN LOẠI ĐỒ THỊ
ĐƠN ĐỒ THỊ
Đơn đồ thị 𝐺 = (𝑉, 𝐸), trong đó tập không rỗng 𝑉 mà các phần
tử của nó được gọi là các đỉnh và một tập 𝐸 mà các phần tử
được gọi là cạnh, đó là các cặp không thứ tự của các đỉnh
phân biệt

4
 PHÂN LOẠI ĐỒ THỊ
ĐA ĐỒ THỊ
• Đa đồ thị 𝐺 = (𝑉, 𝐸), trong đó 𝑉 là tập đỉnh, 𝐸 là tập cạnh, đồ
thị gồm các cạnh vô hướng, nhưng có thể có nhiều cạnh nối
mỗi cặp đỉnh (cạnh bội)
• Đơn đồ thị là một trường hợp riêng của đa đồ thị.

5
 PHÂN LOẠI ĐỒ THỊ
ĐỒ THỊ KHUYÊN
Đồ thị khuyên 𝐺 = (𝑉, 𝐸), trong đó 𝑉 là tập đỉnh, 𝐸 là tập cạnh, đồ
thị có thêm loại cạnh nối từ một đỉnh đến chính nó.

6
 PHÂN LOẠI ĐỒ THỊ
ĐƠN ĐỒ THỊ CÓ HƯỚNG
• Đơn đồ thị có hướng 𝐺 = (𝑉, 𝐸), trong đó tập không rỗng 𝑉
mà các phần tử của nó được gọi là các đỉnh và một tập 𝐸
mà các phần tử được gọi là cạnh, đó là các cặp có thứ tự
của các đỉnh phân biệt

7
 PHÂN LOẠI ĐỒ THỊ
ĐA ĐỒ THỊ CÓ HƯỚNG
• Đa đồ thị có hướng 𝐺 = (𝑉, 𝐸), trong đó 𝑉 là tập đỉnh, 𝐸 là tập
cạnh, đồ thị gồm các cạnh có hướng, nhưng có thể có nhiều
cạnh nối mỗi cặp đỉnh (cạnh bội)
• Đơn đồ thị có hướng là một trường hợp riêng của đa đồ thị có
hướng.

8
 PHÂN LOẠI ĐỒ THỊ
Loại Cạnh Có cạnh Có cạnh
bội khuyên
không? không
Đơn đồ thị Vô hướng

Đa đồ thị Vô hướng x

Đồ thị khuyên x

Đơn đồ thị có Có hướng

hướng
Đa đồ thị có Có hướng x
hướng
9
10
11
12
XÁC ĐỊNH LOẠI CỦA CÁC ĐỒ THỊ SAU
14
 BẬC CỦA ĐỈNH

1. Đỉnh b, c liền kề
(láng giềng) trong
cả 2 đồ thị.
2. Đỉnh c, d liền kề
(láng giềng)? 15

3. Bậc của các đỉnh?

 BẬC CỦA ĐỈNH

1) Có bao nhiêu cạnh trong đồ thị đơn có 10 đỉnh, mỗi đỉnh có bậc
bằng 5?
2) Có bao nhiêu cạnh trong đồ thị đơn có 99 đỉnh, mỗi đỉnh có bậc
bằng 5?

→ Định lý 2: Đồ thị đơn có một số chẵn các đỉnh bậc lẻ. 16

BẬC VÀO RA

17
BẬC VÀO RA

18
 ĐỒ THỊ ĐẦY ĐỦ

Đồ thị đầy đủ 𝑛 đỉnh, ký hiệu 𝐾𝑛 là một đơn đồ thị mà mỗi cặp

đỉnh phân biệt đều có cạnh nối.

19
 ĐỒ THỊ CHU TRÌNH (VÒNG)

Đồ thị chu trình 𝐶𝑛 (𝑛 ≥ 3) là một đồ thị có 𝑛 đỉnh

𝑣1 , 𝑣2 , … , 𝑣𝑛 và các cạnh 𝑣1 , 𝑣2 , 𝑣2 , 𝑣3 ,…,
𝑣𝑛−1 , 𝑣𝑛 , 𝑣𝑛 , 𝑣1 .

20
 ĐỒ THỊ BÁNH XE

Khi thêm một đỉnh vào đồ thị 𝐶𝑛 (𝑛 ≥ 3) và nối đỉnh này

với tất cả các đỉnh của 𝐶𝑛

21
 CÁC KHỐI 𝑛 CHIỀU

Đồ thị các khối 𝑛 chiều, ký hiêu 𝑄𝑛 là các đồ thị có 2𝑛 đỉnh, mỗi

đỉnh được biểu diễn bằng xâu nhị phân độ dài 𝑛. Hai đỉnh là
liền kề nếu và chỉ nếu các xâu nhị phân biểu diễn chúng khác
nhau đúng 1 bit.

22
 ĐỒ THỊ PHÂN ĐÔI (HAI PHÍA)

Một đồ thị 𝐺 được gọi là đồ thị phân đôi (đồ thị hai phía) nếu
tập đỉnh 𝑉 có thể phân làm hai tập con không rỗng, rời nhau
𝑉1 , 𝑉2 sao cho mỗi cạnh của đồ thị nối một đỉnh của 𝑉1 với một
đỉnh của 𝑉2 .

23
ĐỒ THỊ PHÂN ĐÔI ĐẦY ĐỦ

24
 ĐỒ THỊ CON

Đồ thị con của đồ thị 𝐺 = (𝑉, 𝐸) là đồ thị 𝐺 ′ = 𝑉 ′ , 𝐸 ′ , trong

đó 𝑉 ′ ∈ 𝑉 và 𝐸 ′ ∈ 𝐸.

25
HỢP CỦA HAI ĐỒ THỊ

26
BIỂU DIỄN ĐỒ THỊ - DANH SÁCH CẠNH,
DANH SÁCH KỀ

Danh sách cạnh: Liệt kê tất cả các cạnh của đồ thị

Danh sách liền kề: Chỉ rõ các đỉnh nối với mỗi đỉnh của đồ thị

Danh sách cạnh

1. {a,b}
2. {a,c} Danh sách kề
3. {a,e}
4. {c,d}
5. {c,e}
6. {e,d}
27
DANH SÁCH CẠNH, DANH SÁCH KỀ

Danh sách cạnh?

Danh sách liền kề?

28
BIỂU DIỄN ĐỒ THỊ - MA TRẬN LIỀN KỀ (1)

29
BIỂU DIỄN ĐỒ THỊ - MA TRẬN LIỀN KỀ (2)

30
BIỂU DIỄN ĐỒ THỊ - MA TRẬN LIỀN KỀ (3)

31
SỰ ĐẲNG CẤU CỦA HAI ĐỒ THỊ

32
 SỰ ĐẲNG CẤU CỦA HAI ĐỒ THỊ (2)
Các cặp đồ thị sau có đẳng cấu hay không?

33
 SỰ ĐẲNG CẤU CỦA HAI ĐỒ THỊ (3)

Các cặp đồ thị sau có

đẳng cấu hay không?

34
 ĐƯỜNG ĐI, CHU TRÌNH
• Đường đi độ dài 𝑠 từ 𝑢 đến 𝑣 trong đơn đồ thị là một dãy
các đỉnh 𝑥0 , 𝑥1 , … , 𝑥𝑠 mà 𝑥0 = 𝑢; 𝑥𝑠 = 𝑣 và
𝑥0 , 𝑥1 , 𝑥1 , 𝑥2 , … , (𝑥𝑠−1 , 𝑥𝑠 ) là các cạnh của đồ thị.
• Đường đi được gọi là chu trình nếu đường đi có bắt đầu và
kết thúc tại một đỉnh.
• Đường đi (hay chu trình) trong đơn đồ thị được gọi là
đường đi đơn (chu trình đơn) nếu nó không chứa một cạnh
quá một lần.

35
 TÍNH LIÊN THÔNG TRONG ĐỒ
THỊ VÔ HƯỚNG
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ị.

36
ĐỊNH LÝ: GIỮA MỌI CẶP ĐỈNH PHÂN
BIỆT CỦA MỘT ĐỒ THỊ VÔ HƯỚNG
LIÊN THÔNG LUÔN CÓ ĐƯỜNG ĐI
ĐƠN.

37
 CÁC THÀNH PHẦN LIÊN THÔNG
Một đồ thị không liên thông là hợp của nhiều đồ thị con
liên thông (các đồ thị con không có đỉnh chung). Các
đồ thị con liên thông rời nhau như vậy được gọi là các
thành phần niên thông.

38
 ĐỈNH KHỚP (ĐIỂM KHỚP)
• Một đỉnh được gọi là đỉnh khớp nếu như việc xóa đi
đỉnh này và tất cả các cạnh liên thuộc với nó sẽ tạo ra
đồ thị mới có nhiều thành phần liên thông hơn đồ thị
gốc.
• Các đỉnh nào trong đồ thị dưới đây là đỉnh khớp?

39
 CẦU (CẠNH CẮT)
• Một cạnh được gọi là cầu nếu như việc xóa đi cạnh
này sẽ tạo ra đồ thị mới có nhiều thành phần liên
thông hơn đồ thị gốc.

• Các cạnh nào trong đồ thị dưới đây là cầu?

40
 TÍNH LIÊN THÔNG TRONG ĐỒ
THỊ CÓ HƯỚNG
• Đồ thị có hướng gọi là liên thông mạnh nếu có đường đi
từ a tới b và từ b đến a với mọi đỉnh a, b của đồ thị;
• Đồ thị có hướng gọi là liên thông yếu nếu luôn tồn tại
đường đi giữa hai đỉnh bất kỳ khi ta không quan tâm đến
hướng của các cạnh. Đồ thị liên thông mạnh cũng là đồ thị
liên thông yếu.

41
 ĐẾM SỐ ĐƯỜNG ĐI GIỮA CÁC
ĐỈNH (1)
• Cho 𝐺 là một đồ thị (có thể có cạnh bội, khuyên) với ma
trận liền kề 𝐴, khi đó số đường đi khác nhau độ dài 𝑟 từ 𝑖
đến 𝑗 bằng giá trị phần tử (𝑖, 𝑗) của ma trận 𝐴𝑟 .
• Chứng minh bằng quy nạp
➢Giả sử phần tử (𝑖, 𝑗) của ma trận 𝐴𝑟 là số đường đi khác
nhau độ dài 𝑟 từ 𝑖 đến 𝑗.
➢Vì 𝐴𝑟+1 = 𝐴𝑟 × 𝐴 nên phần tử 𝑖, 𝑗 của 𝐴𝑟+1 bằng
𝑟+1 𝑟 𝑟 𝑟 𝑟
𝑎𝑖,𝑗 = σ𝑛𝑘=1 𝑎𝑖,𝑘 𝑎𝑘,𝑗 = 𝑎𝑖,1 𝑎1,𝑗 + 𝑎𝑖,2 𝑎2,𝑗 + ⋯ + 𝑎𝑖,𝑛 𝑎𝑛,𝑗 , trong
𝑟
đó 𝑎𝑖,𝑘 là phần tử (𝑖, 𝑘) của 𝐴𝑟 , là số đường đi độ dài 𝑟 từ 𝑖 đến
𝑘. 42
 ĐẾM SỐ ĐƯỜNG ĐI GIỮA CÁC
ĐỈNH (2)

Đếm số đường đi độ dài 4 từ a

đến d 43
 THỰC HÀNH

Các đồ thị sau có bao nhiêu đỉnh và bao nhiêu cạnh

1) 𝐾9
2) 𝐶15
3) 𝑊15
4) 𝐾3,4
5) 𝑄7

44
ĐỒ THỊ NÀO DƯỚI ĐÂY LÀ ĐỒ THỊ
PHÂN ĐÔI (HAI PHÍA)

45
Dựng và tính số cạnh của đồ thị đơn có bậc các đỉnh như sau
1) 4, 3, 3, 2, 2
2) 3, 3, 3, 3, 2
3) 1, 2, 3, 4, 6
4) 1, 2, 3, 4, 4

46
47
48
49
• Chứng tỏ rằng đồ thị liên thông có n đỉnh thì có ít nhất n-1
cạnh.

• Chứng tỏ rằng trong một đơn đồ thị luôn tồn tại đường đi từ
một đỉnh bậc lẻ tới một đỉnh bậc lẻ khác.

50
ĐẾM SỐ ĐƯỜNG ĐI ĐỘ DÀI 4, ĐỘ
DÀI 8 TỪ 𝒗𝟏 ĐẾN 𝒗𝟒

51
a) Hãy tìm ma trận kề của K2, 3.
b) Tìm số đường đi độ dài 3 và 4 từ một đỉnh bậc 3 đến
một đỉnh bậc 2.

52
CHU TRÌNH EULER VÀ ĐƯỜNG ĐI
EULER (1)
• Chu trình đơn chứa tất cả các cạnh của đồ thị G được gọi là chu
trình Euler;
• Đường đi đơn chứa tất cả các cạnh của đồ thị G được gọi là
đường đi Euler;

53
 CHU TRÌNH EULER VÀ ĐƯỜNG ĐI
EULER (2)
Đồ thị nào có chu
trình Euler?
Đồ thị nào có đường
đi Euler?

54
 ĐIỀU KIỆN CẦN VÀ ĐỦ ĐỂ ĐỒ THỊ
CÓ CHU TRÌNH EULER
Một đa đồ thị liên thông có chu trình Euler nếu và chỉ
nếu mỗi đỉnh của nó đều có bậc chẵn.

55
56
57
IỀU KIỆN CẦN VÀ ĐỦ ĐỂ ĐỒ THỊ CÓ ĐƯỜNG Đ
EULER
Một đa đồ thị liên thông có đường đi Euler nhưng không có
chu trình nếu và chỉ nếu đồ thị có đúng 2 đỉnh bậc lẻ.
Thuật toán tìm đường đi Euler???

58
ĐƯỜNG ĐI, CHU TRÌNH HAMILTON
• Đường đi 𝑥1 , … , 𝑥𝑛−1 , 𝑥𝑛 trong đồ thị 𝐺 = 𝑉, 𝐸 , 𝑛 = |𝑉|, được gọi là
đường đi Hamilton nếu 𝑥𝑖 ≠ 𝑥𝑗 với 𝑖 ≠ 𝑗.
• Chu trình 𝑥0 , 𝑥1 , … , 𝑥𝑛−1 , 𝑥𝑛 trong đồ thị 𝐺 = 𝑉, 𝐸 , 𝑛 = |𝑉|, được gọi
là chu trình Hamilton nếu 𝑥𝑖 ≠ 𝑥𝑗 với 𝑖 = 1,2, . . , 𝑛; 𝑗 = 1,2, . . , 𝑛; 𝑖 ≠ 𝑗.
• Có điều kiện cần và đủ để đồ thị có đường đi, chu trình
Hamilton?
• Có thuật toán tìm đường đi, chu trình Hamilton?

59
1) TÌM ĐƯỜNG ĐI, CHU TRÌNH HAMILTON

60
2) CHỈ RA RẰNG 𝑲𝒏 LUÔN CÓ CHU TRÌNH HAMILTON
TÌM ĐƯỜNG ĐI, CHU TRÌNH
EULER

61
TÌM ĐƯỜNG ĐI, CHU TRÌNH
HAMILTON

62
VẼ BẰNG MỘT NÉT

63
1) với giá trị nào của 𝑚, 𝑛 thì 𝐾𝑚,𝑛 có chu trình Euler,
đường đi Euler?
2) với giá trị nào của 𝑚, 𝑛 thì 𝐾𝑚,𝑛 có chu trình
Hamilton, đường đi Hamilton?

64
 ĐỒ THỊ CÓ TRỌNG SỐ
• Đồ thị mà mỗi cạnh của nó được gán một con số (nguyên hoặc thực), được
gọi là trọng số ứng với cạnh đó.
• Nhiều bài toán có thể mô hình bằng đồ thị có trọng số.

65
 BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN
NHẤT
• Bài toán tìm đường đi ngắn nhất: Tìm đường đi có độ dài ngắn nhất giữa hai
đỉnh của đồ thị.

• Ví dụ, tìm đường đi ngắn nhất từ a đến z

66
THUẬT TOÁN DIJKSTRA TÌM ĐƯỜNG ĐI
NGẮN NHẤT (1)

67
THUẬT TOÁN DIJKSTRA TÌM ĐƯỜNG ĐI
NGẮN NHẤT (2)

68
69
TÌM ĐƯỜNG ĐI NGẮN NHẤT BẰNG
THUẬT TOÁN DIJKSTRA

70
71
72
 ĐỒ THỊ PHẲNG
• Đồ thị phẳng là đồ thị có thể vẽ được trên mặt phẳng
mà không có cạnh nào cắt nhau (ở một điểm không
phải là điểm mút của các cạnh)
• Ví dụ, 𝐾4 là đồ thị phẳng

73
 CÔNG THỨC EULER (1)
• G là đồ thị đơn phẳng liên thông có e cạnh và v đỉnh.
Gọi r là số miền trong biểu diễn mặt phẳng của G, khi
đó r = e – v + 2

74
 CÔNG THỨC EULER (2)
• Giả sử một đơn đồ thị phẳng liên thông có 20 đỉnh, mỗi
đỉnh bậc bằng 3, đồ thị chia mặt phẳng thành bao nhiêu
miền?
v = 20; e = (20x3)/2=30 → r = e – v + 2 = 30 – 20 +
2 = 12

• Giả sử G là một đơn đồ thị phẳng liên thông có e cạnh, v

đỉnh (v  3), khi đó e ≤ 3v-6
2e/3  r = e – v + 2 nên e ≤ 3v-6
• Chứng minh K5 không phẳng 75

K5 có 5 đỉnh và 10 cạnh, ta có 10 > 3x5-6

 CÔNG THỨC EULER (3)

• Giả sử G là một đơn đồ thị phẳng liên thông có e cạnh, v

đỉnh (v  3), và không có chu trình độ dài 3, khi đó e ≤ 2v-4

• Chứng minh K3,3 không phẳng

→ K5 và K3,3 là không phẳng, nên nếu đồ thị chứa K5 hoặc

K3,3 thì đồ thị không phẳng;
76
 ĐỊNH LÝ KURATOWSKI
• Một đồ thị phẳng G, mọi đồ thị nhận được từ đồ thị G bằng cách bỏ đi
cạnh (u,v) và thêm vào đỉnh với w cùng hai cạnh (u,w) và (w,v) cũng là
đồ thị phẳng và được gọi là đồng phôi với G.

• Đồ thị là không phẳng nếu và chỉ nếu nó chứa một đồ thị con đồng
phôi với K5 hoặc K3,3;

77
 TÔ MÀU ĐỒ THỊ (1)
• Tô màu bản đồ
✓ Các vùng kề nhau tô bằng màu khác nhau
✓ Dùng ít màu nhất

• Biểu diễn bản đồ bằng đồ thị

78
79
TÔ MÀU ĐỒ THỊ (2)

80
81
• Số màu của đồ thị Kn

• Số màu của đồ thị Km,n

• Số màu của đồ thị Cn

82
• Bài toán tô màu đồ thị có nhiều ứng dụng
• Ứng dụng lập lịch thi: Lập lịch thi sao cho không có sinh viên
nào thi 2 môn cùng một lúc
➢ Các môn là đỉnh của đồ thị
➢ 2 môn có sinh phải thi cả 2 môn → cạnh
➢ Thời gian thi được biểu diễn bằng các màu khác nhau
→ Việc lập lịch chính là tô màu đồ thị

83
84
85
86
87
Số miền của Cn
Số miền của Wn

88
89