Bài giảng Toán rời rạc - Chương 6: Cây và cây khung đồ thị - Võ Tấn Dũng

CÂY VÀ CÂY KHUNG ĐỒ THỊ
TRƯỜNG CAO ĐẲNG CÔNG NGHỆ THÔNG TIN TP.HCM
KHOA CÔNG NGHỆ THÔNG TIN
MÔN TOÁN RỜI RẠC VÀ LÝ THUYẾT ĐỒ THỊ
CHƯƠNG 6
GV: Võ Tấn Dũng
votandung@yahoo.com
Cây và các tính chất cơ bản
Định nghĩa Cây
Cho G=(V,E) là đồ thị vô hướng. G được gọi là một Cây
(tree) nếu và nếu G liên thông và không có chu trình
đơn.
Định nghĩa Rừng
- Rừng (forest) là đồ thị mà mỗi thành phần liên thông
của nó là một cây.
Rừng
cây
Ví dụ:
c
e f
d
a b
c
e f
d
a b
c
e f
d
a b
c
e f
d
a b
G1 G2 G3 G4
G1, G2 là cây; G3, G4 không phải là cây
Định lý
Định lý: Giả sử G=(V,E) là đồ thị vô hướng n đỉnh. 
Khi đó các mệnh đề sau đây là tương đương:
• (1) T là cây;
• (2) T không chứa chu trình và có n-1 cạnh;
• (3) T liên thông và có n-1 cạnh;
• (4) T liên thông và mỗi cạnh của nó đều là cầu;
• (5) Hai đỉnh bất kỳ của T được nối với nhau bởi 
đúng một đường đi đơn;
• (6) T không chứa chu trình nhưng hễ cứ thêm vào 
một cạnh ta thu được đúng một chu trình.
Cây khung đồ thị
Giới thiệu
Cách tạo cây khung của đồ thị
Trong đồ thị liên thông G, chúng ta thực hiện loại bỏ
một cạnh nằm trên một chu trình nào đó sẽ tạo ra đồ thị G'
vẫn có tính liên thông.
Thực hiện tiếp việc loại bỏ các cạnh ở các chu trình
khác cho đến khi đồ thị T không còn chu trình nhưng vẫn
liên thông thì chúng ta thu được một cây nối tất cả các
đỉnh của G - gọi là cây khung của đồ thị.
• Ví dụ:
Đồ thị sau đây và các cây khung của nó (nó còn 
có các cây khung khác nữa)
Định nghĩa cây khung đồ thị
Định nghĩa
Cho G=(V,E) là đồ thị vô hướng, liên thông. Cây T=(V,F)
với F  E được gọi là cây khung của đồ thị G.
B
G
D
E
FA
C
H
Bài toán tìm cây khung nhỏ nhất
Cho G=(V,E) là đồ thị vô hướng, liên thông có trọng số.
Độ dài c(T) của cây khung T là tổng trọng số các cạnh của
cây:
Bài toán:
Trong số tất cả các cây khung của đồ thị G, hãy tìm ra cây
khung có độ dài nhỏ nhất - gọi là cây khung nhỏ nhất
của đồ thị.
Các bài toán thực tế ứng dụng cây khung nhỏ nhất
1- Bài toán nối mạng máy tính:
Với mạng máy tính gồm n máy đánh số từ 1 đến n. Biết
chi phí nối máy i với máy j là m(i,j) (chi phí phụ thuộc vào
độ dài cáp nối cần sử dụng). Hãy tìm cách nối mạng sao
cho tổng chi phí là nhỏ nhất.
2- Bài toán xây dựng hệ thống đường sắt:
Chúng ta muốn xây dựng một hệ thống đường sắt nối n
thành phố để hành khách từ một thành phố có thể đi đến
bất kỳ các thành phố còn lại. Yêu cầu thiết kế để chi phí
xây dựng hệ thống đường đi là nhỏ nhất.
Bài toán tìm cây khung nhỏ nhất
Thuật toán Kruskal
• Cho đồ thị vô hướng liên thông có trọng số G=(V,E). Thuật 
tóan tìm ra cây khung nhỏ nhất Tmin=(V,Emin). Các bước làm 
như sau:
Bước khởi đầu:
• Tập đỉnh của cây Tmin là tập đỉnh của đồ thị G
• Tập cạnh của cây Tmin là rỗng: Emin = 
Bước lặp: Mỗi lần lặp chọn 1 cạnh cho cây (lặp lại cho đến khi 
chọn đủ số cạnh bằng số đỉnh trừ 1)
• Xét cạnh có trọng số nhỏ nhất trong các cạnh chưa xét.
• Nếu cạnh này không tạo thành chu trình với các cạnh đã chọn 
trước đó, thì chọn nó vào cây. Ngược lại thì bỏ qua không 
chọn.
Thí dụ: Tìm cây khung nhỏ nhất của đồ thị cho trong hình dưới đây:
Bước khởi tạo. Đặt Tmin= 
Bước lặp:
• Xét cạnh (3,5) chọn vào cây.
• Xét cạnh (4,6) chọn vào cây.
• Xét cạnh (4,5) chọn vào cây.
• Xét cạnh (5,6) không chọn vào cây.
• Xét cạnh (3,4) không chọn vào cây.
• Xét cạnh (1,3) chọn vào cây.
• Xét cạnh (2,3) chọn vào cây.
Đã chọn đủ 5 cạnh, được Tmin = { (3,5) , (4,6) , (4,5) , (1,3) , (2,3) } Chính là tập cạnh của cây khung nhỏ 
nhất cần tìm.
Thuật toán Prim
• Thuật toán Prim còn được gọi là phương pháp lân cận 
gần nhất.
• Trong phương pháp này bắt đầu từ một đỉnh s tuỳ ý của 
đồ thị, đầu tiên ta nối s với đỉnh lân cận gần nó nhất, 
chẳng hạn là đỉnh y. Nghĩa là trong số các cạnh kề của 
đỉnh s, cạnh (s,y) có độ dài nhỏ nhất. 
• Tiếp theo trong số các cạnh kề với hai đỉnh s hoặc y ta 
tìm cạnh có độ dài nhỏ nhất, cạnh này dẫn đến đỉnh thứ 
ba z, và ta thu được cây bộ phận gồm 3 đỉnh và 2 cạnh.
• Quá trình này sẽ tiếp tục cho đến khi ta thu được cây 
gồm tất cả các đỉnh của đồ thị, đó chính là cây khung 
nhỏ nhất cần tìm.
Thuật toán Prim
Cho đồ thị vô hướng liên thông có trọng số G=(V,E). 
Thuật tóan tìm ra cây khung nhỏ nhất Tmin=(V,Emin). 
Các bước làm như sau:
Bước khởi đầu:
• Tập đỉnh của cây Tmin là 1 đỉnh tùy ý s: Vmin = {s}.
• Tập cạnh của cây Tmin là rỗng: Emin = 
Bước lặp: Mỗi lần lặp chọn 1 đỉnh và 1 cạnh cho 
cây (Lặp lại cho đến khi chọn hết đỉnh của đồ thị)
• Tìm ra đỉnh gần cây Tmin hiện tại nhất.
• Thêm vào cây Tmin đỉnh này, và cạnh ngắn nhất nối 
đỉnh này với cây.
Thí dụ:Tìm cây khung nhỏ nhất của đồ thị cho trong hình dưới
Bước khởi tạo. Đặt Vmin={1} , Emin = 
Bước lặp:
• Vmin={1,3} , Emin = {(1,3)}
• Vmin={1,3,5} , Emin = {(1,3),(3,5)}
• Vmin={1,3,5,4} , Emin = {(1,3),(3,5),(5,4)}
• Vmin={1,3,5,4,6} , Emin = {(1,3),(3,5),(5,4),(4,6)}
• Vmin={1,3,5,4,6,2} , Emin = {(1,3),(3,5),(5,4),(4,6),(3,2)}
Kết thúc.
Bài tập 
• Một địa đạo gồm 9 căn hầm và các đường hầm với độ dài như hình 
vẽ dưới.
a) Cần đi tham quan tất cả các đường hầm, sao cho mỗi 
đường hầm chỉ đi qua đúng một lần, thì phải trổ cửa lên 
mặt đất ở những hầm nào, để số lần phải xuống-lên mặt 
đất là ít nhất. Chỉ ra các con đường đi tham quan. Nếu 
muốn chỉ trổ duy nhất một cửa hầm mà có thể đi như 
yêu cầu, thì phải đào thêm ít nhất những đường hầm 
nào nữa?
b) Nếu chỉ yêu cầu giữa các hầm có thể đi tới nhau được. 
Hãy đưa ra phương án phải đào những đường hầm nào 
trong các đường hầm đã cho, để tổng chiều dài các 
đường hầm phải đào là nhỏ nhất. Nói rõ đã áp dụng thuật 
tóan nào.
Bài tập (tiếp theo)
Hết chương 6
Tuần sau:
ôn tập chuẩn bị thi cuối kỳ