Đồ thò

7.3. Biểu diễn đồ thò và sự đẳng cấu
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.3. Biểu diễn đồ

1


Biểu diễn đồ thò
– Ví dụ 1. Dùng danh sách liền kề để mô tả đồ thò đơn: liệt kê tất
cả các đỉnh liền kề với mỗi đỉnh của đồ thò.

b
a

c

e

10/01/15

d

Đỉnh


d

Đỉnh đầu
a
b
c
d
e

7.3. Biểu diễn đồ

Đỉnh cuối
b, c, d, e
b, d
a, c, e
b, c, d

3


Ma trận liền kề
•

•

Biểu diễn đồ thò bằng ma trận: Ma trận liền kề. Cho G = (V, E) là
đồ thò đơn có n đỉnh, các đỉnh của G là v1, v2,…, vn .
Ma trận liền kề A hay AG của G là ma trận không-một (0-1) cấp n ×
n có phần tử hàng i cột j là aij bằng

1

1
0
1
0

1
1
0
0

1
0
0
0
c

10/01/15

b

7.3. Biểu diễn đồ

d

5


Ma trận liền kề

c

6


Ma trận liền kề
•

•

Ma trận liền kề có thể dùng để biểu diễn đồ thò vô hướng có
khuyên và (hay) có cạnh bội.
– Khuyên tại đỉnh ai được biểu diễn bằng 1 tại vò trí (i, i) của ma
trận liền kề.
– Khi có cạnh bội, phần tử ở vò trí (i, j) của ma trận bằng số các
cạnh nối các đỉnh ai và aj .
Nhận xét: Tất cả các đồ thò vô hướng (đơn đồ thò, đa đồ thò, giả đồ
thò) đều có ma trận liền kề đối xứng.

10/01/15

7.3. Biểu diễn đồ

7


Ma trận liền kề
– Ví dụ 5. Dùng ma trận liền kề để biểu diễn giả đồ thò .
° Thứ tự các đỉnh là a, b, c, d.
a

•

Cho G = (V, E) là đồ thò có hướng có n đỉnh, các đỉnh của G là v1, v2,
…, vn .
Ma trận liền kề A hay AG của G là ma trận không-một (0-1) cấp n ×
n có phần tử hàng i cột j là aij bằng
°

1 nếu có cạnh đi từ vi tới vj ,

0 trong các trường hợp khác.
Nhận xét:
– Ma trận liền kề của một đồ thò tuỳ thuộc vào thứ tự liệt kê các
đỉnh.
– Ma trận liền kề của đồ thò có hướng không có tính đối xứng.
– Cũng có thể dùng ma trận liền kề để biểu diễn đa đồ thò có
hướng. Khi đó aij bằng số các cung đi từ đỉnh vi tới đỉnh vj .
°

•

10/01/15

7.3. Biểu diễn đồ

9


Ma trận liên thuộc
•

7.3. Biểu diễn đồ

10


Ma trận liên thuộc
•

Ma trận liên thuộc
– Ví dụ 6. Xác đònh ma trận liên thuộc.

v1
v2
v3
v4
v5

e1
1
0
0
1
0

e2
1
0
0
0
1


v2

v1

e6

v3

e3
e4

e1

e5

e2
v4

7.3. Biểu diễn đồ

v5

11


Ma trận liên thuộc
– Ví dụ 7. Biểu diễn cạnh bội và khuyên bằng ma trận liên thuộc.
e2


0
0
0

e3
1
1
0
0
0

10/01/15

e4
0
1
1
0
0

e5
0
0
1
0
1

e6
0
1

Sự đẳng cấu của các đồ thò
– Đònh nghóa 1. Các đồ thò đơn G1 = (V1, E1) và G2 = (V2, E2) là
đẳng cấu nếu có hàm song ánh f từ V1 lên V2 sao cho các đỉnh a
và b là liền kề trong G1 nếu và chỉ nếu f(a) và f(b) là liền kề
trong G2 với mọi a và b trong V1. Hàm f như thế được gọi là một
đẳng cấu.

10/01/15

7.3. Biểu diễn đồ

13


Sự đẳng cấu của các đồ thò
– Ví dụ 8. Các đồ thò G = (V, E) và H = (W, F) là đẳng cấu
u1

u3

u2

G

u4

v1

v2


10/01/15

7.3. Biểu diễn đồ

14


Sự đẳng cấu của các đồ thò
– Ví dụ 9. Các đồ thò G và H là không đẳng cấu.
b

b
c

a

e

G

d

c

a

e

H


16


Sự đẳng cấu của các đồ thò
– Ví dụ 10. Các đồ thò G và H có đẳng cấu hay không?
a

b
e

f

g

h
d

s

G

c

t
w

x

z


f

w

z

h
d

10/01/15

v

7.3. Biểu diễn đồ

18


Sự đẳng cấu của các đồ thò
– Dùng ma trận liền kề để chứng tỏ hàm f là bảo tồn các cạnh:
° Ma trận liền kề của G, (với một thứ tự các đỉnh)
° Ma trận liền kề của H, với hàng và cột được gán nhãn tương
ứng với ảnh qua f của các đỉnh trong G.
° Nếu các ma trận liền kề trên giống nhau thì G và H là đẳng
cấu.

10/01/15

7.3. Biểu diễn đồ


v4

Cả hai đồ thò đều có 6 đỉnh, 7 cạnh, 4 đỉnh bậc 2, 2 đỉnh bậc 3.
° Đònh nghóa f như sau:
f(u1) = v6 , f(u2) = v3 , f(u3) = v4 ,
f(u4) = v5 , f(u5) = v1 , f(u6) = v2
°

10/01/15

7.3. Biểu diễn đồ

20


Sự đẳng cấu của các đồ thò
– Ví dụ 11. (tiếp theo)
° Các ma trận liền kề của G và H là
u1
u2
AG = u3
u4
u5
u6
°

u1
0
1
0

0
0
1
0
1

u6
0
1
0
0
1
0

v6
v3
AH = v4
v5
v1
v2

v6
0
1
0
1
0
0

v3

21