Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 1

Mở ñầu
Lý thuyết ñồ thị là một lĩnh vực ñã có từ lâu và có nhiều ứng dụng hiện ñại. Những
tư tưởng cơ bản của lý thuyết ñồ thị ñược ñề xuất vào những năm ñầu của thế kỷ 18 bởi
nhà toán học lỗi lạc người Thụy Sỹ Lenhard Eurler. Chính ông là người ñã sử dụng ñồ thị
ñể giải bài toán nổi tiếng về các cái cầu ở thành phố Konigsberg.
ðồ thị ñược sử dụng ñể giải các bài toán trong nhiều lĩnh vực khác nhau. Chẳng
hạn, ñồ thị có thể sử dụng ñể xác ñịnh các mạch vòng trong vấn ñề giải tích mạch ñiện.
Chúng ta có thể phân biệt các hợp chất hóa học hữu cơ khác nhau với cùng công thức
phân tử nhưng khác nhau về cấu trúc phân tử nhờ ñồ thị. Chúng ta có thể xác ñịnh hai
máy tính trong mạng có thể trao ñổi thông tin ñược với nhau hay không nhờ mô hình ñồ
thị của mạng máy tính. ðồ thị có trọng số trên các cạnh có thể sử dụng ñể giải các bài
toán như: Tìm ñường ñi ngắn nhất giữa hai thành phố trong mạng giao thông. Chúng ta
cũng còn sử dụng ñồ thị ñể giải các bài toán về lập lịch, thời khóa biểu, và phân bố tần số
cho các trạm phát thanh và truyền hình.
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 2

Mục lục
Mở ñầu 1
Mục lục 2
Danh mục các hình vẽ 4
Bài 1 Các khái niệm cơ bản của Lý thuyết ñồ thị 6
1.1 ðịnh nghĩa cơ bản về ñồ thị 6
1.2 ðường ñi. chu trình. ðồ thị liên thông 9

7.4. Thuật toán Prim 50
7.5 Thuật toán Kruskal 54
Bài 8 Thảo luận về cài ñặt thuật toán tìm cây khung nhỏ nhất trên ñồ thị 57
8.1. Cài ñặt xây dựng tập các chu trình cơ bản của ñồ thị 57
8.2. Cài ñặt thuật toán Prim 59
8.3. Cài ñặt thuật toán Kruskal 60
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 3

8.4. Một số thuật toán xây dựng cây khung(*) 62
Bài 10 Bài toán tìm ñường ñi ngắn nhất 65
10.1. Các khái niệm mở ñầu 65
10.2. ðường ñi ngắn nhất xuất phát từ một ñỉnh. Thuật toán Ford-Bellman 66
10.3. Trường hợp ma trận trọng số không âm. Thuật toán Dijkstra 67
Bài 11 Bài toán tìm ñường ñi ngắn nhất (tiếp) 69
11.1 ðường ñi trong ñồ thị không có chu trình 69
11.2 ðường ñi ngắn nhất giữa tất cả các cặp ñỉnh 74
11.3 Cài ñặt thuật toán Dijkstra 75
Bài 12 Bài toán luồng cực ñại trong mạng 76
12.1. Mạng. Luồng trong mạng. Bài toán luồng cực ñại 76
12.2. Lát cắt. ñường tăng luồng. ðịnh lý ford_fulkerson 77
12.3. Thuật toán tìm luồng cực ñại 81
Bài 13 Lý thuyết ñồ thị và ứng dụng 91
13.1. Các bài toán liên quan tới ñồ thị 91
13.1.1 Các bài toán liên quan tới bậc của ñồ thị 91
13.1.2 Các bài toán liên quan ñến tính liên thông của ñồ thị 93
13.1.3 Các bài toán liên quan tới chu trình 94
13.1.4 Các bài toán có liên quan ñến ñường ñi và chu trình Hamilton 96

