Chương 2: Biểu diễn đồ thị
2
Chương 2 – Biểu diễn đồ thị
Nội dung
Sự đẳng cấu của các đồ thị
Các cách biểu diễn đồ thị
I.
II.
Hướng dẫn cài đặt
III.
Lý thuyết đồ thị
2
3
Chương 2 – Biểu diễn đồ thị
I. Các cách biểu diễn đồ thị
Các cách biểudiễnđồ thị
Ma trậnkềDanh sách cạnh Danh sách kềMa trận liên thuộc
ậntrọng sốDanh sách cungMa tr
Lý thuyết đồ thị
3
4
Chương 2 – Biểu diễn đồ thị
I.1. Ma trận kề (đơn đồ thị vô hướng)
Định nghĩa
Đơn đồ thịG = (V,E) với tập đỉnh V = {0,…,n-1}, tập
cạnh E = {e0,e1,…em-1}. Ta gọi ma trận kềcủa G là
A = {ai,j , i,j = 0,…,n-1}, với:
⎩
⎨
⎧
∈
∉
=
Ejiif
Ejiif
aji ),(,1
),(,0
,
0 1 2 3 4
00 1 1 0 1
1 1 0 1 0 1
21 1 0 0 0
30 0 0 0 0
41 1 0 0 0
5
Chương 2 – Biểu diễn đồ thị
I.1. Ma trận kề (đơn đồ thịcó hướng)
Định nghĩa
Giống đơn đồ thịcó hướng
E là tập các cung
⎩
⎨
⎧
∈
∉
=
Ejiif
Ejiif
aji ),(,1
),(,0
,
0 1 2 3 4
00 0 1 0 1
1 1 0 0 0 0
20 1 0 1 0
30 0 0 0 1
40 1 0 0 0