Bài giảng Toán rời rạc - Chương 5: Lý thuyết đồ thị - Nguyễn Lê Minh

TOÁN RỜI RẠC
Chương 5: LÝ THUYẾT ĐỒ THỊ
GV: NGUYỄN LÊ MINH
Bộ môn Công nghệ thông tin
Nội dung
Khái niệm đồ thị
Các loại đồ thị
Bậc của đồ thị
Biểu diễn đồ thị
Tính liên thông trong đồ thị
Chu trình Euler – Hamilton
Tìm đường đi ngắn nhất
2
Khái niệm
3
Đồ thị là 1 cấu trúc rời rạc gồm các đỉnh và các cạnh (vô
hướng hoặc có hướng) nối các đỉnh đó.
Có 2 loại đồ thị: Đồ thị có hướng – Đồ thị vô hướng
Đồ thị có hướng
3
Đồ thị có hướng G = (V, E) trong đó:
• Tập khác rỗng V là tập hợp hữu hạn các đỉnh của đồ thị
• E là tập hợp các cặp có thứ tự gồm hai phần tử khác
nhau của V gọi là các cung.
• Mỗi cạnh e∈E liên kết với 1 cặp đỉnh (i,j)∈ 𝑉2, quy định
hướng đi từ i -> j
Đồ thị vô hướng
3
Đồ thị vô hướng G = (V, E) trong đó:
• Tập khác rỗng V là tập hợp hữu hạn các đỉnh của đồ thị
• E là tập hợp các cặp không có thứ tự gồm hai phần tử
khác nhau của V gọi là các cạnh.
• Mỗi cạnh e∈E liên kết với 1 cặp đỉnh (i,j)∈ 𝑉2, không quy
định thứ tự.
Cạnh song song và khuyên
3
• Nếu đồ thị có cạnh nối từ một đỉnh với chính nó, cạnh này
được gọi là khuyên
• Nếu hai cạnh V và V’ cùng liên kết với cặp (i,j) thì V và V’
được gọi là cặp cạnh song song với nhau
Các loại đồ thị
3
Đồ thị rỗng
Có tập cạnh là tập
rỗng
Đồ thị đơn
Không có khuyên
và cạnh song song
Đồ thị đủ
Là đồ thị vô hướng, 
đơn, 2 đỉnh bất kỳ
luôn kề nhau
Các loại đồ thị
3
Đồ thị hai phía (Đồ thị lưỡng phân)
Là một đồ thị trong đó tập các đỉnh có thể được chia thành
hai tập không giao nhau thỏa mãn điều kiện không có cạnh
nối hai điểm bất kỳ thuộc cùng một tập
Đỉnh kề
3
Trong đồ thị vô hướng G=(V,E), nếu e=(u,v) là 1 cạnh thì:
• Đỉnh u, v là hai đỉnh kề nhau
• Cạnh e là cạnh liên thuộc với đỉnh u,v
• Đỉnh u, v là đỉnh đầu
cạnh e
u
v
e
Đỉnh kề
3
Trong đồ thị có hướng G=(V,E), nếu e=(u,v) là 1 cung thì:
• Đỉnh v là đỉnh kề của đỉnh u
• Cung e là cung đi ra đỉnh u và cung đi vào đỉnh v
• Đỉnh u là đỉnh đầu
cung e, đỉnh v là đỉnh
cuối cung e
t
s x
v
u
e
Bậc của đỉnh
3
Bậc của đỉnh v trong đồ thị vô hướng G=(V,E), ký hiệu deg(v), 
là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh 
được tính hai lần cho bậc của nó
Deg(v) = 1 -> đỉnh treo
Deg(v) = 0 -> đỉnh cô lập
VD: Deg(9) = ?
Deg(0) = ?
Bậc của đỉnh
3
Trong đồ thị có hướng G=(V,E), 
• Bán bậc ra của một đỉnh v (𝑑𝑒𝑔+ (v)) là số cung đi ra
khỏi nó.
• Bán bậc vào của một đỉnh v (𝑑𝑒𝑔− (v)) là số cung đi vào
nó.
• Bậc của đỉnh = (𝑑𝑒𝑔+) + (𝑑𝑒𝑔−)
• 𝑑𝑒𝑔+(𝑣)= ?
• 𝑑𝑒𝑔−(𝑣)= ?
u
v
xs
t
e
Định lý
3
Xét đồ thị vô hướng G=(V,E), tổng bậc của tất cả các đỉnh
của đồ thị sẽ bằng hai lần số cạnh của nó
deg( ) 2 | |
v V
v E
 
