Bài giảng Lý thuyết đồ thị - Chương 2: Biểu diễn đồ thị trên máy tính - Nguyễn Trần Phi Phượng

Chương 2
BIỂU DIỄN ĐỒ THỊ TRÊN 
MÁY TÍNH
208/03/2011
2.1 Ma trận kề - Ma trận trọng số
Lý thuyết đồ thị
Ma trận kề
Xét đơn đồ thị G = (V,E) bao gồm V={v1, v2, , vn}.
Ma trận kề biểu diễn G là một ma trận vuông A =[aij]n,
được xác định như sau:
Ví dụ
1, ( , )
0, ( , )
i j
ij
i j
v v E
a
v v E
∈⎧= ⎨ ∉⎩ 1 2 3 4
1 0 0 1 0
2 0 0 0 1
3 0 0 0 1
4 1 1 0 0
⎡ ⎤⎢ ⎥⎢ ⎥= ⎢ ⎥⎢ ⎥⎣ ⎦
A
308/03/2011
2.1 Ma trận kề - Ma trận trọng số
Lý thuyết đồ thị
Ví dụ
1 2 3
4 5 6
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
=
000000
001011
010011
000010
011101
011010
6
5
4
3
2
1
654321
A
408/03/2011
2.1 Ma trận kề - Ma trận trọng số
Lý thuyết đồ thị
Các tính chất của ma trận kề
1. Ma trận kề của đồ thị vô hướng là ma trận đối xứng.
2. Tổng các phần tử trên dòng i (cột j) của ma trận kề
chính bằng bậc của đỉnh i (đỉnh j).
Chú ý
Ma trận kề của đa đồ thị có thể xây dựng hoàn toàn tương
tự.
, ( , )
0, ( , )
i j
ij
i j
k v v E
a
v v E
∈⎧= ⎨ ∉⎩
k: số cạnh nối hai đỉnh vi và vj
508/03/2011
2.1 Ma trận kề - Ma trận trọng số
Lý thuyết đồ thị
Đồ thị có trọng số
Đồ 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 (cung) 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
Ma trận trọng số
Cho G = (V, E), V = {v1,v2,,vn} là đơn đồ thị có trọng
số. Ma trận khoảng cách của G là ma trận D= (dij) xác định
như sau:
0,
( , ), ( , )
, ( , )
ij i j i j
i j
i j
d w v v v v E
v v E
⎧ =⎪= ∈⎨⎪∞ ∉⎩
608/03/2011
2.1 Ma trận kề - Ma trận trọng số
Lý thuyết đồ thị
Ví dụ
0 5 31 40
0 27 73
26 0 8 49 25 38
0 16
70 0 9
23 0 12
10 0
D
∞ ∞ ∞⎡ ⎤⎢ ⎥∞ ∞ ∞ ∞⎢ ⎥⎢ ⎥∞⎢ ⎥= ∞ ∞ ∞ ∞ ∞⎢ ⎥⎢ ⎥∞ ∞ ∞ ∞⎢ ⎥∞ ∞ ∞ ∞⎢ ⎥⎢ ⎥∞ ∞ ∞ ∞ ∞⎣ ⎦
708/03/2011
2.2 Ma trận liên thuộc đỉnh cạnh
Lý thuyết đồ thị
Xét đồ thị có hướng G = (V,E) với V={v1, v2,, vn},
E={e1, e2,, em}. Ma trận liên thuộc đỉnh – cạnh
A=[aij]n×m được xây dựng theo quy tắc:
1,
1,
0,
ija
⎧⎪= −⎨⎪⎩
nếu vi là đỉnh đầu của cung ej
nếu vi là đỉnh cuối của cung ej
nếu vi không là đỉnh đầu, đỉnh cuối của
cung ej
808/03/2011
2.2 Ma trận liên thuộc đỉnh cạnh
Lý thuyết đồ thị
Ví dụ
1 1 1 0 0 0
2 0 0 0 1 1
3 1 0 1 0 0
4 0 1 1 1 1
A
−⎡ ⎤⎢ ⎥−⎢ ⎥= ⎢ ⎥−⎢ ⎥− −⎣ ⎦
e1 e2
e3
e4 e5
1 2 3 4 5e e e e e
908/03/2011
2.3 Danh sách cạnh
Cho đồ thị G = (V,E) có m cạnh. Danh sách cạnh của G
sẽ bao gồm hai mảng 1 chiều có kích thước m:
– Mảng Dau sẽ lưu các đỉnh đầu của các cạnh
– Mảng Cuoi sẽ lưu đỉnh cuối của các cạnh
Ví dụ
e1 e2
e3
e4 e5
Dau Cuoi
1 3
4 1
3 4
4 2
2 4
Lý thuyết đồ thị
1008/03/2011
Ví dụ
1 2 3
4 5 6
e1 e2
e3
e4
e5
e6
e7
Dau Cuoi
1 2
2 3
1 4
1 5
4 2
4 5
2 5
2.3 Danh sách cạnh
Lý thuyết đồ thị
1108/03/2011
ƒXác định bậc của đỉnh dựa vào danh sách cạnh:
– Đối với đồ thị vô hướng: duyệt qua 2 mảng Dau va
Cuoi, số lần xuất hiện của một đỉnh chính là bậc của
đỉnh đó.
– Đối với đồ thị có hướng:
• Duyệt qua mảng Dau, số lần xuất hiện của một đỉnh
chính là bán bậc ra của đỉnh đó.
• Duyệt qua mảng Cuoi, số lần xuất hiện của một đỉnh
chính là bán bậc vào của đỉnh đó.
2.3 Danh sách cạnh
Lý thuyết đồ thị
1208/03/2011
2.4 Danh sách kề
Cho đồ thị G = (V,E) có n đỉnh. Đồ thị G có thể được
biểu diễn bằng n danh sách liên kết. Mỗi danh sách liên kết
thứ i sẽ biểu diễn các đỉnh kề với đỉnh vi
Ví dụ
3 NULL
4 NULL
4 NULL
1 NULL2
1
2
3
4
Lý thuyết đồ thị
1308/03/2011
Ví dụ
1 2 3
4 5 6
2 NULL
1 NULL
2 NULL
1 NULL2
1
2
3
4
1
NULL
5
6
4 5
3 4 5
5
2 NULL4
2.4 Danh sách kề
Lý thuyết đồ thị
1408/03/2011
ƒXác định bậc của đỉnh dựa vào danh sách kề:
– Đối với đồ thị vô hướng: Số phần tử của mỗi danh
sách sẽ là bậc của đỉnh tương ứng
– Đối với đồ thị có hướng:
• Số phần tử của mỗi danh sách sẽ là bán bậc ra của
đỉnh tương ứng
• Việc xác định bán bậc vào khó khăn hơn nhiều: phải
duyệt qua tất cả các danh sách, số lần xuất hiện của 1
đỉnh trong các danh sách chính là bán bậc vào của
đỉnh đó.
2.4 Danh sách kề
Lý thuyết đồ thị