TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2 KHOA TOÁN
NGUYỄN THÚY LINH
NHỮNG VẤN ĐÊ Cơ BẢN VÀ MỘT SỐ THUẬT
TOÁN TRÊN ĐỒ THỊ
KHÓA LUÂN TỐT NGHIÊP ĐAI HOC • • • •
Chuyên ngành: ứng dụng
Ngưòi hướng dẫn khoa học TS. TRẦN MINH TƯỚC
HÀ NỘI - 2014
________•__________
Trong quá trình thực hiện khoá luận em đã nhận được nhiều sự giúp
đỡ quý báu và bổ ích từ các thầy cô và bạn bè. Em xin chân thành cảm ơn
các thầy cô trong khoa Toán trường Đại học Sư phạm Hà Nội 2 đã tận tâm
giảng dạy, truyền thụ kiến thức và kinh nghiệm quý báu để em hoàn thành
tốt khoá học. Đặc biệt, em xin bày tỏ lòng cảm ơn sâu sắc của mình tới
thầy Trần Minh Tước, thầy đã trực tiếp hướng dẫn, nhiệt tình giúp đỡ và
chỉ bảo em ừong suốt quá trình thực hiện khoá luận.
Em xin chân thành cảm ơn các thầy cô trong tổ toán ứng dụng - khoa
Toán, thư viện nhà trường, gia đình và bạn bè đã tạo mọi điều kiện, động
viên, giúp đỡ để em hoàn thành khoá luận này.
Xuân Hòa, ngày 06 tháng 5 năm 2014
Sinh viên
Nguyễn Thúy Linh
LỜI CẢM ƠN
Tôi cam đoan khoá luận “Những vẩn đề cơ bản và một sổ thuật toán trên
đồ thị” là kết quả nghiên cứu của tôi dưới sự hướng dẫn của TS.Trần Minh
Tước. Tôi xin khẳng định kết quả nghiên cứu trong khoá luận này không
sao chép kết quả của bất cứ tác giả nào khác. Nếu sai sót tôi xin chịu hoàn
toàn trách nhiệm.
Xuân Hòa, ngày 06 tháng 5 năm 2014
Sinh viên
Nguyễn Thúy Linh

5
Ta có thể hình dung đồ thị như tập hữu hạn các đối tượng và những mối
liên hệ giữa các đối tượng đó. Sơ đồ biểu diễn một mạng máy tính là một hình
ảnh của đồ thị. Các đối tượng là các máy tính, mỗi kênh thoại sẽ biểu diễn mối
liên hệ giữa hai máy tính trong mạng.
Có nhiều loại đồ thị được xây dựng dựa vào cấu trúc của đồ thị, cụ thể là
tùy thuộc vào sự xác định mối liên hệ giữa các đối tượng. Khuôn khổ khóa
luận này tôi chỉ đề cập tới đồ thị vô hướng và đồ thị vô hướng có trọng số.
Định nghĩa 1.1. Đồ thị là một cặp G = (y,E) gồm hai tập hợp hữu hạn
VvàEthỏa mãn điều kiện £c{{m,v}Im , v g V;m^v}
Phần tử của V được gọi là đỉnh, phần tử của E được gọi là cạnh của đồ
thị G.
Người ta thường ký hiệu V = {v
1
,v
2
, ,v
n
},cạnh e = {u,v} thường viết gọn
hơn là uv (cũng trùng với vu).
Trong định nghĩa này, mỗi phàn tử của E là một tập gồm hai phần tử khác
nhau thuộc V. Như vậy, các đồ thị được xét ở đây là các đồ thị hữu hạn, không
có khuyên và cạnh bội (xem [1]), gọi tắt là đồ thị.
Một cách trực quan, người ta thường biểu diễn đồ thị bằng sơ đồ đỉnh -
cạnh như sau:
- Biểu diễn mỗi đỉnh của đồ thị bằng một vòng tròn nhỏ (rỗng hoặc
đặc).
- Một cạnh được biểu diễn bởi một đoạn (cong hay thẳng) nối hai
6
đỉnh liên thuộc với cạnh đó.

, V
3
V
4
, V
3
V
5
, V
3
V
7
, V
4
V
6
, V
3
V
6
, V
6
V
7
}
là đồ thị được biểu diễn trong hình 1.
Hình 2. Đồ thị G và các đồ thị con G' và G" của G .
Định nghĩa 1.3. Đồ thị G = (V,E) được gọi là đồ thị có trọng số nếu hàm:
W:E—>W
E

, V
2
V
7
, V
3
V
4
, V
3
V
5
, V
4
V
5
, V
5
V
6
, V
6
V
7
} Và
w:E—>W
e
được xác định như sau: wCvxV
7
) = w(v

v
6
)
= 6 ; w(v
2
v
6
) = 7 IQii đó G là đồ thị có ừọng số được biểu diễn bởi hình
3.
1.2. Các thuật ngữ cơ bản
1.2.1. Liên thuộc, kề
Định nghĩa 1.4. Giả sử G = (V,E)là đồ thị không rỗng với V e V và
ể g £ , ta nói đỉnh V liên thuộc với cạnh e (hay cạnh e liên thuộc với đỉnh v)
neu V e e. Các đỉnh liên thuộc vón một cạnh được gọi là các đầu mút của
cạnh đó.
Hai đỉnh uvàv của G được gọi là kề nhau nểu uv là một cạnh của
8
Hình 3. Đồ thị có trọng số G
G.
Ví dụ.
Hình 4. Đơn đồ thị G Xét
đồ thị G được cho trong hình 4:
Đỉnh v
l
liên thuộc với Ểj,Ể
2
Đỉnh v
2
kề với các đỉnh v
15

5
là đỉnh cô lập, V! là đỉnh ừeo.
Định lý 1.1.[2] Trong đồ thị G = (V, E) bất kì ta luôn có
Ỵ
d
degiý)=im □
veV
*Nhận xét: Ta thấy rằng mỗi cạnh e = uv được tính một làn trong deg(u) và một
lần trong deg{v). Từ đó ta suy ra được rằng tổng của tất cả các bậc của các đỉnh
bằng hai lần số cạnh.
1.2.3. Đường đi, chu trình
Định nghĩa 1.6. Giả sử G = (y,E)là đồ thị không rỗng, một đường đi trong G là
một dãy phân biệt các đỉnh v
ữ
,v
v
v
2
, ,v
n
, Vị GVsao cho VịV
i+l
G E với mọi ỉ =
0,l, ,n-l. Khi đó n được gọi là độ dài, đỉnh v
0
được gọi là đỉnh đầu, còn đỉnh V
được gọi là đỉnh cuối của đường đi trên.
Một đường đi được gọi là chu trình nểu đỉnh đầu và đỉnh cuối của nó
trùng nhau.
Ví dụ. Giả sử G = (V, E) là đồ thị như ở hình 6.

1
Trong trường hợp ngược lại, đồ thị được gọi là không liên thông.
Ví dụ. Đồ thị G = (V,E) cho ttong hình 7 là đồ thị liên thông.
v
2
Như vậy có thể thấy một đồ thị G không liên thông là tập họp các đồ thị
liên thông.
Mỗi đồ thị liên thông là đồ thị con của G và được gọi là một thành phần
liên thông của đồ thị G đã cho.
Ví dụ. Đồ thị G = (Y,E) cho trong hình 8 là đồ thị không liên thông. Nó gồm 3
thành phần liên thông G
V
G
2
,G
3
.
G
Hình 8. Đồ thị G không liên thông.
1.2.5. Đỉnh cắt
Định nghĩa 1.8. Giả sử G = (y,E) là đồ thị không rỗng với V là một đỉnh của G.
Đỉnh V được gọi là đỉnh cắt nếu khi loại bỏ V cùng với các cạnh liên thuộc với
nó thì đồ thị nhận được sẽ có số thành phần liên thông lớn hơn sổ thành phần
liên thông của đồ thị ban đầu.
Ví dụ. Trong đồ G thị ở hình 9, đỉnh v
2
,v
3
là đỉnh cắt.
1

.
Ví dụ. Các đồ thị K
2
,K
3
,K
4
,K
5
cho trong hình 11 dưới đây.
Hình 11. Đồ thị đầy đủ Có thể thấy rằng đồ thị đầy
đủ K
n
có tất cả —— = cị cạnh, nó
1
Hình 10. Cạnh càu ừên đồ thị G
là đồ thị có nhiều cạnh nhất.
1.3.2. Đồ thị vòng
Đồ thị gồm n đỉnh v
15
v
2
, ,v (n > 3) và các cạnh VJV
2
, V
2
V
3
,
Vi*». v„v

,W
5
,W
6
cho trong hình 13.
W,
Hình 13. Đồ thị bánh xe W
3
,W
4
,W
5
,W
6
1.3.4. Đồ thị hai phía
Đồ thị G = (У, 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ỉ
1
nối một đỉnh nào đó trong X với một đỉnh nào đó ừong Y. Khi đó ta sẽ sử dụng
ký hiệu G =(Xu Y, E) để chỉ đồ thị hai phía với tập đỉnh Xu Y.
Đồ thị hai phía G = (Zu Y, E) với \х\ = т,\у\ = п được gọi là đồ thị hai phía
đầy đủ và kí hiệu là K
m n
nếu mỗi đỉnh trong tập X đều được nối với mỗi đỉnh
trong Y.
Ví dụ. Các đồ thị K
23
,K
33
,K

- by = w 0ỉ .vị) nếu VỊV j G E,
nếu i = j và v,v
;
Ể E.
J 1
]
- h = 0
1
a
u ^12
A =[flÿ]„
xn
=
a
2l
a
22
_
a
nl
a
n2
- а
у
= 1 nếu V^e£,
- a
tj
= 0 nếu VịVj Ể E.
, trong đó:
0 1 1 0 0 0

m
}.
Khi đó ma trận liên thuộc của đồ thị G là:
1
V
>
1
v
0
2
00
00
00
3
2
0
5
В
c
nl
C
n2
- a-=0 nếu canh e, liên thuôc với đỉnh V
1J • 3 • l
- Cịị = 1 nếu cạnh e
]
liên ứiuộc với đừih V
Ví dụ. Giả sử G = (V, E) là đồ thị với tập đỉnh V - {v
1
,v

- Biểu diễn phức tạp nếu đồ thị có số lượng cạnh nhiều.
2.3. Ý nghĩa của các cách biểu diễn đồ thị
Trong những ứng dụng rộng rãi của đồ thị đối với các lĩnh vực khoa
1
c
= [CyU =
. , trong
C
ll
C
12
C
21
học khác và đối với thực tế cuộc sống, việc biểu diễn đồ thị đóng một vai trò
quan trọng.
Biểu diễn đồ thị với sơ đồ đỉnh cạnh được dừng khi muốn mô hình hóa
nhiều bài toán trong thực tế.
Với các loại ma ừận (kề, liên thuộc, ừọng số) và một số cách biểu diễn
khác nữa không được đề cập ở đây (Xem [1]), người ta sẽ mô phỏng được đồ
thị ừong các hệ thống máy tính thuận tiện cho việc lập trình.
Phối hợp cả hai dạng biểu diễn nói ừên, việc lập trình giải quyết nhiều bài
toán thực tế sẽ trở nên đơn giản, thuận tiện hơn.
Chương 2
MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ
1. Bài toán duyệt đồ thị
Một bài toán quan trọng trong lý thuyết đồ thị là bài toán duyệt đồ thị. Ta
phải duyệt qua tất cả các đỉnh của đồ thị, bắt đầu từ một đỉnh xuất phát nào đó.
Vấn đề này đưa về một bài toán liệt kê mà yêu càu của nó là không được bỏ
sót và cũng không được lặp lại bất kỳ đỉnh nào. Chính vì vậy mà ta phải xây
dựng những thuật toán cho phép duyệt các đỉnh một cách hệ thống. Những

Hình 1. Đồ thị G.
Thuật toán tìm kiếm theo chiều sâu trên đồ thị G được cho trong hình 1
được minh họa trong hình dưới đây. Các đỉnh đang xét được khoanh ừòn. Các
2
đỉnh đã duyệt xong được khoanh hình ô vuông. Thứ tự duyệt bằng tay ta có thể
tự quy định từ trên xuống dưới, từ trái qua phải hoặc theo sự tăng dần của chỉ
số của đỉnh để tránh nhầm lẫn (bỏ sót hay lặp lại đỉnh ữong quá trình duyệt). Ở
ví dụ này, ta tìm kiếm theo thứ tự tăng dàn chỉ số của các đỉnh. Thuật toán bắt
đầu tìm kiếm từ đỉnh V!, các
2
đỉnh kề với nó là v
2
,v
3
, v
4
và tiếp tục tìm kiếm đến v
2
, đến v
3
và đến v
5
.
Sau khi thăm đỉnh v
7
ta thấy không còn đỉnh nào kề với nó nữa, ta nói
v
7
đã duyệt xong, ta quay lại v
5

end;
end;
Khi đó, tìm kiếm theo chiều rộng trên đồ thị được thực hiện nhờ thuật
toán sau:
BEGIN
(* Initialization *) for V eV do Chuaxet[v] := true; forv eVdo
if Chuaxet[V7 then BFS(v);
END.
2
Ví dụ. Dùng thuật toán BFS duyệt đồ thị sau:
Hình 2. Đồ thị G
Thuật toán tìm kiếm theo chiều rộng được cho trong hình 2 được minh họa
ttong các hình và bảng dưới đây. Tương tự như DFS, ở đây ta cũng quy định
duyệt theo thứ tự từ tăng dần của chỉ số của các cạnh. Thuật toán BFS bắt đàu
tìm kiếm từ đỉnh v
l
. Các đỉnh đang xét được khoanh tròn. Các đỉnh đã duyệt
xong được khoanh hình ô vuông .
2
Hình 2c
Hình 2b
V
o
v„
v
v
a
v
8
Hình