Cây bao trùm ngắn nhất lý thuyết, thuật toán và ứng dụng
i
MỤC LỤC
trang
MỤC LỤC ............................................................................................................... i
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT .............................................. iii
DANH MỤC BẢNG .............................................................................................. iv
DANH MỤC HÌNH ................................................................................................ v
MỞ ĐẦU ................................................................................................................ 1
CHƯƠNG I. GIỚI THIỆU CÂY BAO TRÙM NGẮN NHẤT ............................... 4
1.1. GIỚI THIỆU .................................................................................................... 4
1.1.1. Khái niệm về cây .................................................................................... 4
1.1.2. Cây Có Gốc ............................................................................................ 6
1.1.3. Cây m - phân .......................................................................................... 8
1.1.4. Duyệt cây nhị phân ............................................................................... 10
1.1.5. Cây tìm kiếm nhị phân .......................................................................... 13
1.1.6. Cây bao trùm ........................................................................................ 14
1.1.7. Cây bao trùm ngắn nhất ........................................................................ 15
1.1.8. Cây bao trùm trên đồ thị có trọng số ...................................................... 18
1.2. MỘT SỐ BÀI TOÁN DẪN ĐẾN CÂY BAO TRÙM ..................................... 22
1.2.1. Cây và bài toán liệt kê .......................................................................... 22
1.2.2. Vạch đường trong mạng di động ........................................................... 24
1.3. TỔNG KẾT CHƯƠNG .................................................................................. 28
CHƯƠNG II. MỘT SỐ THUẬT TOÁN TÌM CÂY BAO TRÙM NGẮN NHẤT ...... 29
2.1. THUẬT TOÁN BORŮVKA ........................................................................ 30
2.1.1. Mô tả thuật toán Borůvka song song. .................................................... 32
2.1.2. Thuật toán song song cho bước 2 .......................................................... 33
2.1.3. Thuật toán con trỏ nhảy mới ................................................................. 34
2.2. THUẬT TOÁN KRUSKAL .......................................................................... 36
2.2.1. Mô tả thuật toán .................................................................................... 36
2.2.2. Chứng minh tính đúng đắn.................................................................... 40
2.2.3. Thực hiện thuật toán ............................................................................. 41
2.3. THUẬT TOÁN PRIM .................................................................................... 42
2.3.1. Mô tả thuật toán. ................................................................................... 43
2.3.2. Độ phức tạp thuật toán ......................................................................... 48
2.3.3. Chứng minh tính đúng đắn.................................................................... 48
2.3.4. Thực hiện thuật toán ............................................................................. 49
ii
2.4 TỔNG KẾT CHƯƠNG II ............................................................................... 50
CHƯƠNG III. ỨNG DỤNG THUẬT TOÁN CÂY BAO TRÙM NGẮN NHẤT
VÀO BÀI TOÁN THIẾT KẾ ĐƯỜNG CÁP TRUYỀN HÌNH ............................. 51
3.1. TỔNG QUAN MẠNG TRUYỂN HÌNH CÁP ................................................ 51
3.1.1. Hệ thống trung tâm ............................................................................... 52
3.1.2. Mạng phân phối tín hiệu truyền hình cáp .............................................. 52
3.1.3. Thiết bị tại nhà thuê bao ...................................................................... 52
3.1.4. Cấu hình mạng truyền hình cáp ............................................................ 53
3.2. MÔ TẢ THUẬT TOÁN CÂY BAO TRÙM NGẮN NHẤT CHO BÀI TOÁN
THIẾT KẾ CÁP TRUYỀN HÌNH ......................................................................... 57
3.2.1. Phát biểu bài toán ................................................................................. 57
3.2.2. Mô tả dạng toán học của bài toán .......................................................... 58
3.2.3. Thực hiện bài toán ................................................................................ 59
3.3. THIẾT KẾ CHƯƠNG TRÌNH VÀ KẾT QUẢ THỬ NGHIỆM .................... 60
3.3.1. Thiết kế chương trình .......................................................................... 60
3.3.2. Kết quả thử nghiệm .............................................................................. 61
3.4 TỔNG KẾT CHƯƠNG III .............................................................................. 65
KẾT LUẬN VÀ KIẾN NGHỊ ............................................................................... 66
iii
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT
Tiếng Anh
Từ viết tắt
Tên đầy đủ
Diễn giải
MST
Minimum Spanning Tree
Cây khung nhỏ nhất
BST
Binary Search Tree
Cây tìm kiếm nhị phân
Multichannel Multipoint
Dịch vụ phân phối đa điểm đa
MMDS
Distribution Service
kênh
HFC
Hybrid Fiber Coaxia
Mạng truyền dẫn
FTTH
Fiber to the home
Cáp quang băng thông rộng
str
Structure
Cấu trúc
iv
DANH MỤC BẢNG
Trang
Bảng
Bảng
Bảng
Bảng
Bảng
Bảng
Bảng
Bảng
1. Minh họa thuật toán Borůvka ......................................................... 32
2. Đồ thị có cấu trúc ........................................................................... 35
3. Thuật toán Kruskal ......................................................................... 39
4. Kết quả chạy ví dụ 1....................................................................... 40
5. Minh hoạ thuật toán Prim ............................................................... 46
6. Kết quả chạy ví dụ.......................................................................... 47
7. Liệt kê thời gian chạy thuật toán .................................................... 48
8. Khoảng cách giữa các trạm FTTH .................................................. 62
v
DANH MỤC HÌNH
Trang
Hình 1. 1 Sơ đồ hình cây ......................................................................................... 4
Hình 1. 2 Cây có gốc x0 .......................................................................................... 7
Hình 1. 3 Cây có gốc ............................................................................................... 7
Hình 1. 4 Duyệt cây nhị phân................................................................................. 11
Hình 1. 5 Duyệt cây nhị phân theo trung thứ tự ..................................................... 12
Hình 1. 6 Cây bao trùm nhỏ nhất trên đồ thị phẳng ................................................ 16
Hình 1. 7 Cây bao trùm nhỏ nhất trong một đồ thị ................................................. 16
Hình 1. 8 Cây bao trùm nhỏ nhất có trọng số nhỏ nhất .......................................... 18
Hình 1. 9 Cây liệt kê hoán vị của {1, 2, 3}............................................................. 23
Hình 1. 10 Liệt kê các xâu ..................................................................................... 24
Hình 1. 11 Liệt kê các tập con ............................................................................... 24
Hình 1. 12 Mô hình mạng có hệ thống không dây.................................................. 25
Hình 1. 13 Vạch đường đi trong mạng di động ...................................................... 27
Hình 2. 1 Thuật toán siêu đỉnh thực hiện theo danh sách ....................................... 34
Hình 2. 2 cây khung nhỏ nhất của đồ thị ................................................................ 39
Hình 2. 3 Kết thúc thuật toán được cây khung nhỏ nhất ......................................... 40
Hình 2. 4 Cây khung có trọng số ........................................................................... 47
Hình 3. 1 Sơ đồ khối hệ thống truyền hình cáp ...................................................... 51
Hình 3. 2 Các cấu hình mạng HFC ........................................................................ 53
Hình 3. 3 Mạng sao truyền dẫn .............................................................................. 54
Hình 3. 4 Mạng vòng truyền dẫn ........................................................................... 54
Hình 3. 5 Mạng con phân phối............................................................................... 54
Hình 3. 6 Cấu hình FTF ......................................................................................... 55
Hình 3. 7 Cấu hình FTTH ...................................................................................... 56
Hình 3. 8 Cấu hình FTTC ...................................................................................... 56
Hình 3. 9 Cấu hình FTLA ...................................................................................... 57
Hình 3. 10 Tuyến huyện ........................................................................................ 58
Hình 3. 11 Triển khai mạng cáp tuyến huyện. ........................................................ 59
Hình 3. 12 Giao diện chương trình......................................................................... 60
Hình 3. 13 Nhập dữ liệu vào chương trình ............................................................. 62
Hình 3. 14 Kết quả chạy chương trình với thuật toán Prim .................................... 63
Hình 3. 15 Kết quả chạy chương trình thuật toán Kruskal ...................................... 63
Hình 3. 16 Bài toán nhiều đỉnh .............................................................................. 64
Hình 3. 17 Chương trình chạy thuật toán Kruskal .................................................. 65
Hình 3. 18 Chương trình chạy thuật toán Prim....................................................... 65
1
MỞ ĐẦU
1. Lý do chọn đề tài
Lý thuyết đồ thị là một lĩnh vực đã được nghiên cứu từ những năm
1857, khi nhà toán học Anh tên là Arthur Cayley dùng cây để xác định những
dạng khác nhau của hợp chất hoá học. Từ đó cây đã được dùng để giải nhiều
bài toán trong nhiều lĩnh vực khác nhau. Chẳng hạn, người ta dùng cây để xây
dựng các thuật toán rất có hiệu quả để tìm kiếm các phần tử trong một danh
sách. Cây cũng được dùng để tạo ra các mã có hiệu quả để lưu trữ và truyền
dữ liệu. Dùng cây có thể mô hình các thủ tục mà để thi hành nó cần dùng một
dãy các quyết định. Cây cũng dùng để xây dựng các mạng máy tính với chi
phí rẻ nhất cho các đường điện thoại nối các máy phân tán do có thể tìm được
cây bao trùm ngắn nhất giữa các nút mạng.
Lý thuyết đồ thị không những có nhiều ứng dụng trong thực tế mà còn
là công cụ đắc lực cho ngành công nghệ thông tin. Nó giúp cho chúng ta mô
tả một cách dễ dàng các bài toán phức tạp cụ thể, để từ đó ta có thể mã hoá
các bài toán đó vào máy tính. Ngoài ra lý thuyết đồ thị được sử dụng để giải
quyết các bài toán trong nhiều lĩnh vực khác nhau.
Cùng với sự phát triển chung của nhân loại thì trong lĩnh vực thông tin
cũng có những bước phát triển mạnh mẽ nhằm đáp ứng nhu cầu của cuộc
sống ngày nay. Các hệ thống thông tin truyền thống như thông tin vô tuyến,
thông tin hữu tuyến ngày càng có những biến đổi cả về chất lẫn lượng. Nhu
cầu thực tế yêu cầu hệ thống truyền dẫn thông tin có dung lượng lớn, tốc độ
truyền dẫn cao. Đặt ra yêu cầu cho nhà cung cấp hệ thống thông tin cũng nói
chung và các nhà cung cấp truyền hình nói riêng về vấn đề nâng cao chất
lượng phục vụ, cũng như việc triển khai lắp đặt mới một hệ thống truyền hình
cáp trong một khu vực nhỏ như cấp huyện hay trong một thành phố lớn.
2
Việc tính toán khảo sát một địa điểm mới để triển khai mới tránh lãng
phí tài nguyên cáp truyền dẫn, lãng phí nhân công và tài chính của đơn vị
cung cấp truyền hình cáp, cũng như lắp đặt các trạm truyền dẫn một cách hiệu
quả. Đòi hỏi nhà cung cấp phải tính toán đường đi cáp xuyên suốt từ trung
tâm truyền dẫn đến các điểm sử dụng thuê bao một cách ngắn nhất, tích kiệm
nhất để chánh lãng phí và đảm bảo tín hiệu truyền dẫn được ổn định.
Nhận thấy sự khó khăn mất nhiều thời gian, công sức và tài chính để
khảo sát địa điểm lựa chọn giải pháp lắp đặt hệ thống truyền hình cáp sao cho
tối ưu và tích kiệm nhất, đảm bảo tính khoa học vì vậy em đã lựa chọn đề tài
“Cây bao trùm ngắn nhất : Lý thuyết, thuật toán và ứng dụng”. để áp
dụng vào thực tế khảo sát và triển khai mới hệ thống truyền hình cáp một
cách tối ưu nhất có thể.
2. Đối tượng nghiên cứu
Đối tượng nghiên cứu của luận văn là các vấn đề về Cây bao trùm
ngắn nhất, thuật toán và các ứng dụng thực tiễn của nó.
3. Phạm vi nghiên cứu
Luận văn tập trung nghiên cứu các kiến thức có liên quan, các cơ sở lý
thuyết như: Lý thuyết về đồ thị và cây, cây bao trùm ngắn nhất, thuật toán và
các ứng dụng của cây bao trùm ngắn nhất.
4. Nhiệm vụ nghiên cứu
- Tìm hiểu những kiến thức tổng quan về cây bao trùm ngắn nhất.
- Tìm hiều ba thuật toán liên quan đến cây bao trùm ngắn nhất Borůvka,
thuật toán Kruskal, thuật toán Prim.
- Thiết kế chương trình ứng dụng vào thực tế giải bài toán thiết hệ thống
truyền hình cáp.
3
5. Những nội dung nghiên cứu chính
Bố cục của luận văn gồm phần mở đầu trình bày lý do chọn đề tài, đối
tượng và nhiệm vụ nghiên cứu của đề tài. Chương một, Tìm hiểu và trình bày
những lý thuyết cơ bản về khái niệm cây bao trùm: lịch sử ra đời và phát triển
của của cây bao trùm, khái niệm cây, các định nghĩa, định lý, tính chất, ví dụ
về cây bao trùm và cây bao trùm có trọng số bé nhất. Một số bài toán dẫn đến
cây bao trùm. Chương hai, Tìm hiều, giới thiệu ba thuật toán liên quan đến
cây bao trùm ngắn nhất Borůvka, thuật toán Kruskal, thuật toán Prim. Chương
3, Tìm hiểu lịch sử truyền hình cáp, sự phát triển của truyền hình cáp hiện
nay. Mổ ta bài toán cây bao trùm ngắn nhất cho bài toán thiết kế cáp truyền
hình. Thiết kế chương trình, và kết quả thử nghiệm.
6. Phương pháp nghiên cứu
- Phương pháp đọc tài liệu
- Phương pháp quan sát
- Phương pháp phân tích – tổng hợp lý thuyết.
- Phương pháp thực nghiệm.
4
CHƯƠNG I. GIỚI THIỆU CÂY BAO TRÙM NGẮN NHẤT
1.1. GIỚI THIỆU
Một đồ thị liên thông và không có chu trình được gọi là cây. Cây được
dùng từ năm 1857, khi nhà toán học Anh tên là Arthur Cayley dùng cây để
xác định những dạng khác nhau của hợp chất hóa học. Từ đó cây đã được
dùng để giải nhiều bài toán trong nhiều lĩnh vực khác nhau. Trong tin học cây
được dùng để tìm kiếm các phần tử trong danh sách hoặc bài toán xây dựng
các mạng máy tính với chi phí rẻ với các máy phân tán.[1]
1.1.1. Khái niệm về cây
Định nghĩa.
Cây là một đồ thị mà trong đó hai đỉnh bất kì đều được nối với nhau
bằng đúng một đường đi. [4]
a
e
b
a
b
c
a
d
d
f
c
b
g
e
Hình 1. 1 Sơ đồ hình cây
Định lý 1. Nếu T là một cây có n đỉnh thì T có ít nhất hai đỉnh treo.
Chứng minh:
Lấy một cạnh (a,b) bất kỳ của cây T. Trong tập hợp các đường đi chứa
cạnh (a,b), ta lấy đường đi từ u đến v dài nhất. Vì T là một cây nếu u ≠ v. u và v
phải là hai đỉnh treo vì nếu một đỉnh, u chẳng hạn, không phải là đỉnh treo thì u
phải là đầu mút của một cạnh (u,x), với x là đỉnh không thuộc đường đi từ u
đến v. Do đó, đường đi sơ cấp từ x đến v, chứa cạnh (a,b), dài hơn đường đi từ
5
u đến v, trái với tính chất đường đi từ u đến v đã chọn.
Ta nhận thấy rằng cây là đồ thị vô hướng đơn giản nhất, định lí 2 cho ta
một số tính chất của cây.[3]
Định lý 2. Cho đồ thị T=(V,E) có n đỉnh. Sáu mệnh đề là tương đương:
1) T là một cây.
2) T liên thông và có n1 cạnh.
3) T không chứa chu trình và có n-1 cạnh.
4) T liên thông và mỗi cạnh là cầu.
5) Giữa hai đỉnh phân biệt của T luôn có duy nhất một
đường đi sơ cấp.
6) T không chứa chu trình nhưng khi bổ sung vào một
cạnh nối hai đỉnh không kề nhau thì xuất hiện một chu
trình.
Chứng minh.
Chứng minh 12 (theo quy nạp)
Khẳng định đúng với n 1 và n 2 . Giả sử khẳng định đúng với mọi
cây T' với n 1 đỉnh khi đó T' liên thông và có n 2 cạnh.
Ta chứng minh khẳng định đúng với mọi T có n đỉnh (n 2) . Trong T
bao giờ cũng tìm được ít nhất một đỉnh treo vì trái lại sẽ tồn tại chu trình trong
T. Giả sử v1 là đỉnh treo và v1 kề v2 trong T khi đó nếu ta loại bỏ v1 và cạnh
( v1 , v2 ) khỏi T thì T sẽ có n 2 cạnh (theo giả thiết quy nạp). Vậy cây T có
n 2 1 n 1 cạnh.
Chứng minh 23 (theo phản chứng)
Giả sử T không liên thông khi đó T sẽ có k thành phần liên thông
( k 1) và giả sử rằng các thành phần liên thông đó là T1 , T2 ,..., Tk . Vì T không
6
chưa chu trình nên các thành phần liên thông đó cũng không chứa chu trình.
Gọi ni và ei tương ứng số các đỉnh và các cạnh của thành phần liên thông Ti .
Ta có ei ni 1(i 1, 2,..., k ) suy ra n1 n2 ...nk k e1 e2 ...ek n 1
(vì e1 e2 ...ek n 1 ) n1 n2 ... nk (n 1 k ) n mâu thuẫn.
Chứng minh 34
Khi loại bỏ một cạnh bất kì khỏi T thì T sẽ có n đỉnh và n 2 cạnh nên
tồn tại ít nhất một đỉnh cô lập có nghĩa là T không liên thông. Vậy mọi cạnh
trong T đều là cầu.
Chứng minh 45 (theo phản chứng)
Vì T liên thông nên giữa hai đỉnh bất kì luôn tồn tại đường đi sơ cấp và
đường đi này là duy nhất. Thật vậy giả sử tồn tại một đường đi sơ cấp khác thì
T sẽ chứa chu trình và các cạnh trên chu trình này không phải là cầu mâu
thuẫn với giả thiết.
Chứng minh 56
Dễ nhận thấy T không chứa chu trình vì nếu chứa chu trình thì sẽ tồn tại
cặp đỉnh có nhiều hơn một đường đi đơn. Giả sử u và v là hai đỉnh không kề
nhau bất kì trong T nếu ta nối u và v thì cạnh này cùng với đường đi đơn từ
u tới v tạo thành chu trình trong T và chu trình này là duy nhất. (đpcm)
Chứng minh 61(theo phản chứng)
Giả sử T không liên thông khi đó tồn tại ít nhất hai thành phần liên
thông giả sử là T1 và T2 , nối cạnh ( u , v ) với u T1 và v T2 thì trong T
không xuất hiện thêm một chu trình nào cả. Điều này mâu thuẫn với giả thiết.
1.1.2. Cây Có Gốc
Định nghĩa. Cây có hướng là đồ thị có hướng mà đồ thị vô hướng
tương ứng của nó là một cây.[1]
7
Cây có gốc là cây có hướng, trong đó có một đỉnh đặc biệt, gọi là gốc,
từ gốc có đường đi đến mọi đỉnh khác của cây.
Trong cây có gốc thì gốc x0 có bậc vào bằng 0, còn tất cả các đỉnh khác
đều có bậc vào bằng 1.
x11
x1
x5
x15
x8
x4
x0
x2
x12
x16
x9
x6
x13
x3
x10
x7
x14
x17
Hình 1. 2 Cây có gốc x0
Một cây có gốc thường được vẽ với gốc x0 ở trên cùng và cây phát triển
từ trên xuống (hình 1.2). Gốc của cây (đỉnh x0 ) gọi là đỉnh mức 0. Các đỉnh kề
với gốc được xếp ở phía dưới và gọi là đỉnh mức 1. Đỉnh ngay dưới đỉnh mức k
là đỉnh mức k +1.
Tổng quát, trong một cây có gốc x0 thì đỉnh x của cây là đỉnh có mức k
khi và chỉ khi đường đi từ đến x0 có độ dài bằng k.
Mức lớn nhất của một đỉnh có trong cây gọi là chiều cao của cây.
Cây có gốc ở hình 2 thường được vẽ như trong hình 1.3 để làm rõ mức
của các đỉnh.
x
x
x
x
x
x
x
x
x
x
x10
x13
x12
x11
x14
x15
Hình 1. 3 Cây có gốc
x16
x17
8
Trong cây có gốc, mọi cạnh đều có hướng từ trên xuống, vì vậy vẽ mũi
tên để chỉ hướng đi là không cần thiết. Xét một đường đi xuất phát từ gốc của
cây có gốc. Ta có các khái niệm sau:
Đỉnh có mức k được gọi là cha của các đỉnh mức k+1, đỉnh ở mức k+1
gọi là con của đỉnh ở mức k.
Các đỉnh có cùng cha được gọi là anh em.
Các đỉnh có mức nhỏ hơn k gọi là tổ tiên của đỉnh ở mức k.
Đỉnh ở mức lớn nhất của đường đi đó gọi là lá. Lá là đỉnh treo và không
có con.
Mọi đỉnh không phải là lá được gọi là đỉnh trong.
Cây có gốc mà mức của mọi lá sai khác nhau không quá 1 đơn vị gọi là
cây cân đối (hay cây cân bằng). Nói cách khác cây cân đối là cây mà mọi lá
đều có mức h hoặc h – 1 trong đó h là chiều cao của cây.
Với một cây tùy ý, nếu chọn một đỉnh nào đó làm gốc được cây có gốc
tương ứng. Do chọn gốc bất kỳ nên với cây có n đỉnh sẽ có n cây có gốc tương
ứng khác nhau. Có thể chứng minh được rằng, nếu chọn tâm của cây là gốc thì
được cây có gốc có độ cao nhỏ nhất.
1.1.3. Cây m – phân
Định nghĩa. Một cây có gốc T được gọi là cây m-phân nếu mỗi đỉnh
trong của T có nhiều nhất là m con.
Cây có gốc T được gọi là một cây m-phân đầy đủ nếu mỗi đỉnh trong
của T đều có m con.
Định lý 3. Một cây m-phân đầy đủ có k đỉnh trong thì có m.k 1 đỉnh
và có (m 1)k 1 lá.
9
Chứng minh. Mọi đỉnh trong của cây m-phân đầy đủ đều có bậc ra là
m, còn lá có bậc ra là 0. Vậy tổng số bậc ra của cây là m.k, từ đó số cạnh của
cây là m.k. Và do đó số đỉnh của cây là m.k 1. Gọi s là số lá thì ta có
s k m.k 1 , nên s (m 1)k 1 .
Định lý 4.
1. Một cây m-phân có chiều cao h thì có nhiều nhất là m h lá.
2. Một cây m-phân có s lá thì có chiều cao h [log ms] .
3. Một cây m-phân đầy đủ và cân đối có s lá thì có chiều cao
h [log ms] .
Chứng minh.
1) Mệnh đề được chứng minh bằng quy nạp theo h. Mệnh đề hiển nhiên
đúng khi h = 1.
Giả sử mọi cây m-phân có chiều cao h = k đều có nhiều nhất m k lá (với
h 2 ). Xét cây m-phân (cây T) có chiều cao h k 1. Bỏ gốc khỏi cây được
một rừng gồm không quá m cây con, mỗi cây con này có chiều cao không quá
k. Do giả thiết quy nạp, mỗi cây con này có nhiều nhất là m k lá. Do lá của
những cây con này cũng là lá của T, nên T có nhiều nhất là m. m k mk 1 lá.
Theo nguyên lý quy nạp, mệnh đề đúng đối với mọi cây có chiều cao
tuỳ ý.
2) s m h h [log ms]
Do cây là cân đối nên các lá có mức h hoặc h –1, vì có ít nhất một lá ở
mức h nên số lá phải nhiều hơn m h 1 Vậy:
m h1 s mh h 1 log m s h h [log ms] .
Ví dụ: Xét trò chơi gửi thư dây truyền. Ban đầu có một người nhận
được một lá thư và giả sử rằng mỗi người khi nhận được một thư hoặc sẽ sao
10
gửi thư đó cho 4 người khác hoặc là không chuyển cho ai cả. Hỏi có bao nhiêu
người nhận được thư kể cả người đầu tiên nếu không có ai nhận được nhiều
hơn một bức thư và trò chơi kết thúc khi có 100 người nhận được thư mà
không viết cho ai cả.
Giải: Biểu diễn trò chơi bằng một cây tứ phân đầy đủ, các đỉnh trong là
những người nhận được thư và sao gửi cho người khác còn lá là những người
nhận được thư mà không gửi cho ai cả. Vì có 100 người không viết thư cho ai
nên số lá của cây là s = 100, theo định lý 3 ta có 100 = (4 – 1)k + 1 thuộc số
đỉnh trong của cây là: k = 33 thuộc số đỉnh của của cây là: n = 100 + 33 = 133.
Vậy có 133 người nhận được thư.
1.1.4. Duyệt cây nhị phân
a) Định nghĩa. [3]
Trong nhiều trường hợp, ta cần phải duyệt một cách có hệ thống mọi
đỉnh của một cây nhị phân, mỗi đỉnh chỉ một lần. Ta gọi đó là việc duyệt cây
nhị phân hay đọc cây nhị phân.
Có nhiều thuật toán duyệt cây nhị phân, các thuật toán đó khác nhau
chủ yếu ở thứ tự thăm các đỉnh.
Cây nhị phân T có gốc r được ký hiệu là T( r ). Giả sử r có con bên trái
là u , con bên phải là v . Cây có gốc u và các đỉnh khác là mọi dòng dõi của u
trong T gọi là cây con bên trái của T, ký hiệu T( u ). Tương tự, ta có cây con
bên phải T( v ) của T. Một cây T( r ) có thể không có cây con bên trái hay bên
phải.
Sau đây là ba trong các thuật toán duyệt cây nhị phân T( r ). Các thuật
toán đều được trình bày đệ quy. Chú ý rằng khi cây T( x ) chỉ là một đỉnh x thì
“duyệt T( x )” có nghĩa là “thăm đỉnh x ”.
11
a
b
c
d
g
h
l
f
e
i
m
f
j
n
o
p
q
s
Hình 1. 4 Duyệt cây nhị phân
b). Thuật toán duyệt cây nhị phân
1) Thuật toán tiền thứ tự: (preorder)
1. Thăm gốc r .
2. Duyệt cây con bên trái của T( r ) theo tiền thứ tự.
3. Duyệt cây con bên phải của T( r ) theo tiền thứ tự.
Duyệt cây nhị phân T( a ) trong hình trên theo tiền thứ tự: Kết quả duyệt
cây T( a ) theo tiền thứ tự là:
a, b, d, g, l, h, e, i, m, n, c, f, j, o, p, k, q, s.
2) Thuật toán trung thứ tự: (inorder)
1. Duyệt cây con bên trái của T(r) theo trung thứ tự.
2. Thăm gốc r.
3. Duyệt cây con bên phải của T( r ) theo trung thứ tự.
Duyệt cây nhị phân T( a ) trong hình trên theo trung thứ tự: Kết quả
duyệt cây T( a ) theo trung thứ tự là:
g, l, d, h, b, m, i, n, e, a, c, o, j, p, f, q, k, s.
3) Thuật toán hậu thứ tự: (postorder)
12
1. Duyệt cây con bên trái của T(r) theo hậu thứ tự.
2. Duyệt cây con bên phải của T(r) theo hậu thứ tự.
3. Thăm gốc r.
Duyệt cây nhị phân T( r ) trong hình trên theo hậu thứ tự: Kết quả duyệt
cây T( r ) theo trung thứ tự là:
l, g, h, d, m, n, i, e, b, o, p, j, q, s, k, f, c, a.
4) Ký pháp Ba Lan
Xét biểu thức đại số sau đây:
(a+b)*(cd/2)
(1)
Ta vẽ một cây nhị phân như hình dưới đây, trong đó mỗi đỉnh trong
mang dấu của một phép tính trong (1), gốc của cây mang phép tính sau cùng
trong (1), ở đây là dấu nhân ký hiệu là *, mỗi lá mang một số hoặc một chữ đại
diện cho số.
*
+
a
b
/
c
d
2
Hình 1. 5 Duyệt cây nhị phân theo trung thứ tự
Duyệt cây nhị phân trong hình trên theo trung thứ tự là:
a + b * c d / 2
(2)
và đây là biểu thức (1) đã bỏ đi các dấu ngoặc.
Đối với cây trong hình thứ nhất, nếu duyệt theo tiền thứ tự, ta có
* + a b c / d 2
(3)
13
và nếu duyệt theo hậu thứ tự, ta có:
a b + c d 2 / *
(4)
Vì vậy, nếu ta viết các biểu thức trong đại số, trong lôgic bằng cách
duyệt cây tương ứng theo tiền thứ tự hoặc hậu thứ tự thì ta không cần dùng các
dấu ngoặc mà không sợ hiểu nhầm.
Người ta gọi cách viết biểu thức theo tiền thứ tự (tiền tố) là ký pháp Ba
Lan, còn cách viết theo hậu thứ tự (hậu tố) là ký pháp Ba Lan đảo, để ghi nhớ
đóng góp của nhà toán học và lôgic học Ba Lan Lukasiewicz (1878-1956)
trong vấn đề này.
Việc chuyển một biểu thức viết theo ký pháp quen thuộc (có dấu ngoặc)
sang dạng ký pháp Ba Lan hay ký pháp Ba Lan đảo hoặc ngược lại, có thể
thực hiện bằng cách vẽ cây nhị phân tương ứng sau đó áp dụng thuật toán
duyệt cây theo thứ tự trước; thứ tự sau như đã làm đối với biểu thức (1).
Như vậy việc tính giá trị của một biểu thức trong tin học thực hiện hai
thao tác cơ bản
(1) Chuyển đổi biểu thức dạng trung tố sang hậu tố
(2) Tính giá trị biểu thức hậu tố
1.1.5. Cây tìm kiếm nhị phân
Cây tìm kiếm nhị phân (BST) là một cấu trúc rất thuận lợi cho bài toán
tìm kiếm.
Định nghĩa. Cây tìm kiếm ứng với n khóa k1 , k2 ,...kn là cây nhị phân
mà mỗi nút đều được gán một khóa sao cho với mỗi mỗi nút k:
Mọi khóa trên cây con trái đều nhỏ hơn khóa trên nút k
Mọi khóa trên cây con phải đều lớn hơn khóa trên nút k
Cây tìm kiếm nhị phân là một cấu trúc dữ liệu cơ bản được sử dụng để
14
xây dựng các cấu trúc dữ liệu trừu tượng hơn như các tập hợp, đa tập hợp, các
dãy kết hợp.
Nếu một BST có chứa các giá trị giống nhau thì nó biểu diễn một đa tập
hợp. Cây loại này sử dụng các bất đẳng thức không nghiêm ngặt. Mọi nút
trong cây con trái có khóa nhỏ hơn khóa của nút cha, mọi nút trên cây con
phải có nút lớn hơn hoặc bằng khóa của nút cha.
Nếu một BST không chứa các giá trị giống nhau thì nó biểu diễn một
tập hợp đơn trị như trong lí thuyết tập hợp. Cây loại này sử dụng các bất đẳng
thức nghiêm ngặt. Mọi nút trong cây con trái có khóa nhỏ hơn khóa của nút
cha, mọi nút trên cây con phải có nút lớn hơn khóa của nút cha.
Việc chọn đưa các giá trị bằng nhau vào cây con phải (hay trái) là tùy
theo mỗi người. Một số người cũng đưa các giá trị bằng nhau vào cả hai phía,
nhưng khi đó việc tìm kiếm trở nên phức tạp hơn.
1.1.6. Cây bao trùm
Giả xử G = ( X, E) là đồ thị vô hướng liên thông với n đỉnh (n ≥ 2). [6]
Định lý 5.
Đồ thị vô hướng G =( X, E )với n (n ≥ 2) đỉnh có cây bao trùm khi và
chỉ khi nó liên thông.
Chứng minh.
Điều kiện cần.
Giả sử đồ thị vô hướng G =( X, E ) có cây bao trùm (H = ( X,F)), nhưng
G lại không liên thông. Khi đó x , y X không nối với nhau. Đồ thị H =
(X,F) nhận được từ G bằng cách bỏ đi một số cạnh, nên trong đồ thị H các
đỉnh x, y cũng không nối với nhau, suy ra đồ thị H không liên thông. Xẩy ra
mâu thuẫn với tính chất của cây. Do đó đồ thị G liên thông.
Điều kiện đủ.
15
Nếu đồ thị G liên thông ta tìm tất cả các cạnh, mà khi loại các cạnh này
khỏi G không làm mất tính liên thông của đồ thị.
Nếu trong G không có cạnh nào như vậy, thì G không có chu trình nên
nó chính là cây bao trùm.
Ngược lại giả sử a là một cạnh nào đó trong các cạnh đã nói ở trên, ta
xóa a khởi G và kí hiệu đồ thị bộ phận nhận được bằng G1.
Đối với G1 và các đồ thị nhận được tiếp theo ta thực hiện xóa các cạnh
tương ứng như trên cho tói khi nhận được đồ thị bộ phận H = (X,F) liên thông
và tất cả các cạnh khác khi xóa đều làm mất tính liên thông của đồ thị, nên đồ
thị bộ phận H = (X,F) là một cây bao trùm của đồ thị G. Định lý được chứng
minh.
Chứng minh điều kiện đủ là thuật toán cây bao trùm của đồ thị của đồ
thị.
1.1.7. Cây bao trùm ngắn nhất
a). Định nghĩa. Cho một đồ thị liên thông G vô hướng bao gồm n
đỉnh, mã số từ 1 đến n, và m cạnh nối hai đỉnh với nhau. Mỗi cạnh có chiều
dài cho trước. Tính liên thông của đồ thị cho biết với hai đỉnh cho trước tuỳ ý
ta luôn tìm được các cạnh gối đầu nhau để đi từ đỉnh này đến đỉnh kia. Hãy
chỉ ra một phần P của đồ thị thoả các tính chất sau: [3][4][7]
(i)
P chứa tất cả các đỉnh của G;
(ii)
P chứa một số ít nhất các cạnh của G;
(iii) P là đồ thị liên thông;
(iv)
Tổng chiều dài các cạnh của P là ngắn nhất.
Đồ thị P thoả ba tính chất (i), (ii) và (iii) được gọi là cây bao trùm của
đồ thị G. Nếu P thoả thêm tính chất (iv) thì P được gọi là cây bao trùm ngắn
nhất của G.