Chương 5

CÂY
[email protected]
http://www.math.hcmus.edu.vn/~luyen/cautrucroirac

FB: fb.com/cautrucroirac
CuuDuongThanCong.com

https://fb.com/tailieudientucntt


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

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

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
và không có chu trình
B

E

3


Cây

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

4


Rừng
Định nghĩa. Rừng (forest) là đồ thị vô hướng không
có chu trình
B

A

G

C

F

D

E

I

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
CuuDuongThanCong.com

https://fb.com/tailieudientucntt

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

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

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à

A
B

C

D

C

F

A

B

E

D

E

D

F

A

B

E

C

D

Số cây khung 55-2=125

E

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

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)

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

12




b

e

l

e

f

b

d

f

g

i

j
k

i

Chọn e làm gốc
Chọn các đỉnh kề với e.
Các đỉnh mức 1 là: b, d, f, i



j
k

f

d

b

i
c

h

k
g

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,
 k là con duy nhất của i,

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

https://fb.com/tailieudientucntt


f

d

b

i
c

h

k

g

j

l

m

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
CuuDuongThanCong.com

https://fb.com/tailieudientucntt

16




Đáp án.

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

18


Tìm kiếm theo chiều sâu (DFS)
Cho G là đồ thị liên thông với tập đỉnh {v1, v2, …, vn}


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.

k

f
c
e
b

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

g

20


d

a

i

f

j
g

f
h



j
g

d

f
h

c
e

k

h

b

k
g

e
c

i

j

b



J
C

CuuDuongThanCong.com

G

https://fb.com/tailieudientucntt

23


Đồ thị có trọng số
Định nghĩa. Đồ thị G = (V,E) gọi là đồ thị có trọng
số (hay chiều dài, trọng lượng) nếu mỗi cạnh e được
gán với một số thực w(e). Ta gọi w(e) là trọng
lượng của e.

 Độ dài của đường đi từ u đến v bằng tổng độ dài
các cạnh mà đường đi qua.

 Trọng lượng của một cây T của G bằng với tổng
trọng lượng các cạnh trong cây

 Cây

khung ngắn nhất là cây khung có trọng
lượng nhỏ nhất của G.
CuuDuongThanCong.com