Chương 3. Lý thuyết đồ thị
3.2. Biểu diễn đồ thị
3.2.1. Các hình thức biểu diễn
Biểu diễn hình học
Biểu diễn hình học là một minh họa trực quan về
đồ thị, trong đó mỗi đỉnh được coi là một điểm, còn
cạnh (cung) là một đường (kèm theo mũi tên) nối
từ đỉnh nọ đến đỉnh kia.
Tuy nhiên BDHH có một nhược điểm là không
được hỗ trợ bởi các công cụ tính toán (máy tính).
Nó chỉ giúp định hướng (trực quan) cho tư duy trên
đồ thị.
3.2. Biểu diễn đồ thị
Danh sách kề
Là danh sách gồm 2 cột. Cột đầu liệt kê tất cả các đỉnh của đồ thị.
Trên mỗi dòng của cột thứ hai lần lượt liệt kê các đỉnh liền kề với
đỉnh tương ứng trong cột thứ nhất.
Một cách lưu trữ danh sách kề là dùng các danh sách liên kết, trong
đó node đầu tiên của mỗi danh sách được cất trong một mảng được
chỉ số hóa bởi các đỉnh.
Ví dụ:
235
135
124
653
421
54
6
1
2
3
4
5
6
1
2
3 4
6
5
1 2 3 5
2 1 3 5
3 1 2 4
4 3 5 6
5 1 2 4 6
6 4 5
3.2. Biểu diễn đồ thị
Danh sách cạnh (cung)
Danh sách cạnh (cung) của
đồ thị có n cạnh (cung) là
danh sách gồm n dòng và 2
cột. Mỗi dòng tương ứng với
một cạnh (cung) của đồ thị.
Trên mỗi dòng, cột đầu ghi
đỉnh (đỉnh đầu), cột thứ hai
ghi đỉnh kề (đỉnh cuối) của
cạnh, (cung) tương ứng.
Một cách lưu trữ danh sách
cạnh là dùng danh sách liên
kết, trong đó mỗi node
tương ứng với một cạnh
(cung).
Ví dụ:
1
2
3
4
6
5
1 3
1 5
1 2
3 4
32
4 6
4 5
2 5
5 6
3.2. Biểu diễn đồ thị
Ma trận kề
Cho G =(V,E) là một đồ thị có n đỉnh, trong đó tập
đỉnh đã được sắp thứ tự (mã hóa từ 1 đến n).
Ma trận kề của đồ thị là ma trận A=[aik], trong đó
aik là số cạnh (cung) nối từ đỉnh thứ i đến đỉnh thứ
k.
Một số tính chất đơn giản của ma trận kề:
Ma trận kề của một đồ thị là ma trận vuông cấp n.
Nếu đồ thị là đồ thị vô hướng thì ma trận kề là ma trận đối
xứng.
Nếu đồ thị là đơn đồ thị thì ma trận kề là ma trận 0-1.
Ví dụ:Đa đồ thị sau
1
2
3
4
6
5
Có ma trận kề là:
Ví dụ:Đơn đồ thị sau
Có ma trận kề là:
1
2
3
4
6
5
=
011000
103011
130100
001022
010201
010210
A