Chương VI
ĐỒ THỊ VÀ CÂY
ồ thò là một chủ đề đã cũ nhưng lại có rất nhiều ứng dụng trong các ngành khoa học
hiện đại và được dùng để giải rất nhiều lớp bài toán khác nhau. Đặc biệt là trong
công nghệ thông tin lý thuyết đồ thò có một vai trò rất quan trọng trong việc xác đònh
các kết nối trên mạng máy tính, tối ưu hóa đường truyền dữ liệu cũng như tối ưu hóa bản thân
dữ liệu được trao đổi giữa các máy tính , .v.v..
Đ
Trong chương trước chúng ta đã nghiên cứu một số khái niệm đầu tiên về đồ thò, chương này
cung cấp cho chúng ta thêm một số khái niệm và tính chất thường dùng để giải các bài toán có
áp dụng lí thuyết đồ thò. Cũng cần lưu ý là nếu không có chỉ đònh gì đặc biệt thì đồ thò nói trong
chương này là đồ thò vô hướng.
I. ĐỒ THỊ
Đònh nghóa: Bậc của một đỉnh trong một đồ thò là số cạnh tới nối với đỉnh này.
Ví dụ:
Các đỉnh cô lập A, D có bậc 0.
Bậc của đỉnh F là 3
Bậc của đỉnh B là 4 (Bậc của đỉnh có vòng được cộng thêm 2 cho
mỗi vòng).
Bậc của đỉnh G là 1. Đỉnh bậc 1 gọi là đỉnh treo và cạnh tới tương
ứng gọi là cạnh treo.
Bổ đề 1: Trong một đồ thò thì tổng bậc các đỉnh bằng hai lần số cạnh.
Chứng minh.
Vì mỗi cạnh được tính cho 2 đỉnh có bậc khác 0.
QED
Ví dụ: Có bao nhiêu cạnh trong đồ thò (vô hướng) có 10 đỉnh đều có bậc là 6?
Giải: Tổng bậc tất cả các đỉnh là 6*10 = 60 nên suy ra đồ thò có tất cả 30 cạnh.
Bổ đề 2: Số các đỉnh bậc lẻ là số chẵn.
Chứng minh.
Tổng bậc các đỉnh bậc lẻ+Tổng bậc các đỉnh bậc chẵn = 2 * số cạnh.
Suy ra tổng bậc các đỉnh bậc lẻ là chẳn.

2
(Không có cạnh nào nối hai đỉnh trong V
1
hoặc hai đỉnh trong V
2
với
nhau).
Các đồ thò phân đôi.
Đònh nghóa: Đồ thò đơn gọi là phân đôi hoàn chỉnh, kí hiệu K
m,n
, nếu tập các đỉnh V của
nó có thể phân thành hai tập con V
1
và V
2
lần lượt có m đỉnh và n đỉnh và mỗi đỉnh trong tập
con này đều được nối với mọi đỉnh trong tập con kia.
K
2,3
K
3,3
K
3,5
K
4,3
Ứng dụng của đồ thò trong công nghệ thông tin:
Mạng cục bộ (LAN - Local Area Network): Nhiều máy tính và các thiết bò ngoại vi đi
kèm đặt trong một tòa nhà có thể được nối với nhau thành một mạng gọi là mạng cục bộ. Cấu
103
V

yêu cầu này hoặc là phải tăng xung nhòp của CPU (tăng tốc độ xử lí) hoặc là phải tăng số bộ
xử lí lên. Nếu có nhiều bộ xử lí thì các giải thuật song song sẽ phân chia bài toán cần giải
quyết ra thành nhiều bài toán con để có thể giải đồng thời. Các bài toán con này sẽ được gởi
đến cho các bộ xử lí khác nhau để xử lí riêng rẽ. Khi tất cả các bài toán con đã được xử lí xong
thì một kết quả tổng hợp sẽ được thực hiện.
Ví dụ: Một đoạn mã giả thể hiện giải thuật có sử dụng quá trình xử lí song song các
phát biểu statement_1, statement_2, ..., statement_n
.....
cobegin
statement_1;
statement_2;
...
statement_n;
coend
Statement_m
....
Ví dụ: Thực hiện đoạn chương trình
2
:
x := a - c*d + e
y := b + d/a
z := x + e*y
Xử lí trên máy tính tuần tự (một bộ xử lí) cần 7 bước:
1 c*d
2 a-(c*d)
3 (a-c*d)+e
4 d/a
5 b+(d/a)
6 e*y
7 x+(e*y)

i+1
. Nhưng như vậy thì cần các bước xử lí trung gian khi P
i
chia
sẽ dữ liệu với các P
j
(P
j
≠
P
i-1
và P
j
≠
P
i+1
).
Người ta dùng phổ biến cách liên kết theo mảng hai chiều, trong đó số bộ xử lí N là
một số chính phương. Các bộ xử lí được đánh thứ tự P
i,j
trong đó i và j chạy từ 1 đến m (m =
2
N ). Mỗi P
i,j
liên kết với 4 bộ xử lí láng giềng P
i+1,j
, P
i-1,j
, P
i,j+1

n-2
,A
n-1
); (A
n-1
,y
n-1
,A
n
)
}
⊆
VxExV
3
Lưu ý rằng đường có thể là đồ thò con của một đồ thò khác.
106
Trong bước 1 các phép
toán +,* và / được xử lí
song song.
Trong bước 2 các phép
toán - và + được xử lí
song song
Nói cách khác đường là một chuỗi cạnh nối tiếp nhau.
Ta kí hiệu đường bằng chuỗi đỉnh được nối với nhau bởi đường.
Đường không tự cắt là một đường có 2 đỉnh bậc 1 và mọi đỉnh còn lại đều có bậc 2.
Ví dụ:
Đường DCB là đường không tự cắt.
Đường ACBCD là đường tự cắt.
Đònh nghóa: Đường đi gọi là đơn nếu nó không chứa cạnh nào quá 1 lần.
Khái niệm liên thông: