Đồ thò

7.2. Các thuật ngữ về đồ thò
Tài liệu này được soạn theo sách Toán học rời rạc ứng dụng trong tin học , K. H.
Rosen, người dòch: Phạm Văn Thiều và Đặng Hữu Thònh, Nhà xuất bản Khoa học
và kỹ thuật, 1998.
Tài liệu lưu hành nội bộ

10/01/15

7.2. Các thuật ngữ

1


Những thuật ngữ cơ sở
– Đònh nghóa 1.
° Hai đỉnh u và v trong một đồ thò vô hướng G được gọi là
liền kề (hay láng giềng) nếu {u, v} là một cạnh của G.
° Nếu e = {u, v} thì e gọi là cạnh liên thuộc với các đỉnh u và
v.
° Cạnh e cũng được gọi là cạnh nối các đỉnh u và v.
° Các đỉnh u và v gọi là các điểm đầu mút của cạnh {u, v}.
– Đònh nghóa 2.
° Bậc của một đỉnh trong đồ thò vô hướng là số các cạnh
liên thuộc với nó.
° Riêng khuyên tại một đỉnh được tính hai lần cho bậc của
nó.
° Ký hiệu bậc của đỉnh v là deg(v).

10/01/15


G
deg(a) = 2
deg(b) = deg(c) = deg(f) = 4
deg(d) = 1
Đỉnh treo
deg(e) = 3
deg(g) = 0
Đỉnh cô lập

10/01/15

e

deg(a) = 4
deg(b) = deg(e) = 6
deg(c) = 1
deg(d) = 5

7.2. Các thuật ngữ

3


Những thuật ngữ cơ sở
– Đònh lý 1. Đònh lý bắt tay. Cho G = (V, E) là một đồ thò vô
hướng có e cạnh. Khi đó
2e=

∑ deg (v)



Những thuật ngữ cơ sở
– Đònh nghóa 4. Trong đồ thò có hướng,
° bậc-vào của đỉnh v ký hiệu là deg− (v) là số các cạnh có
đỉnh cuối là v.
° bậc-ra của đỉnh v ký hiệu là deg+ (v) là số các cạnh có đỉnh
đầu là v.
° (Một khuyên tại một đỉnh góp 1 đơn vò vào bậc-vào và 1
đơn vò vào bậc-ra của đỉnh này.)

10/01/15

7.2. Các thuật ngữ

6


Những thuật ngữ cơ sở
– Ví dụ 3. Tìm bậc-vào và bậc-ra của mỗi đỉnh trong G.
Các bậc-vào là
deg− (a) = 2
deg− (b) = 2
deg− (c) = 3
deg− (d) = 2
deg− (e) = 3
deg− (f ) = 0

a


∑ deg

v∈V

−

(v) =

∑ deg

v∈V

+

(v) = E  .

– Đồ thò vô hướng nền là đồ thò vô hướng nhận được khi lờ đi
các hướng của các cạnh của đồ thò có hướng.
– Nhận xét: Đồ thò có hướng và đồ thò vô hướng nền của nó có
cùng số cạnh.

10/01/15

7.2. Các thuật ngữ

8


Những đồ thò đơn đặc biệt
– Ví dụ 4. Đồ thò đầy đủ n đỉnh, ký hiệu là Kn , là một đơn đồ thò


C6

C5

7.2. Các thuật ngữ

10


Những đồ thò đơn đặc biệt
– Ví dụ 6. Đồ thò hình bánh xe Wn , với n ≥ 3, là đồ thò có được từ
chu trình Cn bằng cách:
°

thêm một đỉnh vào Cn ,

°

nối đỉnh này với mỗi đỉnh của Cn bằng những cạnh mới.

W3

10/01/15

W4

W6

W5

Q1

10/01/15

01

00

000

Q2

7.2. Các thuật ngữ

001
Q3

12

011


Đồ thò phân đôi
– Đònh nghóa 5. Một đồ thò đơn G được gọi là đồ thò phân đôi nếu
tập các đỉnh V có thể phân làm hai tập con không rổng, rời nhau
V1 và V2 sao cho mỗi cạnh của đồ thò G nối một đỉnh của V1 với
một đỉnh của V2 .
– Ví dụ 8. C6 là phân đôi.
Các đỉnh của C6
có thể chia thành:



Đồ thò phân đôi
– Ví dụ 9. K3 là không phân đôi. Vì nếu chia các đỉnh của nó
thành hai phần rời nhau thì một trong hai phần này phải chứa 2
đỉnh; nếu đồ thò là phân đôi thì các đỉnh này không thể nối với
nhau bằng một cạnh, nhưng trong K3 mỗi đỉnh được nối với một
đỉnh bất kỳ khác bằng một cạnh.
– Ví dụ 10.
b

a

b

a
c

g

c
f

f
e

10/01/15

G


e

G

d

Đồ thò G là phân đôi, với {a, b,
d}
và {c, e, f, g}.

10/01/15

e

H

d

Đồ thò H là không phân đôi, vì
° f nối với tất cả các đỉnh khác;
do đó V1 = {f}.
° a và b lại nối với nhau.

7.2. Các thuật ngữ

15


Đồ thò phân đôi
– Ví dụ 11. Đồ thò phân đôi đầy đủ Km,n là đồ thò

Đồ thò phân đôi đầy đủ K1,n
Chu trình Cn
Đồ thò hình bánh xe Wn

10/01/15

7.2. Các thuật ngữ

17


Một vài ứng dụng của các đồ thò đặc biệt
– Ví dụ 13.
° Thuật toán tuần tự (hay nối tiếp)
° Thuật toán song song
– Mảng một chiều
– Mảng kiểu lưới (hay mảng hai chiều)
– Mạng kiểu siêu khối

10/01/15

7.2. Các thuật ngữ

18


Các đồ thò mới từ đồ thò cũ
– Đònh nghóa 6. Đồ thò con của đồ thò G = (V,E) là đồ thò H =
(W,F) trong đó W ⊆ V và F ⊆ E.
– Ví dụ 14. Đồ thò G là đồ thò con của đồ thò K5 .


tập các đỉnh là V1∪ V2

°

tập các cạnh là E1∪E2 .

– Ký hiệu: hợp của các đồ thò G1 và G2 là G1∪ G2 .
a – Ví dụ
b 15. Đồ cthò hợpa của G1 và
b G2 .

e

d

G1

10/01/15

d

c

a

b

f