Hình 1.6 ðồ thị G và H 10
Hình 1.7 ðồ thị liên thông mạnh G và ñồ thị liên thông yếu H. 12
Hình 1.8 ðồ thị vô hướng 13
Hình 1.9 ðồ thị có hướng. 14
Hình 1.10 ðồ thị ñầy ñủ 15
Hình 1.11 ðồ thị vòng C
3
, C
4
, C
5
, C
6
16
Hình 1.12 ðồ thị bánh xe W
3
, W
4
, W
5
, W
6
. 16
Hình 1.13 ðồ thị lập phương Q
1
, Q
2
, Q
3
. 16

1
34
Hình 4.3 ðồ thị ñấu loại D
5
, ñấu loại liên thông mạnh D
6
. 36
Hình 4.4 ðồ thị và cây liệt kê chu trình Hamilton của nó theo thuật toán quay lui. 37
Hình 5.1 ðồ thị và cây liệt kê chu trình Hamilton của nó theo thuật toán quay lui. 40
Hình 6.1 ðồ thị vô hướng 42
Hình 7.1 Cây và rừng 45
Hình 7.2 ðồ thị và các cây khung của nó. 47
Hình 7.3 ðồ thị và cây khung nhỏ nhất 53
Hình 8.1 Hệ chu trình ñộc lập cho ñồ thị vô hướng G 57
Hình 8.2 Hệ chu trình ñộc lập cho ñồ thị có hướng G
1
57
Hình 8.3 Minh họa từng bước thuật toán Prim tìm cây khung nhỏ nhất 60
Hình 8.4 Minh họa từng bước thuật toán Kruskal tìm cây khung nhỏ nhất 61
Hình 11.1 ðồ thị không có chu trình. 69
Hình 11.2 ðồ thị minh hoạ PERT 73
Hình 12.1 Mạng G và luồng f. ðồ thị có trọng số G
f
tương ứng 79
Hình 12.2 Mạng G và minh họa từng bước thuật toán Ford-Fullkerson 86
Hình 12.3 Mạng G với luồng cực ñại và lát cắt hẹp nhất 87
Hình 12.4 Ví dụ tồi tệ ñối với thuật toán Ford_Fulkerson. 89
Hình 12.5 Tăng luồng dọc theo ñường tăng. 90
Hình 13.1 Kết quả thi ñấu của 5 ñội bóng chuyền A, B, C, B, E 96
Hình 13.2 Sơ ñồ nhà của 8 học sinh 97

Bài 1 Các khái niệm cơ bản của Lý thuyết ñồ thị.
1.1 ðịnh nghĩa cơ bản về ñồ thị
ðồ thị là một cấu trúc rời rạc bao gồm các ñỉnh và các cạnh nối các ñỉnh này.
Chúng ta phân biệt các loại ñồ thị khác nhau bởi kiểu và số lượng cạnh nối hai ñỉnh nào
ñó của ñồ thị. ðể có thể hình dung ñược tại sao lại cần ñến các loại ñồ thị khác nhau,
chúng ta sẽ nêu ví dụ sử dụng chúng ñể mô tả một mạng máy tính. Giả sử ta có một mạng
gồm các máy tính và các kênh ñiện thoại (gọi tắt là kênh thoại) nối các máy tính này.
Chúng ta có thể biểu diễn các vị trí ñặt náy tính bởi các ñiểm và các kênh thoại nối chúng
bởi các ñoạn nối, xem hình 1.1.

Hình 1.1 Sơ ñồ mạng máy tính.
Nhận thấy rằng trong mạng ở hình 1.1, giữa hai máy bất kỳ chỉ có nhiều nhất là một kênh
thoại nối chúng, kênh thoại naỳ cho phép liên lạc cả hai chiều và không có máy tính nào
lại ñược nối với chính nó. Sơ ñồ mạng máy cho trong hình 1 ñược gọi là ñơn ñồ thị vô
hướng. Ta ñi ñến ñịnh nghĩa sau
ðịnh nghĩa 1.1
ðơn ñồ thị vô hướng G = (V,E) bao gồm V là tập các ñỉnh, và E là tập các cặp không có
thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh.
Trong trường hợp giữa hai máy tính nào ñó thường xuyên phải truyền tải nhiều
thông tin người ta phải nối hai máy nàu bởi nhiều kênh thoại. Mạng với ña kênh thoại
giữa các máy ñược cho trong hình 1.2.
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 7Hình 1.2 Sơ ñồ mạng máy tính với ña kênh thoại.
ðịnh nghĩa 1.2
ða ñồ thị vô hướng G= (V, E) bao gồm V là tập các ñỉnh, và E là tập các cặp không có

