Bài giảng Toán rời rạc ứng dụng trong tin học - Chương 4: Khái niệm cơ bản về cây

TOÁN R I R C NG D NG TRONG TIN H C

Ờ Ạ Ọ

Ụ

Ứ

KHÁI NI M C B N V CÂY

Ệ Ơ Ả

Ề

M t s khái ni m c b n

ộ ố

ơ ả

ệ

 Đ nh nghĩa:

 Cây ị

ngướ , liên thông và không có ộ ồ ị vô h

 Cây là m t đ th chu trình s c p  Cây không có c nh b i và khuyên ạ ộ  Cây là m t đ n đ th ồ ị

ộ ơ

 Ví dụ

ng 2. Cây

ươ

ơ ấ

M t s khái ni m c b n

ộ ố

ơ ả

ệ

 R ngừ

ị

 Đ nh nghĩa: ừ

ể

 R ng là m t đ th  R ng có th có nhi u thành ph n liên thông ề  M i thành ph n liên thông là m t cây

ng ộ ồ ị vô h ướ

ừ ỗ

ầ

 Ví dụ

ng 2. Cây

ươ

và không có chu trình ầ ộ

M t s khái ni m c b n

ộ ố

ơ ả

ệ

ị

ướ

ế

 Đ nh lý (Đi u ki n đ c a cây) ệ ộ ồ ị ỉ i m t đ ơ ấ

ủ ủ  N u m i c p đ nh c a m t đ th vô h ủ ng đi s c p thì G là m t cây ộ ườ

ề ọ ặ ồ ạ

ng G ộ

 SV tham kh o tài li u

luôn t n t  Ch ng minh ứ ả

ng 2. Cây

ươ

ệ

M t s khái ni m c b n

ộ ố

ơ ả

ệ

ượ ố

 Cây có g cố  Đ nh nghĩa ị  M t cây v i m t đ nh đ ọ ớ ộ  Đ nh h ng các c nh trên cây t ị

 Ví dụ

 Cùng m t cây, n u ch n g c khác nhau thì cây có g c thu ố

ế

ọ

ố

c s khác nhau

ộ ẽ

ượ

ng 2. Cây

ươ

g c đi ra ộ ỉ ạ ướ c ch n làm g c ừ ố

M t s khái ni m c b n

ộ ố

ơ ả

ệ

 Cây có g cố

 M t s khái ni m

ệ

ộ ố  Cha  Anh em  T tiên ổ  Con cháu

 Lá  Đ nh trong ỉ  Cây con  M cứ  Chi u cao ề

ng 2. Cây

ươ

M t s khái ni m c b n

ộ ố

ơ ả

ệ

 Đ nh lý Daisy Chain

ị

ng đ

ng:

T là đ th có n đ nh. Các m nh đ t ỉ

ồ ị

ề ươ

ệ

ươ

ộ

ề ầ

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, m i c nh đ u là c u ọ ạ 4. Gi a hai đ nh b t kỳ c a T luôn t n t ấ ữ s c p duy nh t ấ ơ ấ

5. T không có chu trình và T U {e} có chu trình 6. T liên thông và có n-1 c nh ạ

ng 2. Cây

ươ

i m t đ ng đi ủ ỉ ồ ạ ộ ườ

M t s khái ni m c b n

ộ ố

ơ ả

ệ

 Cây m-phân  Đ nh nghĩa

ị

m con

 Cây m-phân  Cây có g cố  T t c các đ nh trong có không quá ấ ả

ỉ

 Cây m-phân đ y đầ

 T t c các đ nh trong có không quá

m con

ấ ả

 m=2: Cây nh phân

ỉ ị

ng 2. Cây

ươ

ủ

M t s khái ni m c b n

ộ ố

ơ ả

ệ

 Cây m-phân

 Ví dụ

ầ ủ

ủ

 T1: Cây nh phân đ y đ ị  T2: Cây tam phân đ y đầ  T3: Cây t ứ

ng 2. Cây

ươ

phân (không đ y đ ) ủ ầ

M t s tính ch t c a cây

ấ ủ

ộ ố

 Tính ch t 1ấ

 Cây n đ nh (n

ỉ

2) có ít nh t 2 đ nh treo ấ

ỉ

 Tính ch t 2ấ

 Cây m-phân đ y đ v i

ầ

ủ ớ i đ nh trong có ỉ n = m.i + 1

 Tính ch t 3ấ  i = (n -1)/m  l = [(m - 1)n + 1] / m  l = (m - 1)i + 1  n = l + i

ng 2. Cây

ươ

‡

Phép duy t Cây nh phân

ệ

ị

 Li

ộ ứ ự xác đ nh, ị

c đ nh nghĩa đ quy cho các cây con ượ

 Th  3 ph

ệ