Định lý
3
Xét đồ thị có hướng G=(V,E), tổng bán bậc ra của tất cả các
đỉnh sẽ bằng tổng bán bậc vào của tất cả các đỉnh và bằng
số cung của đồ thị
deg ( ) deg ( ) | |
v V v V
v v E 
  
u
t
t x
v
Đường đi
3
Xét đồ thị G = . Một đường đi độ dài n từ u tới v, n là một số
nguyên dương, trong một đồ thị là một dãy:
u = x0 x1 x2  xn = v
sao cho i {0,,n-1}, (xi, xi+1) E
VD: Các đường đi từ 1 đến 5:
d1: 1 2 5
d2: 1 2 4 3 9 2 5
d3: 1 9 2 3 9 2 5
Độ dài 2
Độ dài 6
Độ dài 6
Chu trình
3
Xét đồ thị G = . Một chu trình độ dài n (n là một số
nguyên dương) là một đường đi có độ dài n với đỉnh đầu và
đỉnh cuối trùng nhau
VD: Các chu trình trong đồ thị
C1: 1 2 9 1
C2: 1 9 0 3 9 2 1
C3: 1 9 2 3 9 1 
Độ dài 3
Độ dài 6
Độ dài 5
Đường đi - Chu trình
3
• Một đường đi (chu trình) được gọi là đường đi đơn (chu
trình đơn) nếu nó không lặp lại cạnh nào.
• Một đường đi (chu trình) được gọi là đường đi sơ cấp (chu
trình sơ cấp) nếu nó không lặp lại đỉnh nào. 
VD:
d1: 1 2 9 1
d2: 1 2 4 3 9 2 5
d3: 1 9 2 3 9 2 5
C1: 1 2 9 1
C2: 1 9 0 3 9 2 1
C3: 1 9 2 3 9 1
Sự liên thông
3
• Xét đồ thị vô hướng G = . G được gọi là đồ thị liên
thông nếu luôn tồn tại đường đi giữa hai đỉnh bất kỳ của G.
Đồ thị vô hướng liên thông Đồ thị vô hướng không liên thông
Sự liên thông
3
Một đồ thị không liên thông là hợp của nhiều đồ thị con liên
thông rời nhau. Mỗi đồ thị con này được gọi là một thành phần
liên thông của đồ thị ban đầu.
Đồ thị trên có 3 thành phần liên thông
Sự liên thông
3
• Xét đồ thị vô hướng G = . G được gọi là đồ thị liên
thông nếu luôn tồn tại đường đi giữa hai đỉnh bất kỳ của G.
Đồ thị vô hướng liên thông Đồ thị vô hướng không liên thông
Biểu diễn đồ thị
3
Để biểu diễn 1 đồ thị có hướng và vô hướng, ta có thể dùng
dạng ma trận
Có 2 dạng ma trận:
• Ma trận kề
• Ma trận liên thuộc
Ma trận liền kề
3
Ma trận liền kề của đồ thị G=(V,E) ứng với thứ tự các đỉnh v1, 
v2,  , vn là ma trận cấp MxM
𝐴 = (𝑎𝑖𝑗)𝑖≤𝑗,𝑗≤𝑛∈ 𝑀(𝑛, 𝑍)
Trong đó aij là số cạnh hoặc cung nối từ vi tới vj .
Ma trận liền kề của 1 đồ thị vô hướng là ma trận đối xứng
Ma trận liền kề của 1 đồ thị có hướng là ma trận không đối
xứng
Ma trận liền kề
3
Ma trận liên thuộc
3
Ma trận liên thuộc của đồ thị có hướng G=(V,E) gồm n đỉnh, 
m cạnh (cung) là ma trận gồm n hàng tương ứng n đỉnh, m 
cột tương ứng m cạnh (cung) , A = aij với aij được định nghĩa
• Aij = 1 nếu cạnh Ei đi ra khỏi đỉnh Vi
• Aij = -1 nếu cạnh Ei đi vào đỉnh Vi
• Aij = 0 trong các trường hợp còn lại
1
4
3
2
Thành phần liên thông
3
• 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ị.
• Một thành phần liên thông của đồ thị là 1 lớp tương đương
được xác định bởi quan hệ liên kết
• Số thành phần liên thông của đồ thị là số lượng các lớp
tương đương
• Đồ thị liên thông là đồ thị chỉ có 1 thành phần liên thông
Thành phần liên thông
3
Thành phần liên thông
3
• Thuật toán xác định các thành phần liên thông trong đồ thị
(Tự tìm hiểu)
Đồ thị Euler
3
Cho đồ thị G=(V,E)
• Đường đi Euler: Đường đi đơn 
trong G đi qua mọi cạnh của nó, 
mỗi cạnh chỉ đi qua một lần được 
gọi là đường đi Euler
• Chu trình Euler: Chu trình đơn 
trong đồ thị G đi qua mọi cạnh 
của nó, mỗi cạnh chỉ đi qua một 
lần được gọi là chu trình Euler. 
Đồ thị Euler
3
Cho đồ thị có hướng G=(V,E)
• Đường đi có hướng Euler: Đường đi đơn có hướng qua 
mọi cạnh của đồ thị
• Chu trình có hướng Euler: Là chu trình đơn có hướng qua 
mọi cạnh của đồ thị
Đồ thị có chứa chu trình Euler gọi là đồ thị Euler
Đồ thị Euler
3
Chu trình Euler: a, b, c, f, e, b, d, c, a
Đồ thị Euler
3
Những đồ thị nào là đồ thị Euler
Đồ thị Euler
3
Những đồ thị nào là đồ thị Euler
Định lý Euler
3
• Đồ thị có hướng G=(V,E) là đồ thị Euler  G liên thông và
(𝑑𝑒𝑔+) = (𝑑𝑒𝑔−)
• Đồ thị có hướng G=(V,E) là đồ thị Euler  G liên thông và
deg chẵn
• Đồ thị G có chu trình Euler khi và chỉ khi G liên thông và
mọi đỉnh đều có bậc (chẵn khác 0).
• Đồ thị G có đường đi Euler khi và chỉ khi G liên thông và 
có không quá 2 đỉnh bậc lẻ.
Thuật toán tìm chu trình Euler
3
• Giả sử G = (V, E) là đồ thị vô hướng, liên thông, tất cả các 
đỉnh đều có bậc chẵn hơn nữa G là hữu hạn. Khi đó, tất cả 
các đỉnh đều có bậc lớn hơn 1.
• Gọi chu trình Euler cần tìm là C
 Chọn 1 đỉnh bất kỳ cho vào C 
 Nếu G không còn cạnh nào thì dừng.
 Chọn một cạnh nối đỉnh vừa chọn với một đỉnh kề với nó 
theo nguyên tắc: chỉ chọn cạnh cầu nếu không còn cạnh 
nào khác để chọn. Bổ sung cạnh vừa chọn và đỉnh cuối 
của nó vào C, xóa cạnh ấy khỏi G. Quay về bước 2.
Đồ thị Euler
3
Đồ thị Euler
3
Đồ thị Hamilton
3
Cho đồ thị G=(V,E)
• Đường đi Hamilton là đường đi qua tất cả các đỉnh của 
đồ thị mỗi đỉnh đúng một lần
• Chu trình Hamilton là chu trình bắt đầu từ một đỉnh v 
nào đó qua tất cả các đỉnh còn lại mỗi đỉnh đúng một 
lần rồi quay trở về v.
Đồ thị chứa chu trình Hamilton gọi là đồ thị Hamilton
Đồ thị Hamilton
3
Đồ thị trên không có chu trình Hamilton và đường đi Euler
nhưng có đồ thị Hamilton
Định lý Dirac (1952)
3
Nếu G là 1 đơn đồ thị có n đỉnh và mỗi đỉnh của G đều có
bậc nhỏ hơn n/2 thì G là 1 đồ thị Hamilton
Đồ thị Hamilton
3
Quy tắc xác định chu trình Hamilton
• Nếu G có đỉnh bậc <2 thì G không có chu trình
Hamilton
• Nếu G có đỉnh bậc =2 thì 2 cạnh kề với nó phải nằm
trong chu trình Hamilton
• Các cạnh thừa (Ngoài 2 cạnh đã chọn trong chu trình
Hamilton phải được bỏ đi trong quá trình xác định chu
trình)
• Nếu quá trình xây dựng tạo nên chu trình con, thì đồ thị
không có chu trình Hamilton
Cây
3
• 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 2 đỉnh (cây không chứa khuyên và
cạnh song song)
• Rừng là 1 đô thị gồm p thành phần liên thông trong đó
mỗi thành phần liên thông là 1 cây
Cây khung
3
• Nếu 1 cây T gồm n đỉnh với n ≥ 2 thì t chứa ít nhất 2 
đỉnh treo
• Đơn đồ thị T là 1 đồ thị vô hướng n đỉnh, các mệnh đề
tương đương sau: 
 T là một cây
 T không chứa chu trình và có n-1 cạnh
 T liên thông và có n-1 cạnh
 T liên thông và mỗi cạnh của nó đều là cây