chiều ñược thay thế bởi hai cạnh có hướng ngược chiều nhau.
Ta ñi ñến ñịnh nghĩa sau.
ðịnh nghĩa 1.4
ðơn ñồ thị có hướng G = (V, E) bao gồm V là tập các ñỉnh và E là tập các cặp có thứ tự
gồm hai phần tử khác nhau của V gọi là các cung.
Nếu trong mạng có thể có ña kênh thoại một chiều, ta sẽ phải sử dụng ñến khái niệm ña
ñồ thị có hướng:
ðịnh nghĩa 1.5
ða ñồ thị có hướng G = (V, E) bao gồm V là tập các ñỉnh và E là tập các cặp có thứ tự
gồm hai phần tử khác nhau của V gọi là các cung. Hai cung e
1
, e
2
tương ứng với cùng
một cặp ñỉnh ñược gọi là cung lặp.
Trong các phần tiếp theo chủ yếu chúng ta sẽ làm việc v?i ñơn ñồ thị vô hướng và
ñơn ñồ thị có hướng. Vì vậy, ñể cho ngắn gọn, ta sẽ bỏ qua tính từ ñơn khi nhắc ñến
chúng.
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 9

1.2 ðường ñi. chu trình. ðồ thị liên thông
ðịnh nghĩa 1.6
ðường ñi ñộ dài n từ ñỉnh u ñến ñỉnh v, trong ñó n là số nguyên dương, trên ñồ thị vô
hướng G = (V, E) là dãy x
0
, x
1

trùng với ñỉnh cuối (tức là u = v) ñược gọi là chu trình. ðường ñi hay chu trình ñược gọi
là ñơn nếu như không có cạnh nào bị lặp lại.
Ví dụ 1.1 Trên ñồ thị vô hướng cho trong Hình 1.5: a, d, c, f, e là ñường ñi ñơn ñộ dài 4.
Còn d, e, c, a không là ñường ñi, do (c,e) không phải là cạnh của ñồ thị. Dãy b, c, f, e, b là
chu trình ñộ dài 4. ðường ñi a, b, e, d, a, b có ñộ dài là 5 không phải là ñường ñi ñơn, do
cạnh (a, b) có mặt trong nó 2 lần.

Hình 1.5 ðường ñi trên ñồ thị
Khái niệm ñường ñi và chu trình trên ñồ thị có hướng ñược ñịnh nghĩa hoàn toàn
tương tự như trong trường hợp ñồ thị vô hướng, chỉ khác là ta có chú ý ñến hướng trên
các cung.
ðịnh nghĩa 1.7
ðường ñi ñộ dài n từ ñỉnh u ñến ñỉnh v, trong ñó, n là số nguyên dương, trên ñồ thị có
hướng G = (V, A) là dãy x
0
, x
1
,…, x
n-1
, x
n

trong ñó u = x
0
, v = x
n
, (xi, x
i+1
)
∈

máy tính này (trong ñó các ñỉnh của ñồ thị tương ứng với các máy tính, còn các cạnh
tương ứng với các kênh nối) câu hỏi ñó ñược phát biểu trong ngôn ngữ ñồ thị như sau:
Tồn tại hay không ñường ñi giữa mọi cặp ñỉnh của ñồ thị.
ðịnh nghĩa 1.8
ðồ thị vô hướng G = (V, E) ñược gọi là liên thông nếu luôn tìm ñược ñường ñi giữa hai
ñỉnh bất kỳ của nó.
Như vậy hai máy tính bất kỳ trong mạng có thể trao ñổi thông tin ñược với nhau
khi và chỉ khi ñồ thị tương ứng với mạng này là ñồ thị liên thông.
Ví dụ 1.3 Trong Hình 1.6: ðồ thị G là liên thông, còn ñồ thị H là không liên thông.

