Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Toán rời rạc (Phần II: Lý thuyết đồ thị): Chương 4 - Nguyễn Đức Nghĩa

Chương 4 trình bày về bài toán cây khung nhỏ nhất (The minimum spanning tree problem). Nội dung chính gồm có: Cây và các tính chất cơ bản của cây, cây khung của đồ thị, xây dựng tập các chu trình cơ bản của đồ thị, bài toán cây khung nhỏ nhất. | Chương 4 Bài toán cây khung nhỏ nhất The Minimum Spanning Tree Problem Obtain a network, and use the same network to illustrate the shortest path problem for communication networks, the max flow problem, the minimum cost flow problem, and the multicommodity flow problem. This will be a very efficient way of introducing the four problems. (Perhaps under 10 minutes of class time.) 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 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 T3 Rừng F gồm 3 cây T1, T2,, T3 T2 VÍ DỤ G1, G2 là cây G3, G4 không là cây 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. 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 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. a b e c d a b e c d a b e c d G Đồ thị G và 2 cây khung T1 và T2 của nó T2 T1 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 . a b c a b c b c a c a b K3 Ba cây khung của K3 Arthur Cayley (1821 – 1895) Bài toán trong hoá học hữu cơ Biểu diễn cấu trúc phân tử: Mỗi | Chương 4 Bài toán cây khung nhỏ nhất The Minimum Spanning Tree Problem Obtain a network, and use the same network to illustrate the shortest path problem for communication networks, the max flow problem, the minimum cost flow problem, and the multicommodity flow problem. This will be a very efficient way of introducing the four problems. (Perhaps under 10 minutes of class time.) 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 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 T3 Rừng F gồm 3 cây T1, T2,, T3 T2 VÍ DỤ G1, G2 là cây G3, G4 không là cây 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à .