TOÁN RỜI RẠC
GV: NGUYỄN LÊ MINH
Bộ môn Công nghệ thông tin
Chương 5: LÝ THUYẾT ĐỒ THỊ
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
Đồ 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 đó.
3
Có 2 loại đồ thị: Đồ thị có hướng – Đồ thị vô hướng
Đồ thị có hướng
Đồ thị có hướng G = (V, E) trong đó:
• E là tập hợp các cặp có thứ tự gồm hai phần tử khác
• Tập khác rỗng V là tập hợp hữu hạn các đỉnh của đồ thị
nhau của V gọi là các cung.
hướng đi từ i -> j
3
• Mỗi cạnh e∈E liên kết với 1 cặp đỉnh (i,j)∈ 𝑉2, quy định
Đồ thị vô hướng
Đồ thị vô hướng G = (V, E) trong đó:
• E là tập hợp các cặp không có thứ tự gồm hai phần tử
• Tập khác rỗng V là tập hợp hữu hạn các đỉnh của đồ thị
khác nhau của V gọi là các cạnh.
định thứ tự.
3
• Mỗi cạnh e∈E liên kết với 1 cặp đỉnh (i,j)∈ 𝑉2, không quy
Cạnh song song và khuyên
• 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’
3
được gọi là cặp cạnh song song với nhau
Các loại đồ thị
Đồ thị rỗng Đồ thị đơn Đồ thị đủ
Có tập cạnh là tập rỗng Không có khuyên và cạnh song song
3
Là đồ thị vô hướng, đơn, 2 đỉnh bất kỳ luôn kề nhau
Các loại đồ thị
Đồ thị hai phía (Đồ thị lưỡng phân)
3
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ề
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
u
cạnh e
e
v
3
Đỉnh kề
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
u
e
cung e, đỉnh v là đỉnh
t
v
cuối cung e
s
x
3
Bậc của đỉnh
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) = ?
3
Deg(0) = ?
Bậc của đỉnh
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ó.
u
e
• Bậc của đỉnh = (𝑑𝑒𝑔+) + (𝑑𝑒𝑔−)
t
v
• 𝑑𝑒𝑔+(𝑣)= ?
3
• 𝑑𝑒𝑔−(𝑣)= ?
s
x
Định lý
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ó
3
Định lý
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ị
u
t
v
x
t
3
Đường đi
Xét đồ thị G =
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:
Độ dài 2
Độ dài 6
Độ dài 6
d1: 1 2 5 d2: 1 2 4 3 9 2 5 d3: 1 9 2 3 9 2 5
3
Chu trình
Xét đồ thị G =
VD: Các chu trình trong đồ thị
Độ dài 3
Độ dài 6
Độ dài 5
C1: 1 2 9 1 C2: 1 9 0 3 9 2 1 C3: 1 9 2 3 9 1
3
Đường đi - Chu trình
• 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
3
Sự liên thông
• Xét đồ thị vô hướng G =
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
3
Sự 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 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
3
Sự liên thông
• Xét đồ thị vô hướng G =
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
3
Biểu diễn đồ thị
Để 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ề
3
• Ma trận liên thuộc
Ma trận liền kề
𝐴 = (𝑎𝑖𝑗)𝑖≤𝑗,𝑗≤𝑛∈ 𝑀(𝑛, 𝑍)
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ị có hướng là ma trận không đối xứng
3
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ề
3
Ma trận liên thuộc
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
1
• Aij = 0 trong các trường hợp còn lại
4
2
3
3
Thành phần liên thô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ị.
• 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
3
• Đồ 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
• Thuật toán xác định các thành phần liên thông trong đồ thị
3
(Tự tìm hiểu)
Đồ thị Euler
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
3
• 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
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ị
3
Đồ 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
• Đồ 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à
3
có không quá 2 đỉnh bậc lẻ.
Thuật toán tìm chu trình Euler
• 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
Nếu G không còn cạnh nào thì dừng.
3
Chọn 1 đỉnh bất kỳ cho vào C
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
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.
3
Đồ 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
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
• 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)
trong chu trình Hamilton
3
• 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
• 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 đó
3
mỗi thành phần liên thông là 1 cây
Cây khung
• 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 không chứa chu trình và có n-1 cạnh
T là một cây
T liên thông và có n-1 cạnh
3
T liên thông và mỗi cạnh của nó đều là cây
Cây khung (Tiếp)
• Đơ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
3
kỳ sẽ thu được 1 chu trình
Cây khung
• Vẽ tất cả các cây khung có
5 đỉnh
4 đỉnh
3
6 đỉnh
Cây khung của đồ thị
• Còn được gọi là: cây bao trùm, cây tối đại.
• 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
3
• Spanning tree
Cây khung nhỏ nhất
• 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
3
đượ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
• Thuật toán Prim
3
• Thuật toán Kruskal
Thuật toán Prim
• 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
3
đỉ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
• 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 đó.
3
Thuật toán tìm đường đi ngắn nhất
• Thuật toán Dijkstra
• Thuật toán Johnson (Tự tìm hiểu) ….
3
• Thuật toán Bellman-Ford (Tự tìm hiểu)
Thuật toán Dijkstra
• 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
3
ngắn nhất
Thuật toán Dijkstra
• 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)
3
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:
