Bài giảng Toán rời rạc 2 - Chương 2: Biểu diễn đồ thị trên máy tính - Ngô Xuân Bách
Học viện Công nghệ Bưu chính Viễn thông
Khoa Công nghệ thông tin 1
Toán rời rạc 2
Biểu diễn đồ thị trên máy tính
Ngô Xuân Bách
Nội dung
Biểu diễn đồ thị bằng ma trận kề
Biểu diễn đồ thị bằng ma trận liên thuộc
Biểu diễn đồ thị bằng danh sách cạnh
Biểu diễn đồ thị bằng danh sách kề
2
Ma trận kề của đồ thị vô hướng (1/2)
Xét đồ thị vô hướng 퐺 =< 푉, 퐸 >, với tập đỉnh 푉 =
*1,2, … , 푛+, tập cạnh 퐸 = *푒1, 푒2, . . . , 푒푚+. Ta gọi ma trận kề
của đồ thị 퐺 là ma trận 푛 × 푛 có các phần tử hoặc bằng 0
hoặc bằng 1 theo qui định như sau:
o 퐴 = *푎푖푗: 푎푖푗 = 1 푛ế푢 (푖, 푗) ∈ 퐸, 푎푖푗 = 0 푛ế푢 (푖, 푗) ∉ 퐸; 푖, 푗 =
1, 2, . . . , 푛+.
(Phương ND, 2013)
3
Ma trận kề của đồ thị vô hướng (2/2)
Xét đồ thị vô hướng 퐺 =< 푉, 퐸 >, với tập đỉnh 푉 =
*1,2, … , 푛+, tập cạnh 퐸 = *푒1, 푒2, . . . , 푒푚+. Ta gọi ma trận kề
của đồ thị 퐺 là ma trận 푛 × 푛 có các phần tử hoặc bằng 0
hoặc bằng 1 theo qui định như sau:
o 퐴 = *푎푖푗: 푎푖푗 = 1 푛ế푢 (푖, 푗) ∈ 퐸, 푎푖푗 = 0 푛ế푢 (푖, 푗) ∉ 퐸; 푖, 푗 =
1, 2, . . . , 푛+.
1
1
0
(Phương ND, 2013)
4
Tính chất của ma trận kề đối với đồ thị vô hướng
Đối xứng qua đường chéo chính
Tổng các phần tử của ma trận bằng hai lần số cạnh
푛
푛
푖=1 푗=1 푎푖푗 = 2|퐸|
o
Tổng các phần tử của hàng 푢 là bậc của đỉnh 푢
푛
o
푗=1 푎푢푗 = deg(푢)
Tổng các phần tử của cột 푢 là bậc của đỉnh 푢
푛
o
푖=1 푎푖푢 = deg(푢)
Nếu ký hiệu 푎푖푝푗 (푖, 푗 = 1,2, … , 푛) là các phần tử của ma
trận 퐴푝 = 퐴. 퐴. . . 퐴 (푝 lần), khi đó 푎푖푝푗 cho ta số đường đi
khác nhau từ đỉnh 푖 đến đỉnh 푗 qua 푝 − 1 đỉnh trung gian
5
Ma trận kề của đồ thị có hướng (1/2)
Định nghĩa hoàn toàn tương tự với đồ thị vô hướng
o Cần lưu ý tới hướng của cạnh
o Ma trận kề của đồ thị có hướng là không đối xứng
(Phương ND, 2013)
6
Ma trận kề của đồ thị có hướng (2/2)
Định nghĩa hoàn toàn tương tự với đồ thị vô hướng
o Cần lưu ý tới hướng của cạnh
o Ma trận kề của đồ thị có hướng là không đối xứng
(Phương ND, 2013)
7
Tính chất của ma trận kề đối với đồ thị có hướng
Tổng các phần tử của ma trận bằng số cạnh
푛
푛
푖=1 푗=1 푎푖푗 = |퐸|
o
Tổng các phần tử của hàng 푢 là bán bậc ra của đỉnh 푢
푛
푗=1 푎푢푗 = 푑푒ꢀ+(푢)
o
Tổng các phần tử của cột 푢 là bán bậc vào của đỉnh 푢
푛
푖=1 푎푖푢 = 푑푒ꢀ−(푢)
o
Nếu ký hiệu 푎푖푝푗 (푖, 푗 = 1,2, … , 푛) là các phần tử của ma
trận 퐴푝 = 퐴. 퐴. . . 퐴 (푝 lần), khi đó 푎푖푝푗 cho ta số đường đi
khác nhau từ đỉnh 푖 đến đỉnh 푗 qua 푝 − 1 đỉnh trung gian
8
Ma trận trọng số
Mỗi cạnh 푒 = (푢, 푣) của đồ thị được gán bởi một số
푐(푒) = 푐(푢, 푣) gọi là trọng số của cạnh 푒
o Đồ thị trong trường hợp như vậy gọi là đồ thị trọng số
o Ma trận trọng số 푐 = 푐,푖, 푗-, 푐,푖, 푗- = 푐(푖, 푗) nếu (푖, 푗) ∈ 퐸,
푐,푖, 푗- = 휃 nếu (푖, 푗) ∉ 퐸. 휃 nhận các giá trị: 0, ∞, −∞ tuỳ theo từng
tình huống cụ thể của thuật toán
(Phương ND, 2013)
9
Ưu & nhược điểm của ma trận kề
Ưu điểm
o Đơn giản, dễ cài đặt trên máy tính
. Sử dụng một mảng hai chiều để biểu diễn ma trận kề
o Dễ dàng kiểm tra được hai đỉnh 푢, 푣 có kề với nhau hay không
. Đúng một phép so sánh (푎,푢-,푣- ≠ 0?)
Nhược điểm
o Lãng phí bộ nhớ: bất kể số cạnh nhiều hay ít ta cần 푛2 đơn vị bộ
nhớ để biểu diễn
o Không thể biểu diễn được với các đồ thị có số đỉnh lớn
o Để xem xét đỉnh đỉnh 푢 có những đỉnh kề nào cần mất 푛 phép so
sánh kể cả đỉnh 푢 là đỉnh cô lập hoặc đỉnh treo
10
Khuôn dạng lưu trữ ma trận kề
Dòng đầu tiên ghi lại số đỉnh của đồ thị
푛 dòng kế tiếp ghi lại ma trận kề của đồ thị
o Hai phần tử khác nhau của ma trận kề được viết cách nhau một
vài khoảng trống
11
Nội dung
Biểu diễn đồ thị bằng ma trận kề
Biểu diễn đồ thị bằng ma trận liên thuộc
Biểu diễn đồ thị bằng danh sách cạnh
Biểu diễn đồ thị bằng danh sách kề
12
Ma trận liên thuộc: Đồ thị vô hướng (1/2)
Xét đồ thị vô hướng 퐺 = (푉, 퐸), 푉 = *1,2, … , 푛+, 퐸 =
*푒1, 푒2, … , 푒푚+. Ma trận liên thuộc đỉnh-cạnh của 퐺 là ma
trận kích thước 푛 × 푚 được xây dựng như sau:
1,
푛ế푢 đỉ푛ℎ 푖 푙푖ê푛 푡ℎ푢ộ푐 푣ớ푖 푐ạ푛ℎ 푗
푎푖푗 =
0, 푛ế푢 đỉ푛ℎ 푖 푘ℎô푛ꢀ 푙푖ê푛 푡ℎ푢ộ푐 푣ớ푖 푐ạ푛ℎ 푗
6
9
1
7
3
5
2
8
4
13
Ma trận liên thuộc: Đồ thị vô hướng (2/2)
Xét đồ thị vô hướng 퐺 = (푉, 퐸), 푉 = *1,2, … , 푛+, 퐸 =
*푒1, 푒2, … , 푒푚+. Ma trận liên thuộc đỉnh-cạnh của 퐺 là ma
trận kích thước 푛 × 푚 được xây dựng như sau:
1,
푛ế푢 đỉ푛ℎ 푖 푙푖ê푛 푡ℎ푢ộ푐 푣ớ푖 푐ạ푛ℎ 푗
푎푖푗 =
0, 푛ế푢 đỉ푛ℎ 푖 푘ℎô푛ꢀ 푙푖ê푛 푡ℎ푢ộ푐 푣ớ푖 푐ạ푛ℎ 푗
1 2 3 4 5 6 7 8 9
6
1 1 1 0 0 0 0 0 0 0
2 1 0 1 0 1 1 0 0 0
3 0 1 1 1 0 0 0 0 0
4 0 0 0 1 1 0 1 1 0
5 0 0 0 0 0 1 1 0 1
6 0 0 0 0 0 0 0 1 1
9
1
7
3
5
4
2
8
14
Ma trận liên thuộc: Đồ thị có hướng (1/2)
Xét đồ thị có hướng 퐺 = (푉, 퐸), 푉 = *1,2, … , 푛+, 퐸 =
*푒1, 푒2, … , 푒푚+. Ma trận liên thuộc đỉnh-cung của 퐺 là ma
trận kích thước 푛 × 푚 được xây dựng như sau:
1, 푛ế푢 푖 푙à đỉ푛ℎ đầ푢 푐ủ푎 푐푢푛ꢀ 푒
푗
−1, 푛ế푢 푖 푙à đỉ푛ℎ 푐푢ố푖 푐ủ푎 푐푢푛ꢀ 푒
푎푖푗 =
푗
0, 푛ế푢 푖 푘ℎô푛ꢀ 푙à đầ푢 푚ú푡 푐ủ푎 푐푢푛ꢀ 푒
푗
6
9
8
1
7
3
5
2
4
15
Ma trận liên thuộc: Đồ thị có hướng (2/2)
Xét đồ thị có hướng 퐺 = (푉, 퐸), 푉 = *1,2, … , 푛+, 퐸 =
*푒1, 푒2, … , 푒푚+. Ma trận liên thuộc đỉnh-cung của 퐺 là ma
trận kích thước 푛 × 푚 được xây dựng như sau:
1, 푛ế푢 푖 푙à đỉ푛ℎ đầ푢 푐ủ푎 푐푢푛ꢀ 푒
푗
−1, 푛ế푢 푖 푙à đỉ푛ℎ 푐푢ố푖 푐ủ푎 푐푢푛ꢀ 푒
푎푖푗 =
푗
0, 푛ế푢 푖 푘ℎô푛ꢀ 푙à đầ푢 푚ú푡 푐ủ푎 푐푢푛ꢀ 푒
푗
1 2 3 4 5 6 7 8 9
1 1 -1 0 0 0 0 0 0 0
2 -1 0 1 0 1 1 0 0 0
3 0 1 -1 -1 0 0 0 0 0
4 0 0 0 1 -1 0 1 -1 0
5 0 0 0 0 0 -1 -1 0 1
6 0 0 0 0 0 0 0 1 -1
6
9
8
1
7
3
5
4
2
16
Nội dung
Biểu diễn đồ thị bằng ma trận kề
Biểu diễn đồ thị bằng ma trận liên thuộc
Biểu diễn đồ thị bằng danh sách cạnh
Biểu diễn đồ thị bằng danh sách kề
17
Danh sách cạnh (cung)
Trong trường hợp đồ thị thưa (푚 ≤ 6푛), ta thường biểu
diễn đồ thị dưới dạng danh sách cạnh
o Ta lưu trữ danh sách tất cả các cạnh (cung) của đồ thị vô hướng
(có hướng). Mỗi cạnh (cung) 푒(푥, 푦) được tương ứng với hai biến
푑푎푢,푒-, 푐푢표푖,푒-.
o Như vậy, để lưu trữ đồ thị, ta cần 2푚 đơn vị bộ nhớ
o Nhược điểm: để nhận biết những đỉnh nào kề với đỉnh nào chúng
ta cần 푚 phép so sánh trong khi duyệt qua tất cả 푚 cạnh (cung)
của đồ thị
o Nếu là đồ thị có trọng số, ta cần thêm 푚 đơn vị bộ nhớ để lưu trữ
trọng số của các cạnh
18
Biểu diễn đồ thị vô hướng
bằng danh sách cạnh
Chỉ cần liệt kê cạnh (푢, 푣), không cần liệt kê cạnh (푣, 푢)
Nên liệt kê các cạnh theo thứ tự tăng dần của đỉnh đầu
mỗi cạnh
Số cạnh có giá trị 푢 (phải hoặc trái) của danh sách cạnh
là bậc của đỉnh 푢
(Phương ND, 2013)
19
Biểu diễn đồ thị có hướng
bằng danh sách cạnh
Mỗi cạnh là bộ có tính đến thứ tự các đỉnh
o Đỉnh đầu không nhất thiết phải nhỏ hơn đỉnh cuối mỗi cạnh
Số cạnh có giá trị 푢 thuộc vế trái là 푑푒ꢀ+(푢)
Số cạnh có giá trị 푢 thuộc vế phải là 푑푒ꢀ−(푢)
(Phương ND, 2013)
20
Tải về để xem bản đầy đủ
35 trang
37200
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc 2 - Chương 2: Biểu diễn đồ thị trên máy tính - Ngô Xuân Bách", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_roi_rac_2_chuong_2_bieu_dien_do_thi_tren_may.pdf
