Bài giảng Toán tổ hợp

Chương 5

CÂY

Nội dung

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

. Cây khung ngắn nhất

. Cây có gốc

. Phép duyệt cây

2

1. Định nghĩa và tính chất

Định nghĩa. Cây (tree) lꢀ đồ thị vô hưꢁng, liên thông

và không cꢂ chu trꢃnh

B

E

B

E

F

A

C

D

C

D

G2

G1

G1 là cây, G2 không phải cây

3

Cây

4

Rꢀng

Định nghĩa. Rꢀng (forest) lꢀ đꢄ thị vô hưꢁng không

cꢂ chu trꢃnh

B

G

I

L

J

C

D

A

F

E

K

H

Nhꢁn xꢂt. Rừng lꢀ đꢄ thị mꢀ mỗi thꢀnh phần liên thông

của nꢂ lꢀ một cây.

5

Rꢀng

6

Tính chất của cây

Định lý: Cho đồ thị vô hưꢁng T cꢂ n đꢅnh. Khi đꢂ cꢆc

phát biểu sau là tương đương:

1) T là 1 cây

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) Giꢇa hai đꢅnh bất kỳ của T cꢂ đúng một đường

đi nối chúng vꢁi nhau

6) T không chứa chu trꢃnh nhưng khi thêm vꢀo

một cạnh ta thu được đúng một chu trꢃnh

7

Hệ quả.

a) Một cây cꢂ ít nhất 2 đꢅnh treo

b) Nếu G lꢀ một rừng cꢂ n đꢅnh vꢀ cꢂ p cây thꢃ số

cạnh của G lꢀ m=n-p

8

Cây khung của đồ thị

Định nghĩa: Một cây T được gꢈi lꢀ cây khung (hay

cây tối đại, cây bao trùm) của đồ thị G=(V, E) nếu T là

đꢄ thị con của G và chứa tất cả các đꢅnh của G.

C

B

D

Ví dụ. Cho đꢄ thị

F

A

E

Hãy tꢃm cây khung của G?

9

Cây khung của đồ thị

C

B

D

E

F

Đáp án. Một số cây khung của G

A

C

D

C

B

D

F

A

B

E

Nhꢁn xꢂt. Vꢁi 1 đꢄ thị cho trưꢁc, cꢂ thể cꢂ vꢀi cây khung

của đꢄ thị đꢂ

10

Định lý. Mꢈi đꢄ thị liên thông đều cꢂ cây khung

Định lý (Cayley) Số cây khung của đꢄ thị K_nlà n^n-2

a

Số cây khung 4^4-2=16

f

d

b

Ví dụ: abc, bcd, cda, dab, abf, acf, bdf, ...

c

e

A

B

C

Số cây khung 5^5-2=125

E

D

11

Tìm một cây khung của đồ thị

Bài toán: Cho G lꢀ đꢄ thị vô hưꢁng liên thông, hãy

tꢃm 1 cây khung của đꢄ thị G.

Lời giải

• Thuật toꢆn tꢃm kiếm theo chiều rộng (BFS)

• Thuật toꢆn tꢃm kiếm theo chiều sâu (DFS)

12

Tìm kiếm theo chiều rộng (BFS)

Cho G lꢀ đꢄ thị liên thông vꢁi tập đꢅnh {v₁, v₂, …, v_n}

 Bưꢁc 0: thêm v₁như lꢀ gốc của cây rỗng.

 Bưꢁc 1: thêm vào các đꢅnh kề v₁và các cạnh nối v₁

vꢁi chúng. Nhꢇng đꢅnh này lꢀ đꢅnh mức 1 trong cây.

 Bưꢁc 2: đối vꢁi mꢈi đꢅnh v mức 1, thêm vào các

cạnh kề vꢁi v vào cây sao cho không tạo nên chu

trình. Ta thu được các đꢅnh mức 2.

…………………………………………………….

Tiếp tục quá trình này cho tꢁi khi tất cả các đꢅnh của đꢄ

thị được ghép vào cây. Cây T có được là cây khung của

đꢄ thị.

13

Ví dụ. Tꢃm một cây khung của đꢄ thị G.

c

l

e

b

a

e

f

d

b

f

d

i

g

h

i

j

Chọn e làm gốc

Chọn các đỉnh kề với e.

m

k

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

14

c

l

b

e

a

e

f

d

b

d

g

i

c

h

k

a

h

g j

i

j

. Thêm a và c làm con của b,

. h là con duy nhất của d,

. g và j là con của f,

m

k

. k là con duy nhất của i,

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

15

c

l

b

e

a

e

f

d

b

d

g

i

c

h

a

k

h

g j

i

j

m

k

m

l

Cuối cùng thêm l và m là con của g và k tương ứng

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

Ta có được cây khung cần tìm

16

Ví dụ. Tꢃm cây khung của đꢄ thị bằng thuật toꢆn BFS

vꢁi D lꢀ đꢅnh bắt đầu

E

B

I

D

H

K

F

A

J

C

G

17

Đáp án.

18

Tìm kiếm theo chiều sâu (DFS)

Cho G là đꢄ thị liên thông vꢁi tập đꢅnh {v₁, v₂, …, v_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ần lượt

ghép các cạnh sao cho mỗi cạnh mꢁi ghép sẽ nối

đꢅnh cuối cùng trên đường đi vꢁi một đꢅnh còn

chưa thuộc đường đi. Tiếp tục ghép thêm cạnh

vào đường đi chừng nào không thể thêm được

nꢇa.

 Nếu đường đi qua tất cả các đꢅnh của đꢄ thị thì

cây do đường đi này tạo nên là cây khung.

19

 Nếu chưa thì lùi lại đꢅnh trưꢁc đꢅnh cuối cùng của

đường đi và xây dựng đường đi mꢁi xuất phát từ

đꢅnh này đi qua các đꢅnh còn chưa thuộc đường đi.

Nếu điều đꢂ không thể làm được thì lùi thêm một

đꢅnh nꢇa trên đường đi, tức là lùi hai đꢅnh trên

đường đi và thử xây dựng đường đi mꢁi.

d

i

j

a

Ví dụ. Tìm một cây

khung của đꢄ thị vꢁi

f là đꢅnh gốc

f

c

e

k

h

b

20

g

Bài giảng Toán tổ hợp - Chương 5: Cây