ỉ m i đ nh m t l n ộ ầ ng đ ỉ ệ ng pháp duy t cây

 Đ nh nghĩa  Duy t cây ệ t kê các đ nh theo m t th t ệ ỗ ỉ ườ ươ  Duy t ti n t ệ ề ự  Duy t trung t ệ  Duy t h u t ệ ậ ự

ng 2. Cây

ươ

(Pre-Oder) (In-Oder) ự (Post-Oder)

Phép duy t Cây nh phân

ệ

ị

 Đ nh nghĩa  Duy t ti n t

ệ ề ự 1. Duy t nút g c ố ệ 2. Duy t ti n t ệ ề ự 3. Duy t ti n t ệ ề ự

ng 2. Cây

ươ

con trái con ph i ả

Phép duy t Cây nh phân

ệ

ị

 Đ nh nghĩa

ị

 Duy t trung t ự ệ 1. Duy t trung t ự ệ 2. Duy t nút g c ố ệ 3. Duy t trung t ự ệ

con trái

ng 2. Cây

ươ

con ph i ả

Phép duy t Cây nh phân

ệ

ị

 Đ nh nghĩa  Duy t h u t ệ ậ ự 1. Duy t h u t ệ ậ ự 2. Duy t h u t ệ ậ ự 3. Duy t nút g c ố ệ

ng 2. Cây

ươ

con trái con ph i ả

Phép duy t Cây nh phân

ệ

ị

 Đ nh nghĩa

ị  Ví dụ

 Duy t ti n t ự ệ ề  A B D E C F  Duy t trung t ệ  D B E A C F  Duy t h u t ệ ậ ự  D E B F C A

ng 2. Cây

ươ

ự

Ký pháp ngh ch đ o Ba Lan ị

ả

ứ

 Cây bi u th c s h c ố ọ

ị

 Bi u di n cho bi u th c

ể  Là cây nh phân  M i nút trong bi u di n cho toán t ể ể

ễ

ể

q 2 ngôi ỗ ử

q E2 ứ

 Con trái bi u di n cho bi u th c E ễ

ể

1  Con ph i bi u di n cho bi u th c E ễ

ứ

ể

ả

 M i nút lá bi u di n cho m t toán h ng ễ

ễ ứ E1 ể

2 ạ

ng 2. Cây

ươ

ể ỗ ộ

Ký pháp ngh ch đ o Ba Lan ị

ả

 Cây bi u th c s h c ố ọ

ứ

ể

 Ví dụ

E = (2 + 3)*2 – (4 – 1)*(15/5)

ng 2. Cây

ươ

Ký pháp ngh ch đ o Ba Lan ị

ả

ể

 Cây bi u th c s h c ố ọ  Duy t cây bi u th c ứ

ứ ể  Bi u th c ti n t ứ ề ố  Bi u th c trung t ứ  Bi u th c h u tô ứ

ệ ể ể ể

ố

ng 2. Cây

ươ

ậ

Ký pháp ngh ch đ o Ba Lan ị

ả

ể

 Cây bi u th c s h c ố ọ ả

ứ  Ký pháp ngh ch đ o Ba Lan ị

(Reverse Polish Notation – RPN)  Bi u th c d ng h u t ể

 S d ng đ tính giá tr bi u th c trên máy tính

ậ ố

ừ

ứ ở ạ  Ví d : ụ 5 1 2 + 4 * + 3 – ể ị ể ứ

ử ụ

ế

ng 2. Cây

ươ

ử ụ  Tính t trái qua ph i ả  Không s d ng d u ngo c ặ ấ ử ụ  S d ng Stack (ngăn x p)

Ký pháp ngh ch đ o Ba Lan ị

ả

ể

 Cây bi u th c s h c ố ọ ả

ứ  Ký pháp ngh ch đ o Ba Lan ị

(Reverse Polish Notation – RPN)  Thu t toán tính giá tr bi u th c RPN

ộ

ệ

ị ể ứ

ộ ố

ẩ

 Đ c m t ký hi u (token)  N u ký hi u là m t s ệ  Đ y vào Stack ệ

ử

 Ng 

ạ

đ i v i 2 toán h ng

ạ

i, ký hi u là m t toán t c l ộ ượ ạ Stack L y ra 2 toán h ng t ừ ấ  Tính giá tr theo toán t ử ố ớ ị  Đ y k t qu vào Stack

ế

ẩ

ả

ng 2. Cây

ươ

ậ ọ ế

Ký pháp ngh ch đ o Ba Lan ị

ả

ể

 Cây bi u th c s h c ố ọ ả

ứ  Ký pháp ngh ch đ o Ba Lan ị

(Reverse Polish Notation – RPN)  Ví d : Tính giá tr bi u th c

ụ

ng 2. Cây

ươ

ứ ị ể 5 1 2 + 4 * + 3 -

Cây khung (Spanning Tree)

 Đ nh nghĩa

ị

ồ ị

 Cây khung c a đ n đ th G ủ ủ

 Đ th con c a G ồ ị  Ch a t ứ ấ ả

ủ

ộ ồ ị

ề

 Ví dụ

ng 2. Cây

ươ

t c các đ nh c a G ỉ  M t đ th có th có nhi u cây khung ể

Cây khung (Spanning Tree)

 Đ nh lý ị

 M t đ n đ th là liên thông khi và ch khi nó có

ồ ị

ỉ

ộ ơ cây khung  Ch ng minh

ứ

Ñôn giaûn

ng 2. Cây

ươ

Cây khung (Spanning Tree)

 Cây khung nh nh t ấ

ỏ

 Đ nh nghĩa

ị

ấ ộ ồ

ị ọ ổ ố

 Cây khung nh nh t trong m t đ th liên thông, có ỏ tr ng s là m t cây khung có t ng tr ng s trên các ố ọ ộ c nh là nh nh t ấ ạ  Đ nh lý ị

 Cho G = (V, E), X (cid:204)  e là c nh có tr ng s nh nh t n i gi a X và V\X. ỏ

ỏ

ọ

ng 2. Cây

ươ

(cid:222) V ố e là m t c nh trong cây khung nh nh t. ấ ố ữ ấ ỏ ạ ộ ạ

Cây khung (Spanning Tree)

 Cây khung nh nh t ấ

ỏ  Thu t toán Prim

ậ

 Phân ho ch t p đ nh ạ

ự

ậ

ậ ậ

ỉ ỉ

 Ch n m t đ nh ch a thu c cây mà có kho ng cách g n

 Xây d ng cây ự ộ ỉ ọ

ầ

ả

ộ

c ượ

ự  Ghép vào cây c nh ng n nh t tìm đ ấ ạ c n-1 c nh  Thu t toán d ng khi đ

cây đang xây d ng nh t ấ ắ ượ

ừ

ậ

ạ

ng 2. Cây

ươ

ỉ  T p các đ nh thu c cây đang xây d ng ộ i  T p các đ nh còn l ạ

Cây khung (Spanning Tree)

 Cây khung nh nh t ấ

ỏ  Thu t toán Prim

ậ

ồ ậ

 Tìm đ nh

 Cho T là t p đ nh g m m t đ nh x ỉ  Trong khi T có ít h n ơ n đ nh, th c hi n vi c sau ự ớ

ầ

ỉ



ệ



thêm đ nh thêm c nh ạ

u vào T uv vào cây v i ớ v ˛

T là đ nh g n ỉ

ầ u nh t ấ

ng 2. Cây

ươ

ộ ỉ ỉ ệ u trong V \ T mà g n v i T nh t ấ ỉ

ng 2. Cây

ươ

Cây khung (Spanning Tree)

 Cây khung nh nh t ấ

ỏ  Thu t toán Prim

ậ  Ph ươ

ấ ậ

ng pháp lân c n g n nh t (Gán nhãn) ầ  Kho ng cách ả

 d(v, X) = min { d(v, x) | x ˛

X } v i v ớ

ỉ

 M i đ nh v ta g n m t nhãn d

 Nhãn c a đ nh ủ ỗ ỉ

ắ

ộ

ự

ớ

 dv = d(v, T) v i T là t p đ nh c a cây đang xây d ng ỉ

 M i b

c ta tìm đ nh

ỗ ướ

ỉ

v ậ ủ u mà du = min {dv | v ˇ

 Ghép uv vào cây T  C p nh t l

ậ

ậ ạ v v i v ớ i d

ng 2. Cây

ươ

Cây khung (Spanning Tree)

 Cây khung nh nh t ấ

ỏ  Thu t toán Prim

;

ậ  Ph ươ Kh i t o  B c 1: ở ạ ướ  VT = {s}; T = ˘  ds = 0; dv = w(s, v)

VT} {uv}

 B c 3: ướ

ng pháp lân c n g n nh t (Gán nhãn) ầ ấ ậ

Tìm c nhạ  B c 2: ướ  Tìm u mà du = min {dv | v ˇ  VT = VT ¨ T = T ¨ {u}; T ” V thì d ngừ  N u Vế C p nh t nhãn ậ ậ  dv = min{ dv, w(u, v) } v i V ớ

ng 2. Cây

ươ

ng 2. Cây

ươ

Cây khung (Spanning Tree)

ỏ

ậ

 Phân ho ch t p đ nh ạ

 Cây khung nh nh t ấ  Thu t toán Kruskal ỉ  T p các đ nh liên thông v i m t đ nh đ

c ch n trong cây

ộ ỉ

ậ

ớ

ỉ

ượ

ọ

đang xét

 T p các đ nh còn l

ậ

ỉ

i ạ

 Xây d ng cây ự ọ

ạ

 Ch n 1 c nh e = uv  N u uv không liên thông v i nhau trong cây đang xây d ng

ự

ế

ớ

ạ  Thu t toán d ng khi đ

c n-1 c nh

thì ghép c nh này vào cây ừ

ượ

ậ

ạ

ng 2. Cây

ươ

ậ

Cây khung (Spanning Tree)

ỏ

 S p x p các c nh c a đ th G theo th t ủ

tăng d n ồ ị ứ ự ạ ầ

 Cây khung nh nh t ấ  Thu t toán Kruskal ậ ế ắ c a tr ng s . ố ọ ủ  Kh i t o t p c nh T = ở ạ ậ  V i m i c nh ỗ ạ

 N u các đ u mút c a ầ

ủ e không liên thông v i nhau

ế

ớ

trong T thì  Thêm e vào T.

 Cây khung nh nh t là T

ạ e l y theo th t : ấ ớ ứ ự

ng 2. Cây

ươ

ấ ỏ

ng 2. Cây

ươ

Cây khung (Spanning Tree)

 Cây khung nh nh t ấ

ỏ

 Ví d : Tìm cây khung nh nh t c a đ th sau

ấ ủ

ồ ị

ụ

ỏ

ng 2. Cây

ươ

Cây khung (Spanning Tree)

 Cây khung nh nh t ấ

ỏ  Ví d : Tìm cây khung nh nh t ấ

ụ

ỏ

ng 2. Cây

ươ

Cây khung (Spanning Tree)

 Cây khung nh nh t ấ

ỏ

 So sánh Prim và Kruskal

 Prim ch n c nh có tr ng s nh nh t liên thu c v i

ấ ớ ộ ỏ ố ọ ạ

 Kruskal ch n c nh có tr ng s nh nh t mi n là ọ

ộ ỉ

ễ ấ ố ỏ ộ ạ

 Thu t toán Prim hi u qu h n đ i v i các đ th dày

ọ m t đ nh đã thu c cây ọ không t o ra chu trình ạ

ố ớ ả ơ ồ ị ệ

ng 2. Cây

ươ

(s c nh nhi u) ậ ố ạ ề

Cây khung (Spanning Tree)

ứ

ụ

 M t s bài toán ng d ng ệ

ộ ố ố

 N i dây đi n ặ

ộ ể

ồ ầ

 Trong m t m t ph ng to đ cho N + 1 đi m, đi m ể c coi là ngu n đi n ệ đó ta n i dây c p đi n cho các n i ơ

ộ ượ ấ ẳ ố ọ ố

ệ ạ ể

ể ể i có to đ là (Xi, ạ ộ ặ ứ ể ỗ

n i c p đi n ban đ u hay gián ti p qua ầ ế

ộ

 Yêu c u đ a ra ph ươ ề

ng án n i đi n gi a các đi m đ ể ữ ể ố

ệ ổ ề

ng 2. Cây

ươ

ạ ộ đ u tiên chính là g c t a đ đ duy nh t mà t ừ ấ khác. Đi m th i trong N đi m còn l ứ Yi), là đi m đ t máy th i. M i đi m đ t máy có th ể ặ l y tr c ti p t ệ ự ế ừ ơ ấ ấ m t đi m đ t máy khác. ặ ể ư ầ m i n i đ t máy đ u có đi n và t ng chi u dài dây ọ ơ ặ ệ c n thi ế ầ t là ng n nh t. ắ ấ

Cây khung (Spanning Tree)

ụ

ộ ố  Theo thi

t tr ế ướ

ồ ự ế ừ

ế

nút ắ ạ c K tuy n đ

ầ

ượ

ự

ế

ng hai chi u tr c ti p t ề ng khác nhau không c t nhau t ệ  Bài toán : H th ng đ ườ

ả

 M t s bài toán ng d ng ứ t k , m t m ng giao thông g m N nút. Bi ạ ế ế ộ chi phí đ xây d ng đ ườ ự ể nút j. Hai tuy n đ ườ không là đ u mút. Hi n đã xây d ng đ ự ư

ệ ố ấ

ế

ọ

ự

ng đã

ườ

ẽ

ớ

c i đ n ế i đi m ể ng. ườ ng đã xây d ng đã b o đ m s đi ự l i gi a hai nút b t kỳ ch a? N u ch a, hãy ch n m t s ạ ữ ộ ố ư ng c n xây d ng thêm sao cho: tuy n đ ầ ườ ế  Các tuy n đ ườ ế xây d ng b o đ m s đi l ả

ự

ấ

ng s xây d ng thêm cùng v i các đ ả  T ng kinh phí xây d ng các tuy n đ

ng thêm vào là ít

ự i gi a hai nút b t kỳ. ạ ữ ườ

ự ự

ế

ổ nh t. ấ

ng 2. Cây

ươ