Cây khung (Tiếp)
3
• Đơn đồ thị T là 1 đồ thị vô hướng n đỉnh, các mệnh đề
tương đương sau: (tt)
 Hai đỉnh bất kỳ của T được nối với nhau bởi đúng 1 
đường đi
 T không chứa chu trình nhưng khi thêm vào 1 cạnh bất
kỳ sẽ thu được 1 chu trình
Cây khung
3
• Vẽ tất cả các cây khung có
 4 đỉnh
 5 đỉnh
 6 đỉnh
Cây khung của đồ thị
3
• Còn được gọi là: cây bao trùm, cây tối đại.
• Spanning tree
• Cây khung của đồ thị G là một đồ thị con của G, chứa
tất cả các đỉnh của G, liên thông và không có chu trình
Cây khung nhỏ nhất
3
• Cho G=(V,E) là đồ thị vô hướng, liên thông. Mỗi cạnh
e∈E được gắn một trọng số (weight) hay chi phí (const) 
không âm được gọi là độ dài (length) của cạnh đó.
• Giả sử T = (Vt,Et) là cây khung đồ thị G. Độ dài c(T) của
cây khung T là tổng độ dài các cạnh của nó
c(T) = 𝑒∈𝐸 𝑐(𝑒)
• Một đồ thị mà cách cạnh được gán trọng số như trên
được gọi là đồ thị có trọng số
Cây khung nhỏ nhất
3
Thuật toán tìm cây khung
nhỏ nhất
3
• Thuật toán Prim
• Thuật toán Kruskal
Thuật toán Prim
3
• Cho G=(V,E) là một đồ thị liên thông có trọng số gồm n 
đỉnh
• Thuật toán xuất phát từ một cây chỉ chứa đúng một 
đỉnh và mở rộng từng bước một, mỗi bước thêm một 
cạnh mới vào cây, cho tới khi bao trùm được tất cả các 
đỉnh của đồ thị.
Thuật toán Kruskal
3
• Cho G=(V,E) là một đồ thị liên
thông có trọng số gồm n đỉnh
• Để xây dựng tập n-1 cạnh
của cây khung nhỏ nhất -, Kruskal 
đề nghị cách kết nạp lần lượt các 
cạnh vào tập đó theo nguyên tắc 
như sau:
 Ưu tiên các cạnh có trọng số nhỏ 
hơn.
 Kết nạp cạnh khi nó không 
tạo chu trình với tập cạnh đã kết 
nạp trước đó.
Thuật toán tìm đường đi ngắn
nhất
3
• Thuật toán Dijkstra
• Thuật toán Bellman-Ford (Tự tìm hiểu)
• Thuật toán Johnson (Tự tìm hiểu) .
Thuật toán Dijkstra
3
• Tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z trong đồ 
thị có trọng số. Trọng số của cạnh (i,j) là w(i,j) > 0 và 
đỉnh x sẽ mang nhãn L(x). Khi kết thúc thuật giải L(z) 
chính là chiều dài đường đi ngắn nhất từ a đến z.
• Đầu vào: Đồ thị liên thông G = (V, E) có trọng số w(i, j) 
> 0 với mọi cạnh (i, j), đỉnh a và đỉnh z
• Đầu ra: Chiều dài đường đi ngắn nhất và đường đi 
ngắn nhất
Thuật toán Dijkstra
3
• Phương pháp:
1. Gán L(a) = 0. Với mọi đỉnh x ≠ a gán L(x) = ∞. Kí hiệu T = V
2. Chọn v ∈T sao cho L(v) có giá trị nhỏ nhất. Đặt: T = T – {v}
3. Nếu z ∄ T → Kết thúc. L(z) là đường đi ngắn nhất từ a đến z. Từ z 
lần ngược theo các đỉnh được ghi nhớ ta có đường đi ngắn nhất. 
Ngược lại sang bước 4.
4. Với mỗi x ∈ T kề với v gán: 
L(x) = min{L(x), L(v) + w(v, x)} 
Nếu L(x) này thay đổi thì ghi nhớ đỉnh v cạnh x để sau này xây dựng 
đường đi ngắn nhất. (Quay về bước 2)
Thuật toán Dijkstra
3
• Ví dụ
Thuật toán Dijkstra
3
• Ví dụ
Thuật toán Dijkstra
3
• Ví dụ
Thuật toán Dijkstra
3
• Ví dụ
Thuật toán Dijkstra
3
• Tìm đường đi ngắn nhất:
Bài tập
3
• Tìm đường đi ngắn nhất: