Bài giảng Toán rời rạc - Phần 8: Cây (TS. Nguyễn Viết Đông)

Cây

ễ

ạ

ế

Biên so n: TS.Nguy n Vi

t Đông

Cây

1. ĐN và tính ch tấ ấ ắ 2. Cây khung ng n nh t 3. Cây có g cố ệ 4. Phép duy t cây

2

ị

ấ Đ nh nghĩa và tính ch t

ị

Đ nh nghĩa Cây.

a)

ồ ị ượ m t cây ọ c g i là ng. G đ

b)

ộ ướ Cho G là đ  th  vô h ơ ấ ế n u G liên thông và không có chu trình s  c p.

ủ ầ ỗ

3

R ng ừ là đ  th   mà m i thành ph n liên thông c a  ồ ị ộ nó là m t cây.

ị

ấ Đ nh nghĩa và tính ch t

1 1

4 4

2 2

3 3

10 10

5 5

9 9

8 8

6 6

7 7

15 15

11 11

12 12

16 16

17 17

13 13

14 14

4

ị

ấ Đ nh nghĩa và tính ch t

ề

ướ ể ỉ ng có n đ nh. Các phát bi u sau

ủ ệ ầ Đi u ki n c n và đ . ồ ị Cho T là đ  th  vô h đây

ươ ươ là t ng đ ng:

i. T là cây. ii. T liên thông và có n­1 c nh.ạ ơ ấ

ạ

iii. T không có chu trình s  c p và có n­1 c nh . ỗ ạ

iv. T liên thông và m i c nh là m t c u.

ộ ầ

v. Gi a hai đ nh b t k  có đúng m t đ

ộ ườ ng đi s  c p

ữ ố ớ ơ ấ 5 ấ ỳ ỉ n i chúng v i nhau.

ộ ế ơ ấ vi. T không có chu trình s  c p và n u thêm vào m t

ữ ộ ề ạ ỉ c nh gi a hai đ nh không k  nhau thì có m t chu

ơ ấ trình s  c p duy nh t ấ .

ị

ấ Đ nh nghĩa và tính ch t

1 1

4 4

2 2

3 3

10 10

5 5

9 9

8 8

6 6

7 7

15 15

11 11

12 12

16 16

17 17

13 13

14 14

6

ị

ấ Đ nh nghĩa và tính ch t

ị

Đ nh nghĩa cây khung.

ồ ị ướ Cho G = (V,E) là đ  th  vô h ng.

ồ ị ủ T là đ  th  con khung c a G.

ọ c  g i  là cây  khung(hay  cây

ượ ủ ồ ị

Thu t toán tìm cây khung.

7

ế ộ N u  T  là  m t  cây  thì  T  đ ố ạ , hay cây bao trùm) c a đ  th  G. i đ i t ậ

ư ậ Breadth­first Search Algorithm .Thu t toán  u

ề ộ   tiên chi u r ng ồ ị ớ ậ ỉ Cho G là đ  th  liên thông v i t p đ nh { v1, v2, …, vn}

ỗ

ủ ướ ướ ề v1 làm con c a nó và

ứ

ạ ơ ạ

ượ ứ ỉ c các đ nh m c 2.

ấ ả ủ ớ ỉ t c  các đ nh c a i khi t

c ghép vào cây. ượ ố ủ ư thêm v1 nh  là g c c a cây r ng. c 0: B ỉ thêm vào các đ nh k   c 1:  B ớ ố v1 v i chúng.  ạ các c nh n i  ỉ ỉ ứ ữ Nh ng đ nh này là đ nh m c 1 trong cây. ọ ỉ ố ớ ướ v m c1, thêm vào các c nh  đ i v i m i đ nh  c 2:  B ề ớ v  vào cây sao cho không t o nên chu trình đ n.  k  v i  Thu đ ……………………………………………………. ế ụ Ti p t c quá trình này cho t ồ ị ượ đ  th  đ CâyT thu đ ủ ồ ị c là cây khung c a đ  th .

G.

ồ ị Ví d . ụ Xét đ  th  liên thông  l c

b

e

a

e

f

d

d

b

f

g

i

h

i

j

Ch n ọ e làm g cố

m

k

ủ ỉ Các đ nh k  v i ề ớ e là con c a  nó.

ứ ỉ b, d, f, i Các đ nh m c 1 là:

c

l

b

e

a

e

f

f

d

d

b

g

i

c

h

k

h

a

i

j

g

j

m

k

§  Thêm a và c làm con c a ủ b, §  h là con duy nh t c a  §  g và j là con c a ủ f,

§  k là con duy nh t c a

ấ ủ d,

ấ ủ i,

ứ ỉ a, c, h, g, j, k Các đ nh m c 2 là:

c

l

b

e

a

e

f

f

d

d

b

g

i

c

h

h

a

k

i

j

g

j

m

k

m

l

l và m là con c a ủ g và k

ố n Cu i cùng thêm  ươ ứ ng  ng t

ứ ỉ l, m Các đ nh m c 3 là:

)

ề ậ

ỉ Depth­first Search Algorithm ư (Thu t toán  u tiên chi u sâu ớ ậ ồ ị Cho G là đ  th  liên thông v i t p đ nh{ v1, v2, …, vn}

ố ộ ỉ

ượ ừ ỉ ự ạ ọ ườ t ghép các c nh sao

ượ ữ ớ ộ ỉ ạ c n a. N u đ ố ư ộ ườ ng đi.Ti p  ng đi v i m t đ nh còn ch a thu c đ ể ừ ng đi ch ng nào không th   ỉ ấ ả t c  các đ nh c a

ng đi và  xây d ng đ

ỉ

ượ

ườ ử ỉ ườ ủ ng đi qua t ạ ng đi này t o nên là cây khung.  ố ủ ướ ỉ c đ nh cu i cùng c a  ấ ừ ỉ  đ nh  ng đi m i xu t phát t ề ế ng đi. N u đi u  ữ ộ ỉ c thì lùi thêm m t đ nh n a trên  ng đi và th  xây

ng đi, t c là  lùi hai đ nh trên đ ớ ườ ủ ồ ị Ch n m t đ nh tùy ý c a đ  th  làm g c. Xây d ng  ằ ng đi t  đ nh này b ng cách l đ ỗ ạ ẽ ố ỉ cho m i c nh m i ghép s  n i đ nh  cu i cùng trên  ế ớ ườ đ ụ t c ghép thêm c nh vào đ ế ườ thêm đ ườ ồ ị đ  th  thì cây do đ ạ ỉ ư ế i đ nh tr N u ch a thì lùi l ườ ớ ự ườ đ ộ ườ ư này đi qua các đ nh còn ch a thu c đ đó không th  làm đ ườ đ ự d ng đ ể ứ ng đi m i.

ủ ồ ị G.

Ví dụ. Tìm cây bao trùm c a đ  th

f

d

i

j

a

g

f

h

c

e

k

h

b

k

g

j

i.ả  B t đ u ch n đ nh

ố ọ f làm g c và  ệ ủ f : g, h, k, j  ượ ạ ế ụ ỉ ắ ầ Gi ậ Thêm các h u du  c a  Lùi v  ề k không thêm đ ề h c c nh nào, ti p t c lùi v

f

d

i

j

a

g

d

f

h

e

c

e

k

h

b

k

c

i

g

j

a

b

ứ và lùi v  ề f.

ạ ậ ệ ủ f : d, e, c, a

ứ ủ

§ Thêm i làm con th  hai c a  ủ h § L i thêm các h u du  c a  § Lùi v  ề c và thêm b làm con th  hai c a nó .  §Cây thu đ

ủ ồ ị ượ c là cây khung c a đ  th  đã cho

ị

ấ Đ nh nghĩa và tính ch t

ị

ắ

ố

ủ ố ạ ấ c g i là

ấ ấ

ấ . Đ nh nghĩa Cây khung ng n nh t ọ ồ ị   Cho G là đ  th  có tr ng s . Cây khung T c a G  ắ ắ ượ ọ i đ i ng n  cây khung ng n nh t (cây t đ ố ể ắ nh t,cây bao trùm ng n nh t, cây khung t i ti u)  ỏ ượ ủ ế n u nó là cây khung c a G mà có tr ng l ng nh   nh t.ấ

15

ọ

ắ

ấ Cây khung ng n nh t

ắ

ậ ậ

ấ Thu t toán tìm cây khung ng n nh t a)Thu t toán Kruscal

ồ ị ọ ỉ Cho G là đ  th  liên thông, có tr ng s , ố n đ nh.

ướ ế ắ ấ ọ Tr ạ c  h t  ch n  c nh  ng n  nh t e1  trong  các c  1.

ướ B c nhạ

ủ c a G.

ướ ế ạ ọ Khi đã ch n ọ k c nh ạ e1,e2,…ek thì ch n ti p c nh B

c 2.  ắ ạ ấ ạ ủ i  c a  G  sao  cho

ek+1  ng n  nh t  trong  các  c nh  còn  l không

16

ạ ọ ướ ớ ạ t o thành chu trình v i các c nh đã ch n tr c.

ướ ừ Ch n đ ạ ọ ủ n­1 c nh thì d ng. B c 3.

ắ

ấ Cây khung ng n nh t

6

d

u

a

3

1

4

b

6

8

c

17

4

ắ

ấ Cây khung ng n nh t

a

1

S1

d

a

u

b

6 1 4

3

b

6

8

c

18

4

ắ

ấ Cây khung ng n nh t

d

a

u

1

d

3

u

a

b

6 4

1

3

b

6

8

4

S2

c

19

ắ

ấ Cây khung ng n nh t

d

a

u

3

1

d

4

a

u

b

6 4

1

3

b

6

8

4

S3

c

20

ắ

ấ Cây khung ng n nh t

d

a

u

3

1

d

4

a

u

b

6

6 1 4

3

b

6

8

4

S4

c

c

21

ậ

Thu t toán Krusal

1

8

A

B

3

5

C

3

4

F

1

1

6

D

E

2

AE DC AC ED BD AF AD BC FE AB

2 3 3 4 5 6 8 1

22

1 1 0. S0={}

ậ

Thu t toán Krusal

1

8

A

B

3

5

C

3

4

F

1

1

6

D

E

2

AE DC AC ED BD AF AD BC FE AB

2 3 3 4 5 6 8 1

1. S1=S0 + AE = {AE}

23

1 1 0. S0={}

ậ

Thu t toán Krusal

1

8

A

B

3

5

C

3

4

F

1

1

6

D

E

2

AE DC AC ED BD AF AD BC FE AB

1. S1= {AE}

2. S2=S1 + DC = {AE,DC}

24

1 1 1 2 3 3 4 5 6 8

ậ

Thu t toán Krusal

1

8

A

B

3

5

C

3

4

F

1

1

6

D

E

2

AE DC AC ED BD AF AD BC FE AB

3. S3= {AE,DC,AC}

4. S4=S3 + BD= {AE,DC,AC,BD}

25

1 1 1 2 3 3 4 5 6 8

ậ

Thu t toán Krusal

1

8

A

B

3

5

C

3

4

F

1

1

6

D

E

2

AE DC AC ED BD AF AD BC FE AB

4. S4= {AE,DC,AC,BD} 5. S5=S4 + AF= {AE,DC,AC,BD,AF}

26

1 1 1 2 3 3 4 5 6 8

ậ

Thu t toán Krusal

1

A

B

3

C

3

F

1

1

D

E

Kết luận: S5= {AE,DC,AC,BD,AF}

là cây bao trùm tối tiểu cần tìm

Trọng lượng: 9

27

Ví dụ

A

1 1

7

1 0

B

G

D

8

9

3

5

E

1 0

1 2

8

4

C

F

28

ắ

ấ Cây khung ng n nh t

ắ

ậ

ấ Thu t toán tìm cây khung ng n nh t

ậ b)Thu t toán Prim.

ọ ỉ ể ấ ỳ v1 đ  có cây ỉ ồ T1  ch  g m 1

c 1ướ . Ch n 1 đ nh b t k   B ỉ đ nh.

ọ ế ọ Tk thì ch n ti p cây c 2ướ . Khi đã ch n cây

ắ ấ ạ ek+1.  Trong  đó  ek+1  là  c nh  ng n  nh t

B Tk+1  =  Tk(cid:0) trong

29

ạ ộ ầ các c nh có m t đ u mút thu c ầ ộ Tk và đ u mút kia

ọ ượ c cây Tn thì d ng.ừ không thu c ộ Tk c 3ướ . Ch n đ B

ắ

ấ Cây khung ng n nh t

ắ

ậ

ấ Thu t toán tìm cây khung ng n nh t

3

6

d

u

a a

4

1

4

b

6

8

c

30

ắ

ấ Cây khung ng n nh t

3

6

d

a

u

4

1

4

b

6

8

T1

c

c

31

ắ

ấ Cây khung ng n nh t

d

3

6

d

a

u

6

4

1

4

b

6

8

T2

c

c

32

ắ

ấ Cây khung ng n nh t

3

d

u

3

6

d

a

u

6

4

1

4

b

6

8

T3

c

c

33

ắ

ấ Cây khung ng n nh t

3

d

u

4

3

6

d

a

u

b

6

4

1

4

b

6

8

T4

c

c

34

ắ

ấ Cây khung ng n nh t

3

d

a

u

4

1

3

6

d

a

u

b

6

4

1

4

b

6

8

T5

c

c

35

ậ

Thu t toán Prim

1

8

A

B

3

5

C

3

4

F

1

1

6

D

E

2

36

ậ

Thu t toán  Prim

1

8

A

B

3

5

C

3

4

F

1

1

6

D

E

2

37

ậ

Thu t toán Prim

1

8

A

B

3

5

C

3

4

F

1

1

6

D

E

2

38

ậ

Thu t toán Prim

1

8

A

B

3

5

C

3

4

F

1

1

6

D

E

2

39

ậ

Thu t toán  Prim

1

8

A

B

3

5

C

3

4

F

1

1

6

D

E

2

40

ậ

Thu t toán Prim

1

8

A

B

3

5

C

3

4

F

1

1

6

D

E

2

41

ậ

Thu t toán Prim

1

8

A

B

3

5

C

3

4

F

1

1

6

D

E

2

Cây T5 = {AC, AE,CD,AF,DB} là cây bao trùm tối tiểu cần tìm với w(T5) = 9

42

Ví dụ

A

1 1

7

1 0

B

G

D

8

9

3

5

E

1 0

1 2

8

4

C

F

43

ắ

ấ Cây khung ng n nh t

ậ ắ

ề Đ  thi 2004 ấ Hãy trình bày thu t toán tìm cây khung ng n nh t

ứ ạ ứ ạ ư ủ c a G ch a c nh 58 nh ng không ch a c nh 26

2

9

2

1

3

3

14

11

7

4

1

4

6

5

5

6

8

12

9

8

7

13

10

44

ắ

ấ Cây khung ng n nh t

Gi § Đ t  G’=  G  ­26  thì  cây  khung  ph i  tìm  là

iả ặ ầ

ả ở

ụ ạ

trong  G’.  ư Đ u  tiên  ch n  c nh  58  sau  đó  áp  d ng  Kruscal  nh   thông th ọ ngườ

2

9

3

1

2

7

2

9

2

1

3

1

4

4

14

11

7

6

5

4

1

4

6

5

6

8

5

6

8

8

9

7

12 9

8

7

10

13

10

45

Cây có g cố

ộ ỉ ộ ọ ủ ọ

ị Đ nh nghĩa. Cho T là m t cây. Ch n m t đ nh

r c a cây g i là

ườ ơ ấ ấ ừ ố ớ g c . ố Vì có đ ng đi s  c p duy nh t t g c t i

ủ ồ ị ỗ ỉ ị ướ m i đ nh c a đ  th  nên ta đ nh h ỗ ạ ng m i c nh là

ướ ừ ố ớ ố h ng t ộ  g c đi ra . Cây cùng v i g c sinh ra m t

ộ

ố r thì deg­(r) = 0,

ọ ỉ

ả

ố

Trong m t cây có g c  ớ deg­(v) =1v i m i đ nh không ph i là g c.

46

ướ cây có g cố ồ ị đ  th  có h ọ ng g i là

Cây có g cố

ượ ọ ứ (level 0).

ướ ố

ị Đ nh nghĩa Cho cây có g c ố r. § G c ố r đ ỉ đ nh m c 0  § Các đ nh k  v i g c

c g i là  ề ớ ố r đ ượ ế ở c x p phía d i g c và

ỉ đ nh m c

ướ ỉ ỉ i  đ nh

ỉ ọ g i là  ỉ ứ ọ

ng đi t g c đ

ủ

ộ

ỉ

là m c cao nh t c a các đ nh.

47

ế …… ừ ố r đ n ế v qua k cung. ấ ủ ườ ứ ứ 1(level 1). § Đ nh  sau  c a  đ nh  m c  1(x p  phía  d ứ ủ ứ ỉ đ nh m c 2.      m c1)g i là  § Level (v) = k (cid:0) § Đ  cao c a cây

Cây có g cố

­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­level 0

---------------------------------------level 1

---------------------------------------------­level 2

-------------------------------------------------­level 3

---------------------------------------------level 4

48

Cây có g cố

ị Đ nh nghĩa Cho cây có g c ố r

a) N u ế uv là m t cung c a  con c a uủ . ọ

ượ cha c a ủ ủ T thì u đ ọ c g i là

ộ v, còn v g i là

ỉ ỉ lá(hay  đ nh  ngoài ỉ ).  Đ nh

ả ọ ọ b) Đ nh  không  có  con  g i  là  ỉ đ nh trong không ph i là lá g i là .

c) Hai đ nh có cùng cha g i là

49

ọ ỉ anh em.

Cây có g cố

ị Đ nh nghĩa Cho cây có g c ố r

ườ ọ ế d) N u có đ ng đi v1v2…vk thì v1, v2,.., vk­1 g i là

ọ tiên c a vkủ ậ h u du ổ t ệ c a ủ v1, v2,.., vk­1. . Còn vk g i là

e) Cây  con  t

ạ ỉ ố ấ ả v  là  cây  có  g c  là v  và  t t  c   các

50

ọ ậ i  đ nh  ỉ đ nh khác là m i h u du  c a ệ ủ v trong cây T đã cho.

Cây có g cố

ị Đ nh nghĩa Cho T là cây có g c.ố

ế ỗ ỉ cây  k­phân  n u  m i  đ nh  c a ủ T  có

ượ a) T  đ ề ọ c  g i  là  ấ nhi u nh t là k con.

b) Cây 2­phân đ

ượ ọ c g i là ị cây nh  phân .

c) Cây  k­phân  đ  ủ là  cây  mà  m i  đ nh  trong  có  đúng

ọ ỉ k

con.

d) Cây k­ phân v i đ  cao   m c

ượ ọ ế c g i là cân đ i ố n u các

51

ớ ộ h đ ề ở ứ h ho c ặ h – 1 . lá đ u

Cây có g cố

1 1

4 4

2 2

3 3

10 10

5 5

9 9

8 8

6 6

7 7

15 15

11 11

12 12

16 16

17 17

13 13

14 14

52

Cây có g cố

ị

Đ nh nghĩa

ễ

i

ầ ượ ượ ể ể r. Ta có th  bi u di n  ạ r  là  TL  và  TR  cây con bên trái và cây con ố ị Cho T là cây nh  phân có g c là  ẽ ướ ớ i  v i  hai  cây  con  t ọ c g i là

ư T  nh   hình  v   d ,chúng l n l t đ bên ph iả  c a ủ T.

r

53

TL TR

Cây có g cố

ườ ộ ườ

ị Đ nh nghĩa ộ Đ  dài đ

ng đi ngoài

ị Cho T là cây nh  phân ng đi trong và đ  dài đ đủ.

ườ ấ ả ứ ủ ộ a) Đ   dài  đ ng  đi  trong t  c   các  m c  c a

ệ ỉ các đ nh trong, ký hi u IP( ổ là  t ng  t T).

ấ ả ứ ủ ộ b) Đ   dài  đ ổ là  t ng  t t  c   các  m c  c a

54

ườ ng  đi  ngoài  ệ các lá, ký hi u EP( T).

Cây có g cố

1

IP(T) = ?

2

3

EP(T) = ?

7

5

4

6

10

8

11

9

55

Cây có h

ngướ

ị

Đ nh lí

ỉ ị Cho T là cây nh  phân đ  v i ủ ớ k đ nh trong và s lá.

s = k+1 và EP=IP+2k

56

Ta có:

Cây có h

ngướ

ị

Đ nh nghĩa

ị Cho T là cây nh  phân không đ . L p ủ ậ T’ là cây có

i.

ượ ằ đ c b ng cách sau:

ii.

ỗ Thêm vào m i lá c a ủ T hai con.

ộ ỉ ế v là đ nh trong c a ủ T mà ch  ỉ

IP(T) :=IP(T’)& EP(T):=EP(T’)

57

ặ ộ Thêm vào v m t con n u  có m t con. Ta đ t:

ệ

Phép duy t cây(Tree travesal)

ị

Đ nh nghĩa

ủ

ệ

ấ

là li

t kê t

ỉ ộ

ỗ

ệ Duy t cây  t các đ nh c a cây  ứ ự ộ theo m t th  t  nào đó thành m t dãy, m i  ộ ầ . ệ ấ ỉ ỉ đ nh ch  xu t hi n m t l n

58

ệ

Phép duy t cây

ề

ứ ự

ệ Phép duy t  ti n th  t (Preoder traversal)

ố r.

ề

ế 1. Đ n g c  2. Dùng  phép  duy t  ti n  th   t

ệ   đ   duy t  ừ   trái

ứ ự ể ệ ồ các cây con T1 r i cây con T2  …t sang ph iả .

59

Preorder Traversal:   J E A H T M Y

Visit first.

ROOT

‘J’

‘T’

‘E’

‘M’

‘Y’

‘A’

‘H’

Visit left subtree second

Visit right subtree last

60

Preorder Traversal:   J E A H T M Y

Visit first.

ROOT

‘J’

‘T’

‘E’

‘M’

‘Y’

‘A’

‘H’

Visit right subtree in Preorder

61

Visit left subtree in Preorder

ệ

Phép duy t cây

ệ ậ

ứ ự

Phép duy t h u th  t (Posoder traversal).

ệ ậ

1. Dùng phép duy t h u th  t

ứ ự ể ầ ượ  đ  l n l ừ

t    trái  sang

T1,  T2,….  t

ố r.

ệ duy t  cây  con  ph i.ả ế 2. Đ n g c

62

Postorder Traversal: A H E M Y T J

Visit last

ROOT

‘J’

‘T’

‘E’

‘M’

‘Y’

‘A’

‘H’

Visit left subtree first

Visit right subtree second

63

Postorder Traversal: A H E M Y T J

Visit last

ROOT

‘J’

‘T’

‘E’

‘M’

‘Y’

‘A’

‘H’

Visit right subtree in Postorder

64

Visit left subtree in Postorder

ệ

Phép duy t cây

ệ

cây nh  ị

cho

ứ ự Phép duy t trung th  t phân (Inorder traversal)

ệ

1. Duy t cây con bên trái

TL theo trung th  ứ

ố r.

ệ

ả

ứ ự.

.ự t ế 2. Đ n g c  3. Duy t cây con bên ph i theo trung th  t

65

Inorder Traversal:  A E H J M T Y

Visit second

ROOT

‘J’

‘T’

‘E’

‘M’

‘Y’

‘A’

‘H’

Visit left subtree first

Visit right subtree last

66

Inorder Traversal:  A E H J M T Y

Visit second

ROOT

‘J’

‘T’

‘E’

‘M’

‘Y’

‘A’

‘H’

Visit left subtree in Inorder

Visit right subtree in Inorder

67

ệ

Phép duy t cây

1 1

preoder

4 4

2 2

3 3

10 10

5 5

9 9

8 8

6 6

7 7

15 15

11 11

12 12

16 16

17 17

13 13

14 14

Preoder:1,2,5,11,12,13,14,3,6,7,4,8,9,10,15,16,17

68

ệ

Phép duy t cây

1 1

posoder

4 4

2 2

3 3

10 10

5 5

9 9

8 8

6 6

7 7

15 15

11 11

12 12

16 16

17 17

13 13

14 14

Posoder:11,12,13,14,5,2,6,7,3,8,9,15,16,17,10,4,1

69

ệ

Phép duy t cây

...

r r

b b

a a

Inoder

e e

c c

d d

g g

i i

f f

h h

n n

j j

m m

k k

p p

t t

u u

s s

q q

70

Inoder :p,j,q,f,c,k,g,a,d,r,b,h,s,m,e,i,t,n,u

ủ

ể

ị

ứ Cây nh  phân c a bi u th c

G cố

‘-’

INORDER TRAVERSAL: 8 - 5 có giá trị 3

PREORDER TRAVERSAL:        - 8 5

POSTORDER TRAVERSAL: 8 5 -

71

‘8’ ‘5’

ị

ị ị ứ là cây nh  phân mà

ễ ộ ở

ớ

là cây con t

ấ ả ủ ộ ỉ

ể

Đ nh nghĩa ể ủ Cây nh  phân c a bi u th c  ể ế ố ượ ỗ c bi u di n b i m t lá. 1.  M i bi n s  đ ộ ễ ể ỗ ỉ 2.  M i đ nh trong bi u di n m t phép toán v i các  ạ ỉ ố i đ nh  y. thành t 3. Cây con bên trái và bên ph i c a m t đ nh trong  ể bi u di n cho bi u th c con, giá tr  c a chúng là  ạ ố ủ thành t con.

72

ụ ị ủ ứ ễ ố  mà ta áp d ng cho phép toán t i g c c a cây

ủ

ể

ị

ứ Cây nh  phân c a bi u th c

‘*’ ‘*’

‘3’ ‘3’

‘+’  ‘+’

‘2’ ‘2’ ‘4’ ‘4’

ế

ả K t qu ?

( 4 + 2 ) *  3 =  18

73

ủ

ể

ị

ứ Cây nh  phân c a bi u th c

‘*’

‘3’

‘+’

‘2’ ‘4’

ạ

D ng trung t

ố ề ố ậ ố , h u t ?

, ti n t

74

ủ

ể

ị

ứ Cây nh  phân c a bi u th c

‘*’

‘3’

‘+’

Infix:          ( ( 4 + 2 ) * 3 )

‘2’ ‘4’

ừ ả

ph i sang trái

Prefix:  *  +  4  2  3    Ký pháp Ba lan  : t

ừ

Postfix:  4  2  +  3  *  Ký pháp BL đ o : ả t

ả  trái sang ph i 75

ả

i thích

Gi ứ

ể

ể

ủ

ứ ằ

ề

ể

ph i sang trái:

ự ắ ầ ừ

ộ

ứ ừ ả ặ ả  bên ph i, khi g p m t phép toán

ượ

ự

ệ

ố

ả

ả

76

ể Đ  có bi u th c theo ký pháp Ba lan, ta  duy tệ ị ệ cây nh  phân c a bi u th c b ng phép duy t ứ ự . ti n th  t ệ Th c hi n bi u th c t B t đ u t thì phép toán này đ c th c hi n cho 2 thành t ố ế ngay bên ph i nó, k t qu  này là thành t   cho

ế

phép toán ti p theo.

ả

i thích

Gi ứ

ể

ể

ượ

c,

ể

ứ ằ

ứ ừ

ả

trái sang ph i: ộ

ặ

bên trái, khi g p m t phép toán

ự ệ ả

ố

ố  cho

77

ế

Đ  có bi u th c theo ký pháp Ba lan ng ta ị ệ ủ duy t cây nh  phân c a bi u th c b ng phép ứ ự ệ ậ . duy t h u th  t ể ệ ự Th c hi n bi u th c t ắ ầ ừ B t đ u t thì ượ phép toán này đ c th  hi n cho 2 thành t ế ngay bên trái nó, k t qu  này là thành t phép toán ti p theo.

Ví dụ

‘*’

‘/’

‘-’

‘3’ ‘5’

‘+’

‘8’

‘2’ ‘4’

ả ủ

ế

K t qu  c a infix, prefix, postfix?

78

‘*’

‘/’

‘-’

‘8’ ‘5’ ‘3’

‘+’

( ( 8 ­ 5 ) * ( ( 4 + 2 ) / 3 ) )

Infix:

Prefix:

* ­ 8 5  / + 4 2 3

Postfix:

8 5 ­  4 2 + 3 / *

79

‘2’ ‘4’

‘*’

‘/’

‘-’

‘8’ ‘5’ ‘3’

‘+’

( ( 8 ­ 5 ) * ( ( 4 + 2 ) / 3 ) )

Infix:

‘2’ ‘4’

ệ ừ ả

ự

Th c hi n t

ph i sang

Prefix:

* ­ 8 5  / + 4 2 3

ệ ừ

ự

Th c hi n t

Postfix:

8 5 ­  4 2 + 3 / *

trái sang 80

Inorder  Traversal:

(5 + 1) / (4 ­ 2) = 3

Print second

ROOT

‘/’

‘-’

‘+’

4

2

5

1

Print left subtree first

Print right subtree last

81

Preorder  Traversal:

/+ 5 1 – 4 2

=/+51 2 = /62

Print first

=3

ROOT

‘/’

‘-’

‘+’

4

2

5

1

Print left subtree second

Print right subtree last 82

Postorder  Traversal:

5 1 + 4 2 – = 6 4 2 –/

Print last

/= =6 2 / =3

ROOT

‘/’

‘-’

‘+’

4

2

5

1

Print left subtree first

Print right subtree second

83

Cây khung có h

ngướ

ị

Đ nh nghĩa

ồ ị

ướ

Cho G =(V,E) là đ  th  có h

ế

ng và  ủ

ướ

ướ

ủ

ng(hay cây có h

i đ i)

ồ ị   T = (V,F) là đ  th  con khung c a G. N u  ọ cây khung có  ng thì T g i là  T là cây có h ố ạ  c a G. ướ ng t h

84

Cây khung có h

ngướ

ồ ị

ậ ế

Matr n Kirchhoff ( G không khuyên) ướ a) N u G là đ  th  có h

ng thì K(G) =(kij)

=

khi i

j

i deg ( )

= (cid:0)

k

ij

- (cid:0) (cid:0)

khi i

j

trong  đó  Bij  là  s  ố ừ

cung đi t

ế  i đ n j

B ij

ồ ị

ế

b) N u G là đ  th  vô h

ng thì K(G) =(k

ij)

