Chương 4 Bài toán cây khung nhỏ nhất The Minimum Spanning Tree Problem Nội dung 4.1. Cây và các tính chất cơ bản của cây 4.2. Cây khung của đồ thị 4.3. Xây dựng tập các chu trình cơ bản của đồ thị 4.4. Bài toán cây khung nhỏ nhất 2 Cây và rừng (Tree and Forest) §Þnh nghÜa 1. Ta gäi c©y lµ ®å thÞ v« híng liªn th«ng kh«ng cã chu tr×nh. §å thÞ kh«ng cã chu tr×nh ®îc gäi lµ rõng. Nh vËy, rõng lµ ®å thÞ mµ mçi thµnh phÇn liªn th«ng cña nã lµ mét c©y. T1 T2 Rừng F gồm 3 cây T1, T2,, T3 T3 3 VÍ DỤ G1, G2 là cây G3, G4 không là cây 4 Các tính chất cơ bản của cây Định lý 1. Giả sử T=(V,E) là đồ thị vô hướng n đỉnh. Khi đó các mệnh đề sau đây là tương đương: (1) T là liên thông và không chứa chu trình; (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 nó một cạnh ta thu được đúng một chu trình. 5 Nội dung 4.1. Cây và các tính chất cơ bản của cây 4.2. Cây khung của đồ thị 4.3. Xây dựng tập các chu trình cơ bản của đồ thị 4.4. Bài toán cây khung nhỏ nhất 6 Cây khung của đồ thị Định nghĩa 2. Giả sử 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 c a b d c a b d c a d e e e G T1 T2 Đồ thị G và 2 cây khung T1 và T2 của nó 7 Số lượng cây khung của đồ thị Định lý sau đây cho biết số lượng cây khung của đồ thị đầy đủ Kn: Định lý 2 (Cayley). Số cây khung của đồ thị Kn là nn-2 . Arthur Cayley (1821 – 1895) b a c K3 a b c b c a c a b Ba cây khung của K3 8 Bài toán trong hoá học hữu cơ Biểu diễn cấu trúc phân tử: Mỗi đỉnh tương ứng với một nguyên tử Cạnh – thể hiện liên kết giữa các nguyên tử Bài toán: Đếm số đồng phân của cacbua hydro no chứa một số nguyên tử cácbon cho trước 9 methane H H propane H C C H C H H C H H H C H H C H H C H H C H H H H C H H C H H H