Hình 1.6 ðồ thị G và H.
ðịnh nghĩa 1.9
Ta gọi ñồ thị con của ñồ thị G = (V, E) là ñồ thị H = (W, F), trong ñó W
⊆
V và F
⊆
E.
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 11

Trong trường hợp ñồ thị là không liên thông, nó sẽ rã ra thành một số ñồ thị con
liên thông ñôi một không có ñỉnh chung. Những ñồ thị con liên thông như vậy ta sẽ gọi là
các thành phần liên thông của ñồ thị.
Ví dụ 1.4. ðồ thị H trong hình 2 gồm 3 thành phần liên thông H
1
, H
2
, H

Một câu hỏi ñặt ra là khi nào có thể ñịnh hướng các cạnh của một ñồ thị vô hướng
liên thông ñể có thể thu ñược ñồ thị có hướng liên thông mạnh? Ta sẽ gọi ñồ thị như vậy
là ñồ thị ñịnh hướng ñược. ðịnh lý dưới ñây cho ta tiêu chuẩn nhận biết một ñồ thị có là
ñịnh hướng ñược hay không.
ðịnh lý 1.1
ðồ thị vô hướng liên thông là ñịnh hướng ñược khi và chỉ khi mỗi cạnh của nó nằm trên ít
nhất một chu trình.
Chứng minh.
ðiều kiện cần. Giả sử (u,v) là một cạnh của một ñồ thị. Từ sự tồn tại ñường ñi có hướng
từ u ñến v và ngược lại suy ra (u, v) phải nằm trên ít nhất một chu trình.
ðiều kiện ñủ. Thủ tục sau ñây cho phép ñịnh hướng các cạnh của ñồ thị ñể thu ñược ñồ
thị có hướng liên thông mạnh. Giả sử C là một chu trình nào ñó trong ñồ thị. ðịnh hướng
các cạnh trên chu trình này theo một hướng ñi vòng theo nó. Nếu tất cả các cạnh của ñồ
thị là ñã ñược ñịnh hướng thì kết thúc thủ tục. Ngược lại, chọn e là một cạnh chưa ñịnh
hướng có chung ñỉnh với ít nhất một trong số các cạnh ñã ñịnh hướng. Theo giả thiết tìm
ñược chu trình C’ chứa cạnh e. ðịnh hướng các cạnh chưa ñược ñịnh hướng của C’ theo
một hướng dọc theo chu trình này (không ñịnh hướng lại các cạnh ñã có ñịnh hướng). Thủ
tục trên sẽ ñược lặp lại cho ñến khi tất cả các cạnh của ñồ thị ñược ñịnh hướng. Khi ñó ta
thu ñược ñồ thị có hướng liên thông mạnh.
1.3. Phân loại ñồ thị
1.3.1. ðồ thị vô hướng liên thông
Trong mục này chúng ta sẽ trình bày một số thuật ngữ cơ bản của lý thuyết ñồ thị.
Trước tiên, ta xét các thuật ngữ mô tả các ñỉnh và cạnh của ñồ thị vô hướng.
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 13

ðịnh nghĩa 1.13
Hai ñỉnh u và v của ñồ thị vô hướng G ñược gọi là kề nhau nếu (u,v) là cạnh của ñồ thị G.

∑
∈∈
+
=
OvUv
vvm )deg()deg(2

Do deg(v) là chẵn với v là ñỉnh trong U nên tổng thứ nhất ở trên là số chẵn. Từ ñó
suy ra tổng thứ hai (chính là tổng bậc của các ñỉnh bậc lẻ) cũng phải là số chẵn, do tất cả
các số hạng của nó là số lẻ, nên tổng này phải gồm một số chẵn các số hạng. Vì vậy, số
ñỉnh bậc lẻ phải là số chẵn.
Ta xét các thuật ngữ tương tự cho ñồ thị vô hướng.
1.3.2. ðồ thị có hướng liên thông
ðịnh nghĩa 1.15
Nếu e = (u, v) là cung của ñồ thị có hướng G thì ta nói hai ñỉnh u và v là kề nhau, và nói
cung (u, v) nối ñỉnh u với ñỉnh v hoặc cũng nói cung này là ñi ra khỏi ñỉnh u và vào ñỉnh
v. ðỉnh u(v) sẽ ñược gị là ñỉnh ñầu (cuối) của cung (u,v).
Tương tự như khái niệm bậc, ñối với ñồ thị có hướng ta có khái niệm bán bậc ra và
bán bậc vào của một ñỉnh.
ðịnh nghĩa 1.16
Ta gọi bán bậc ra (bán bậc vào) của ñỉnh v trong ñồ thị có hướng là số cung của ñồ thị ñi
ra khỏi nó (ñi vào nó) và ký hiệu là deg
+
(v) (deg
-
(v))

Hình 1.9 ðồ thị có hướng.
Ví dụ 1.9 Xét ñồ thị cho trong hình 1.10. Ta có
deg

deg ( ) deg ( )
v v
+ −
+
∑ ∑

Rất nhiều tính chất của ñồ thị có hướng không phụ thuộc vào hướng trên các cung
của nó. Vì vậy, trong nhiều trường hợp sẽ thuận tiện hơn nếu ta bỏ qua hướng trên các
cung của ñồ thị. ðồ thị vô hướng thu ñược bằng cách bỏ qua hướng trên các cung ñược
gọi là ñồ thị vô hướng tương ứng với ñồ thị có hướng ñã cho.
1.4. Một số loại ñồ thị ñặc biệt
Trong mục này ta xét một số ñơn ñồ thị vô hướng dạng ñặc biệt xuất hiện trong
nhiều vấn ñề ứng dụng thực tế.
ðồ thị ñầy ñủ.
ðồ thị ñầy ñủ n ñỉnh, ký hiệu bởi K
n
, là ñơn ñồ thị vô hướng

mà giữa hai ñỉnh bất
kỳ của nó luôn có cạnh nối.
Các ñồ thị K
3
, K
4
, K
5
cho trong hình dưới ñây.

Hình 1.10 ðồ thị ñầy ñủ.
ðồ thị ñầy ñủ K

3
, C
4
, C
5
, C
6
cho trong hình 2.2
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 16Hình 1.11 ðồ thị vòng C
3
, C
4
, C
5
, C
6
.
ðồ thị bánh xe.
ðồ thị W
n
thu ñược từ C
n
bằng cách bổ sung vào một ñỉnh mới nối với tất cả các
ñỉnh của C


ðồ thị hai phía.
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 17

ðơn ñồ thị G = (V, E) ñược gọi là hai phía nếu như tập ñỉnh V của nó có thể phân
hoạch thành hai tập X và Y sao cho mỗi cạnh của ñồ thị chỉ nối một ñỉnh nào ñó trong X
với một ñỉnh nào ñó trong Y. Khi ñó ta sẽ sử dụng ký hiệu G = (X∪Y, E) ñể chỉ ñồ thị hai
phía với tập ñỉnh X∪Y.
ðịnh lý sau ñây cho phép nhận biết một ñơn ñồ thị có phải là hai phía hay không.
ðịnh lý 1.4 ðơn ñồ thị là ñồ thị hai phía khi và chỉ khi nó không chứa chu trình ñộ dài lẻ.
ðể kiểm tra xem một ñồ thị liên thông có phải là hai phía hay không có thể áp
dụng thủ tục sau. Cho v là một ñỉnh bất kỳ của ñồ thị. ðặt X={v}, còn Y là tập các ñỉnh
kề của v. Khi ñó các ñỉnh kề của các ñỉnh trong Y phải thuộc vào X. Ký hiệu tập các ñỉnh
như vậy là T. Vì thế nếu phát hiện T ∩ Y ≠ ∅ thì ñồ thị không phải là hai phía, kết thúc.
ngược lại, ñặt X = X ∪ T. Tiếp tục xét như vậy ñối với T’ là tập các ñỉnh kề của T,.
ðồ thị hai phía G=(X ∪ Y, E) với |X|= m, |Y| = n ñược gọi là ñồ thị hai phía ñầy
ñủ và ký hiệu là K
2,3,
K
3,3,
K
3,4
ñược cho trong hình 2.5.

Hình 1.14 ðồ thị hai phía.
ðồ thị phẳng.
ðồ thị ñược gọi là ñồ thị phẳng nếu ta có thể vẽ nó trên mặt phẳng sao cho các

.
Trong trường hợp riêng, ñồ thị K
3,3
hoặc K
5
không phải là ñồ thị phẳng. Bài toán về
tính phẳng của ñồ thị K
3,3
là bài toán ñố nổi tiếng về ba căn hộ và ba hệ thống cung cấp
năng lượng cho chúng: Cần xây dựng hệ thống ñường cung cấp năng lượng với mỗi một
căn hộ nói trên sao cho chúng không cắt nhau.
ðồ thị phẳng còn tìm ñược những ứng dụng quan trọng trong công nghệ chế tạo
mạch in.
Biểu diễn phẳng của ñồ thị sẽ chia mặt phẳng ra thành các miền, trong ñó có thể có
cả miền không bị chặng. Ví dụ, biểu diễn phẳng của ñồ thị cho trong Hình 1.16 chia mặt
phẳng ra thành 6 miền R
1,
R
2,
. . . .R
6
.

Hình 1.16 Các miền tương ứng với biểu diễn phẳng của ñồ thị.
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 19

Euler ñã chứng minh ñược rằng các cách biểu diễn phẳng khác nhau của một ñồ thị

1
,
e
2
, . . . ,e
m
}

. Ta gọi ma trận kề của ñồ thị G là ma trận.
A=( a
i,j
: i, j = 1, 2, . . . ,n)
Với các phần tử ñược xác ñịnh theo qui tắc sau ñây:
a
i,j
= 1 , nếu có cạnh từ i sang j hay (i, j) ∈ E, i, j =1, 2,. . ., n.
a
i, j
= 0, trong trường hợp còn lại tức là không có cạnh(i, j)
Ví dụ 2.1 Ma trận trận kề của ñồ thị vô hướng G cho trong Hình 2.1 là:

1

2

3

4

5


3

1

1

0

1

0

0

4

0

0

1

0

1

1

5

Trang 21Hình 2.1 ðồ thị vô hướng G và ðồ thị có hướng G
1
.
Các tính chất của ma trận kề:
1) Rõ ràng ma trận kề của ñồ thị vô hướng là ma trận ñối xứng, tức là
a[i,j]=a[j,i], i,j =1,2,. . .,n. Ngược lại, mỗi (0,1)-ma trận ñối xứng cấp n sẽ tương ứng,
chính xác ñến cách ñánh số ñỉnh (còn nói là: chính xác ñến ñẳng cấu), với một ñơn ñồ thị
vô hướng n ñỉnh.
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).
3) nếu ký hiệu a
ịj
p
, i,j=1, 2,. . . ,n là phần tử của ma trận A
p
=A.A. . .A p thừa số. Khi ñó
a
ịj
p
, i,j=1, 2,. . . ,n cho ta số ñường ñi khác nhau từ ñỉnh i ñến ñỉnh j qua p-1 ñỉnh trung
gian.
Ma trận kề của ñồ thị có hướng ñược ñịnh nghĩa một cách hoàn toàn tương tự.
Ví dụ 2.2 ðồ thị có hướng G
1
cho trong Hình 2.1 có ma trận kề là ma trận sau:

1


0

0

0

0

3

0

1

0

1

0

0

4

0

0

0


1

0

Lưu ý rằng ma trận kề của ñồ thị có hướng không phải là ma trận ñối xứng.
Chú ý: Trên ñây chúng ta chỉ xét ñơn ñồ thị. Ma trận kề của ña ñồ thị có thể xây dựng
hoàn toàn tương tự, chỉ khác là thay vì ghi 1 vào vị trí a[i,j] nếu (i,j) là cạnh của ñồ thị,
chúng ta sẽ ghi k là số cạnh nối hai ñỉnh i, j.
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 22

Trong rất nhiều vấn ñề ứng dụng của lý thuyết ñồ thị, mỗi cạnh e=(u,v) của ñồ thị
ñược gán với một con số c(e) (còn viết là c(u,v) gọi là trọng số của cạnh e. ðồ thị trong
trường hợp như vậy ñược gọi là ñồ thị có trọng số. Trong trường hợp ñồ thị có trọng số,
thay vì mà trận kề, ñể biểu diễn ñồ thị ta sử dụng ma trận trọng số.
C= {c[i,j], i, j = 1, 2,. . ., n}
với c[i,j]=c(i,j) nếu (i,j) ∈ E và c[i,j]= δ nếu (i, j) ∉ E
trong ñó số δ , tuỳ từng trường hợp cụ thể, có thể ñược ñặt bằng một trong các giá trị sau :
0, +
∞
, -
∞
.
Ưu ñiểm lớn nhất của phương pháp biểu diễn ñồ thị bằng ma trận kề (hoặc ma trận
trọng số) là ñể trả lời câu hỏi: Hai ñỉnh u, v có kề nhau trên ñồ thị hay không, chúng ta chỉ
phải thực hiện một phép so sánh. nhược ñiểm lớn nhất của phương pháp này là : không
phụ thuộc vào số cạnh của ñồ thị, ta luôn phải sử dụng n
2

2 3 3 4
2 5 5 4
3 4 5 6
4 5 6 5
4 6
5 6
Danh sách cạnh của G Danh sánh cung của G
1

2.2.3. Danh sách kề
Trong rất nhiều vấn ñề ứng dụng của lý thuyết ñồ thị, cách biểu diễn ñồ thị dưới
dạng danh sách kề là cách biểu diễn thích hợp nhất ñược sử dụng.
Trong cách biểu diễn này, với mỗi ñỉnh v của ñồ thị chúng ta lưu trữ danh sách các ñỉnh
kề với nó, mà ta sẽ ký hiệu là
Ke(v)= { u ∈ V: (v,u)∈ E }
Khi ñó vòng lặp thực hiện với mỗi một phần tử trong danh sách này theo thứ tự các
phần tử ñược sắp xếp trong nó sẽ ñược viết như sau:
for u ∈ Ke(v) do. . .
Chẳng hạn, trên PASCAL có thể mô tả danh sách này như sau (Gọi là cấu trúc Forward
Star):
Const
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010

Trang 24

m=1000; {m-so canh}
n= 100; {n-so dinh}
var
Ke: array[1 m] of integer;

v:integer;
next:link;
End;
Var
j,x,y,m,n,u,v:integer;
t:link;
Ke:array[1. .Vmax] of link;
Begin
Write(‘Cho so canh va dinh cua do thi:’);
readln(m,n);
(*Khoi tao*)
for j:=1 to n do Ke[j]:=nil;
for j:=1 to m do
begin
write(‘Cho dinh dau va cuoi cua
canh ‘,j,’:’);
readln(x,y);
new(t); t^.v:=x, t^.next:=Ke[y];
Ke[y]:=t;
new(t); t^.v:=y, t^.next:=Ke[x];
Ke[x]:=t;
end;
writeln(‘Danh sach ke cua cac dinh cua do
thi:’);
for J:=1 to m do
begin