ướ =

- (cid:0) (cid:0) (cid:0)

khi i

j

= (cid:0)

k

ij

(cid:0)

trong  đó  Bij  là  s  ố ừ

cung đi t

ế  i đ n j

khi i

j

i deg( ) B ij

85

- (cid:0) (cid:0)

1

2

3

4

5

- -

- -

-

1 2 0 1 0

0 1 1 0 0

1 1 1 3 0

0 0 0 1 1

2 � � 0 � � 0 � 1 � � -� 1

� � � � � � � �

86

- - -

Cây khung có h

ngướ

ị

Đ nh lý

ặ ầ

ồ ị ậ ằ K(G) b ng cách xoá dòng q ượ ừ c t

ụ  Cho G là đ  th  không khuyên. Đ t Kq(G) là ph n ph   ủ c a kqq(Ma tr n có đ ộ và c t q).

ố ướ ằ ỉ ố ng trong G có g c là đ nh q b ng

87

S  cây khung có h detKq(G).

Đ  thiề

ề

Đ  thi 2003 ồ ị Ø Cho đ  th  có h ậ ở

ớ

ủ

ố

ỉ

a) Tìm s  liên thông đ nh c a

G

ồ ị

b) G có là đ  th  Euler không?

ạ

ố

T i sao? ố c)  Tìm  s   cây  có  h

i

0 1 0 1 0 � � 0 0 1 1 0 � � 0 0 0 1 0 � 1 1 0 0 1 � � 1 0 0 0 0 �

� � � � � � � �

ướ ỉ

ố

ng  t đ i c a G có g c là đ nh 1

88

ạ ủ ẽ

d) V  các cây trong câu c)

ị ướ ng G = (V,E) v i V={1,2,3,4,5} xác  ề đ nh b i ma tr n k  sau:

Đ  thiề

...

1

2

3

4

5

89

Đ  thiề

Gi

iả

(cid:0) ệ

ể ỉ ồ ị ộ

ượ ừ c t ề ớ ộ ỉ ồ ỉ ẫ ế ấ

ế ớ a) V i A   G   V ký hi u G­A đ  ch  đ  th  có đ ằ b ng cách xoá các đ nh thu c A và các cung k  v i  nó.Ta th y  G ­ A v n liên thông n u A ch  g m m t  ỉ đ nh. G ­ A không liên thông n u

ậ  A ={1,4}. V y v(G) = 2 ằ

b)

90

G liên thông và cân b ng nên G là Euler.

Đ  thiề

Gi

iả

ủ ậ ậ c)Ma tr n Kirchhoff c a G là ma tr n sau

- -

- -

-

1 2 0 1 0

0 1 1 0 0

1 1 1 3 0

0 0 0 1 1

2 � � 0 � � 0 � 1 � � -� 1

� � � � � � � �

91

- - -

Đ  thiề

...

1

1

0

- -

1

1

0

=

)

K G ( 1

-

1

0

3

1

0

0

1

2 � � 0 � � � 0 �

� � � � � �

92

- -

Đ  thiề

...

2

1

=

det

)

0

1

1 - = 1

4

K G ( 1

- -

1

0

3

ậ

ướ

ố ạ

V y G có 4 cây có h

ng t

i đ i .

Đó là các cây sau đây

93

-

Đ  thiề

...

1

2

3

4

5

94

Đ  thiề

...

1

2

3

4

5

95

Đ  thiề

...

1

2

3

4

5

96

Đ  thiề

...

1

2

3

4

5

97

Đ  thiề

ề

Đ  thi 2001

7

5

12

4

6

11

15

9

2

1

3

8

10

98

ị Xét cây nh  phân

Đ  thiề

ề

Đ  thi 2001

ệ ứ ự ữ ứ ự

ị ủ gi a  (trung  th   t ).  Có  ứ ự ệ

a)  Hãy  duy t  cây  theo  th   t ề ậ nh n xét gì v  giá tr  c a các khoá khi duy t theo th  t gi a.ữ

ầ ượ ẫ t các khoá 13,14 vào cây mà v n duy

99

ượ ậ b) Hãy chèn l n l trì đ c nh n xét trên.

Đ  thiề

Gi

iả

ệ ứ ự ữ ẽ ầ ị gi a các khoá s  có giá tr  tăng d n

a) Duy t theo th  t 1,2,3,4,5,6,7,8,9,10,11,12,15.

100

ượ ượ ủ ả ủ b) Khoá 13 đ và khoá 14 đ c chèn thành nút con bên trái c a nút 15  c chèn thành nút con bên ph i c a nút 13.

Đ  thiề

ề

Đ  thi 2002

G

C

K

M

A

E

I

B

D

F

H

J

L

N

101

Đ  thiề

ề

Đ  thi 2002

ộ ườ ộ ườ ng đi trong và đ  dài đ ng đi ngoài

a) Tìm đ  dài đ ủ c a cây.

ế ế ứ ự ả b) Cho bi ệ t k t qu  duy t cây theo th  t sau.

ự

ả ễ ắ ễ ứ ự ậ ồ

ế ầ ử  tăng g m 14 ph n t ậ ố ầ

ầ ử ộ

102

ế ả ị c) Xây d ng cây bi u di n cho thu t toán tìm ki m nh   phân trên m ng a s p th  t . Suy  ra s  l n so sánh khoá trung bình khi dùng thu t toán tìm  ằ ể ị ki m nh  phân đ  tìm xem m t ph n t  x có n m trong  m ng a hay không.

Đ  thiề

Gi

iả

ườ ộ a) Đ  dài đ ng đi trong IP=0+2.1+4.2+7.3=31.

ộ ườ Đ  dài đ ng đi ngoài EP=IP+2n=31+2.14=59.

ứ ự ế ả ệ b) K t qu  dy t cây theo th  t sau:

B,A,D,F,E,C,H,J,I,L,N,M,K.

ề ằ ươ ứ ng  ng A,B,C,

103

ở c) Là cây trong đ  bài b ng cách thay t … b i 1,2,3,…

Đ  thiề

...

ố S  phép so sánh khoá trung bình

Ø Tìm thành công (d ng t

ừ ạ i nút trong):

3.21

(IP+n)/n = (31 + 14) /14 (cid:0) ừ i nút ngoài):

104

ạ Ø Tìm không  có (d ng t EP/(n+1) = 59/15 (cid:0) 3,93

Đ  thiề

ủ ồ ị ơ ế

ầ c g i là c u n u G

ế

ầ

ằ

ố ạ ủ

ọ

ề

105

Đ  thi 2008 ộ ạ Bài 5.M t c nh e c a đ  th  đ n,  ượ ọ liên thông G đ không còn liên thông khi ta xóa e.  ứ Ch ng minh r ng e là c u n u và  ề ỉ ế i đ i c a G đ u  ch  n u m i cây t ch a eứ .

Đ  thiề

ầ ộ

ứ ầ

ố ạ ủ ả ậ

ả ử ả Gi i:­ Gi  s  e là c u.Khi đó G – e  không liên  ả ử  s  T là m t cây không ch a e.Do T liên  thông.Gi ộ ẽ ằ thông nó s  n m trong m t thành ph n liên thông  ủ c a G – e , vì v y T không ph i là cây t i đ i c a  G.

- Đ o l

ọ ả ử ả ạ ố ạ ế i:Gi s  e n m trong m i cây t

ẽ ứ ộ i đ i. N u  i đ i T.

ố ạ ủ ậ

106

ằ ố ạ G – e  liên thông thì nó s  ch a m t cây t ộ i đ i c a G, mà T  Rõ ràng T cũng là m t cây t ẫ ứ không ch a e, mâu thu n.V y  G – e không liên  thông, do đó e là c u.ầ

Đ  thiề

§ Đ  2008.

ề

Bài 6.

ị ượ ằ

ầ c b ng cách chèn l n  ở ỗ ẽ t các khóa K1,K2,…,K14 sao cho khóa m i nút

ộ

ộ

107

ủ ủ ứ ự ủ ư ả a) V  cây nh  phân có đ ượ l ớ ơ l n h n khóa c a các nút thu c cây con bên trái và  ơ bé h n khóa c a các các nút thu c cây con bên   c a các khóa nh  sau: ph i.Th  t

Đ  thiề

K5 < K8 

ẫ

ộ

108

ư ế ộ b) N u tìm ng u nhiên m t khóa K đã có trong cây  ả ố   thì s  phép so sánh trung bình là bao nhiêu? Ta gi ằ ấ ể ế ằ thi t r ng xác su t đ  K b ng m t trong các khóa  trong cây là nh  nhau.

K5 < K8 

K1

K4

K2

K10

K5

K7

K3

K11

K8

K9

K6

K14

K13

K12

109

Đ  thiề

ườ ộ § Đ  dài đ ng đi trong :

I = 0+2.1+4.2 + 6.3+ 4 = 2 +8+18+4 = 32

ế

ố S  phép so sánh trung bình cho tìm ki m thành  công:

110

(I + n)/n = 46/14 = 3,29

Đ  thiề

ề Đ  thi ĐHBK 2000.

ự ế ậ

ễ a) Xây d ng cây bi u di n cho thu t toán tìm ki m  ắ ể ả ứ ự ồ  tăng g m 13

ị nh  phân trên m ng s p th  t ầ ử ph n t .

b) Tìm đ  dài đ

ườ ộ ườ ng đi trong và đ  dài đ ng đi

ộ ủ ngoài c a cây.

c) Cho bi

111

ế ế ả ệ t k t qu  duy t cây theo th  t ứ ự ướ  tr c.

Appendix

ế

ậ

ị

Thu t toán tìm ki m nh  phân(binary search):

q Tìm ph n t

ầ ử ầ ố x trong dãy s  tăng d n.

Ø Nh p: dãy a1,a2, …,an tăng d n và ph n t

ầ ử ầ ậ x.

Ø Xu t :v  trí c a x trong dãy ho c 0.

112

ủ ặ ấ ị

Appendix

ậ Thu t toán l:=1,r:= n

repeat

i:=(l+r)div2;

if

ai

if

ai>x  then r : = i­1:

utill(x = ai or (l >r);

if

(x =ai)then

ấ

ở ị

xu t ấ i (tìm th y x

v  trí

i)

else

113

ấ

ấ

xu t 0(không tìm th y x trong dãy)