zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Bài giảng Lý thuyết đồ thị: Chương 11 - PGS.TS. Hoàng Chí Thành

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:73

Báo xấu

15
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Lý thuyết đồ thị: Chương 11 Cây và một số ứng dụng, cung cấp cho người đọc những kiến thức như: Khái niệm cây; Cây bao trùm; Cây bao trùm nhỏ nhất; Cây bao trùm lớn nhất; Cây phân cấp; Cây nhị phân; Cây biểu thức; Cây mã tối ưu. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết đồ thị: Chương 11 - PGS.TS. Hoàng Chí Thành

CHƯƠNG 11 CÂY VÀ MỘT SỐ ỨNG DỤNG 1
NỘI DUNG Khái niệm cây Cây bao trùm Cây bao trùm nhỏ nhất Cây bao trùm lớn nhất Cây phân cấp Cây nhị phân Cây biểu thức Cây mã tối ưu 2
11.1. KHÁI NIỆM CÂY Khái niệm cây do Cayley đưa ra vào năm 1857. Định nghĩa: Giả sử T = (V, E) là một đồ thị vô hướng. T là một cây nếu nó thỏa mãn hai tính chất sau: - liên thông, - không có chu trình. 3
VÍ DỤ 11.1 Đồ thị dưới đây là một cây. b a c d e f g Hình 11.1. Cây 7 đỉnh 4
11.1. KHÁI NIỆM CÂY (tiếp) Định lý 11.1: Cho T là đồ thị vô hướng có số đỉnh không ít hơn 2. Khi đó các khẳng định sau là tương đương: 1. T là một cây. 2. T không có chu trình và có n - 1 cạnh. 3. T liên thông và có n - 1 cạnh. 4. T không có chu trình nhưng nếu thêm một cạnh bất kỳ nối hai đỉnh không kề nhau thì có chu trình. 5. T liên thông nhưng nếu bớt đi một cạnh bất kỳ thì sẽ mất tính liên thông. 6. Chỉ có duy nhất một đường đi nối hai đỉnh bất kỳ. 5
11.1. KHÁI NIỆM CÂY (tiếp) Chứng minh: Chú ý rằng đồ thị T không có chu trình khi và chỉ khi chu số của nó bằng 0, nghĩa là: m = n - p. 1)  2) : Vì p = 1 và m = n - p suy ra: m = n - 1. 2)  3) : m = n - p, m = n - 1 cho nên p = 1. 3)  4) : p = 1, m = n - 1 suy ra: m = n - p. Vậy thì c(T) = 0, đồ thị T không có chu trình. Thêm một cạnh vào thì m tăng thêm 1 còn n, p không đổi. Khi đó chu số c(T) = m - n + p = 1. Đồ thị có một chu trình. 6
11.1. KHÁI NIỆM CÂY (tiếp) Chứng minh: 4)  5) : c(T) = 0 nên m = n - p. Phản chứng: đồ thị T không liên thông, có ít nhất hai đỉnh a, b không liên thông. Thêm cạnh (a, b) vào đồ thị vẫn không có chu trình. Mâu thuẫn với điều 4). Vậy đồ thị phải liên thông, nghiã là p = 1. Suy ra: m = n - 1. Khi bớt đi một cạnh bất kỳ, đồ thị vẫn không có chu trình. Do đó m - 1 = n - p'. Suy ra p' = 2 và đồ thị mất tính liên thông. 7
11.1. KHÁI NIỆM CÂY (tiếp) Chứng minh: 5)  6) : Đồ thị T liên thông nên có đường đi đơn nối mỗi cặp đỉnh. Giả sử cặp đỉnh a, b được nối bằng hai đường đi đơn khác nhau. Khi đó có cạnh e thuộc đường đi này nhưng không thuộc đường đi kia. Ta bỏ cạnh e này đi, đồ thị vẫn liên thông. Trái với điều 5). 8
11.1. KHÁI NIỆM CÂY (tiếp) Chứng minh: 6)  1) : Suy ra đồ thị T liên thông. Phản chứng: T có chu trình. Vậy thì giữa hai đỉnh của chu trình có thể nối bằng hai đường đơn khác nhau. Mâu thuẫn với điều 6). 9
11.2. CÂY BAO TRÙM Định nghĩa 11.2 Giả sử G là một đồ thị vô hướng. Cây T được gọi là cây bao trùm của đồ thị G nếu T là một đồ thị riêng của G. 10
VÍ DỤ 11.2 Đồ thị G: a b c d e Hình 11.2. Đồ thị có cây bao trùm Một số cây bao trùm của G: a b a b c c d e d e Hình 11.3. Hai cây bao trùm của đồ thị G 11
11.2. CÂY BAO TRÙM (tiếp) Định lý 11.2: Đồ thị vô hướng G có cây bao trùm  G liên thông. Chứng minh: : Hiển nhiên, vì cây bao trùm liên thông suy ra G liên thông. : Chọn a là một đỉnh bất kỳ trong đồ thị G. Ký hiệu: d(x) là khoảng cách giữa a và đỉnh x. Xây dựng các tập đỉnh: D0 = {a}, Di = { x  d(x) = i } với i  1. 12
11.2. CÂY BAO TRÙM (tiếp) a D0 D1 D2 ... Hình 11.4. Cách xây dựng cây bao trùm 13
11.2. CÂY BAO TRÙM (tiếp) Chú ý: Mỗi đỉnh x thuộc Di (i  1) đều có đỉnh y thuộc Di-1 sao cho (x, y) là một cạnh, vì nếu < a, ... , y, x > là đường đi ngắn nhất nối a với x thì < a, ... , y > là đường đi ngắn nhất nối a với y và y  Di-1. 14
11.2. CÂY BAO TRÙM (tiếp) Chứng minh: Lập tập cạnh T như sau: Với mỗi đỉnh x của đồ thị G, x  Di với i  1, ta lấy cạnh nào đó nối x với một đỉnh trong Di-1. Tập cạnh này sẽ tạo nên một đồ thị riêng của G với n đỉnh và n - 1 cạnh. Đồ thị riêng này liên thông vì mỗi đỉnh đều được nối với đỉnh a. Theo tính chất 3) của cây thì T là một cây. Do vậy, T là cây bao trùm của đồ thị G. 15
11.2. CÂY BAO TRÙM (tiếp) Định lý 11.3 (Borchardt): Số cây bao trùm của một đồ thị vô hướng đầy đủ n đỉnh là nn – 2. Một số thuật toán tìm cây bao trùm: - Thuật toán sử dụng phương pháp duyệt theo chiều sâu. - Thuật toán sử dụng phương pháp duyệt theo chiều rộng. 16
11.3. THUẬT TOÁN TÌM CÂY BAO TRÙM Thuật toán 11.1 (Tìm cây bao trùm bằng phương pháp duyệt theo chiều sâu) Dữ liệu: Biểu diễn mảng DK các danh sách kề của đồ thị vô hướng G. Kết quả: Cây bao trùm (V, T) của đồ thị G. 17
11.3. THUẬT TOÁN TÌM CÂY BAO TRÙM (tiếp) Thuật toán 1 procedure CBT_S (v) ; 2 begin 3 Duyet [v] := true ; 4 for u  DK[v] do 5 if ! Duyet [u] then 6 begin T := T  {(v, u)} ; CBT_S (u) end 7 end ; 18
11.3. THUẬT TOÁN TÌM CÂY BAO TRÙM (tiếp) 8 BEGIN { Chương trình chính } 9 for u  V do Duyet [u] := false ; 10 T :=  ; 11 CBT_S (z) ; { z là đỉnh tuỳ ý của đồ thị, sẽ trở thành gốc của cây } 12 END. 19
11.3. THUẬT TOÁN TÌM CÂY BAO TRÙM (tiếp)  Tính đúng đắn của thuật toán: : 1. Khi ta thêm cạnh (v, u) vào tập cạnh T thì trong đồ thị (V, T) đã có đường đi từ z tới v. Vậy thuật toán xây dựng lên đồ thị liên thông. 2. Mỗi cạnh mới (v, u) được thêm vào tập T có đỉnh v đã được duyệt và đỉnh u đang duyệt. Vậy đồ thị đang được xây dựng không có chu trình. 3. Theo tính chất của phép duyệt theo chiều sâu, thủ tục CBT_S thăm tất cả các đỉnh của đồ thị liên thông G. 20

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.