ờ ti thc tp chuyờn ngnh Nhúm thc hin: Lp 46B2_CNTT
Li M u
Lý thuyt th l mt lnh vc ó cú t lõu v cú nhiu ng dng hin
i. Nhng t tng c bn ca lý thuyt th c xut vo nhng nm
u ca th k 18 bi nh toỏn hc li lc ngi Thy S Lenhard Euler.
th c s dng gii cỏc bi toỏn trong nhiu lnh lc khỏc nhau . Chng
hn , th cú th s xỏc nh mch vũng trong vn gii tớch mch in.
th cú trng s trờn cỏc cnh cú th s dng gii cỏc bi toỏn nh: Tỡm
ng i ngn nht gia hai thnh ph trong mnh giao thụng. Chỳng ta cng
cũn s dng th gii cỏc bi toỏn v lp lch , thi khoa biu
Đặc biệt trong khoảng vài mơi năm trở lại đây, cùng với sự ra đời của
máy tính điện tử và sự phát triển nhanh chóng của tin học, lí thuyến đồ thị càng
đợc quan tâm đến nhiều hơn. Các thuật toán trên đồ thị đã có nhiều ứng dụng
trong nhiều lĩnh vực khác nhau nh: Mạng máy tính, Lí thuyết mã, Tối u hoá .
Trong phạm vi ti này do thi gian cú hn chỳng em chỉ nghiên cứu về
một số bài toán v ng i trong lí thuyết đồ thị nh: Bài toán tìm chu trình
Euler, Bài toán tìm đờng đi ngắn nhất , Thuật toán Dijkstral. Chỳng em rt
mong c s úng gúp ý kin ca thy cụ v cỏc bn.
Chúng em đặc biệt bày tỏ lòng biết ơn chân thành tới thầy giáo, Tin s:
Nguyn Trung Hũa, ngời thầy đã tạo mọi điều kiện và luôn giúp đỡ, hớng dẫn
chúng em tận tình để chúng em hoàn thành tốt đề tài này.
Nhúm sinh viờn thc hin:
Lờ Th Thu Hin
Nguyn Th Tho
Trnh Th Thy
Nguyn Trng Ti
GVHD: TS. Nguyễn Trung Hoà
1
Hỡnh 1.2: th cú hng
Đê tài thực tập chuyên ngành Nhóm thực hiện: Lớp 46B2_CNTT
Phần I:

Ví dụ:
Xếp lịch thi đấu là một đồ thị vô hướng với mỗi đội là đỉnh, hai đội thi đấu với
nhau là cạnh. Mạng giao thông là một đa đồ thị có hướng với nút giao thông
là đỉnh, đường đi giữa hai nút là cung. Tương tự việc thiết kế mạng máy tính,
mạng viễn thông có thể đưa về bài toán đồ thị
II. Các khái niệm
1 . Các khái niệm cơ bản
- Khuyên: cạnh (cung) e gọi là khuyên nếu e có dạng (v,v).
- Cạnh (cung) lặp: là hai cạnh (cung) cùng tương ứng với một cặp đỉnh.
- Đỉnh kề: nếu (u,v) là cạnh (hoặc cung) của đồ thị thì v gọi là kề của u.
Trong đồ thị vô hướng nếu v kề u thì u cũng kề v, nhưng trong đồ thị có
hướng thì không chắc.
- Cạnh liên thuộc: Trong đồ thị vô hướng, cạnh e=(u,v) gọi là cạnh liên
thuộc với đỉnh u và liên thuộc với đỉnh v.
- Bậc của đỉnh: Trong đồ thị vô hướng, số cạnh liên thuộc với v gọi là bậc
của đỉnh v, kí hiệu là deg(v).
Ví dụ: Xét đồ thị hình 1,deg(a)=1, deg(b)=deg(c)=4, deg(d)=1,
deg(e)=deg(f)=3, deg(g)=0
- Đỉnh cô lập, đỉnh treo: Trong đồ thị vô hướng, đỉnh bậc 0 gọi là đỉnh cô lập
, đỉnh bậc 1 gọi là đỉnh treo.
Ví dụ: Xét đồ thị hình 1.1.
Ta có a là đỉnh treo, g là đỉnh cô lập
GVHD: TS. NguyÔn Trung Hoµ
3
Hình 1.1: Đồ thị vô hướng
a

e

c

(B)=3, deg
-
(C)=1, deg
-
(D)=2, deg
-
(E)=2
deg
+
(A)=3, deg
+
(B)=2, deg
+
(C)=2, deg
+
(D)=2, deg
+
(E)=1
- Định lý 1 : Trong đồ thị vô hướng thì tổng bậc của tất cả các đỉnh bằng 2
lần số cạnh.
∑
∈Vv
v)deg(
= 2m (m là số cạnh)
Chứng minh:
Mỗi cạnh e=(u,v) được tính một lần trong deg(u) và một lần trong
deg(v) nên trong tổng bậc của các đỉnh, mỗi cạnh được tính hai lần, mà
có m cạnh nên suy ra tổng bậc bằng 2m.
- Hệ quả : Trong đồ thị vô hướng, số đỉnh có bậc là số lẻ là một số chẵn
Chứng minh:

∈
O, deg(v) lẻ mà tổng
∑
∈Ov
v)deg(
chẵn, nên tổng này phải gồm
một số chẵn các số hạng
⇒
số đỉnh có bậc là số lẻ là một số chẵn (đpcm).
- Định lý 2 : Trong đồ thị có hướng, tổng bán bậc ra của tất cả các đỉnh bằng
tổng bán bậc vào của tất cả các đỉnh và bằng số cạnh của đồ thị
∑
∈
+
Vv
v)(deg
=
∑
∈
−
Vv
v)(deg
= m (m là số cạnh)
Chứng minh: Hiển nhiên vì mỗi cung đều ra ở một đỉnh và vào ở một đỉnh
khác.
GVHD: TS. NguyÔn Trung Hoµ
4
1, nếu i là đỉnh đầu của cung e
j
-1, nếu i là đỉnh cuối của cung e

1 0 1 1 0 1 0
2 1 0 1 0 1 0
3 1 1 0 1 0 0
4 0 0 1 0 1 1
5 1 1 0 1 0 1
6 0 0 0 1 1 0
1 2 3 4 5 6
1 0 1 1 0 0 0
2 0 0 0 0 0 0
3 0 1 0 1 0 0
4 0 0 0 0 0 0
5 0 0 0 1 0 1
6 0 0 0 0 1 0
5
1, nếu i là đỉnh đầu của cung e
j
-1, nếu i là đỉnh cuối của cung e
j
0, nếu i không là đầu mút của cung
e
j
(1,2) (1,3) (2,3) (2,4) (3,5) (4,5) (4,6) (5,2) (5,6)
1 1 1 0 0 0 0 0 0 0
2 -1 0 1 1 0 0 0 -1 0
3 0 -1 -1 0 1 0 0 0 0
A= 4 0 0 0 -1 0 1 1 0 0
5 0 0 0 0 -1 0 0 1 1
6 0 0 0 0 0 0 -1 0 -1
Đê tài thực tập chuyên ngành Nhóm thực hiện: Lớp 46B2_CNTT
- Tổng các phần từ trên dòng i (cột j) bằng bậc của đỉnh i (đỉnh j).

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
đơn vị bộ nhớ để lưu trữ ma trận kề của nó.
b. Ma trận liên thuộc đỉnh-cạnh
Xét G=(V, E) là đơn đồ thị có hướng. Ma trận liên thuộc đỉnh-cạnh có dạng:
Ví dụ:
GVHD: TS. NguyÔn Trung Hoµ
6
1, nếu i là đỉnh đầu của cung e
j
-1, nếu i là đỉnh cuối của cung e
j
0, nếu i không là đầu mút của cung
e
j
a
ij
=
1
2 4
6

2 -1 0 1 1 0 0 0 -1 0
3 0 -1 -1 0 1 0 0 0 0
A= 4 0 0 0 -1 0 1 1 0 0
5 0 0 0 0 -1 0 0 1 1
6 0 0 0 0 0 0 -1 0 -1
Đê tài thực tập chuyên ngành Nhóm thực hiện: Lớp 46B2_CNTT
1 3 1 3
1 5 3 2
2 3 3 4
2 5 5 4
3 4 5 6
4 5 6 5
4 6
5 6
D/s cạnh của G D/s cung của G1
d. Danh sách kề
Với mỗi đỉnh v, ta lưu trữ danh sách các đỉnh kề với v: Ke(v)={u
∈
V: (v,u)
∈
E}
Ví dụ:
- Danh sách kề của G
Đỉnh đầu
- Danh sách kề của hình G1
Đỉnh đầu
GVHD: TS. NguyÔn Trung Hoµ
8
ờ ti thc tp chuyờn ngnh Nhúm thc hin: Lp 46B2_CNTT
Trong cỏch biu din ny chỳng ta cn phi s dng c m+n n v b nh.

v
i
e
i
v
i1
e
i1
v
i2
e
i2
... e
j
v
j
Trong đó các cạnh, các đỉnh trong đờng đi có thể lặp lại
2 Chu trình
Xét một đờng đi từ v
i
- v
j
. Nếu v
i
v
j
thì đờng đi này đợc gọi là một chu trình.
Nh vậy chu trình là một đờng đi có đỉnh xuất phát và đỉnh kết thúc trùng nhau.
Chú ý rằng đờng đi trong đồ thị có hớng không đợc đi ngợc chiều mũi tên
- Đờng đi (chu trình) đợc gọi là đơn nếu nó đi qua mỗi cạnh không quá một lần.

1
), (x
1
,x
2
), ,(x
n-1
,x
n
).
Đỉnh u đợc gọi là đỉnh đầu, còn đỉnh v đợc gọi là đỉnh cuối của đờng đi.
Đờng đi có đỉnh đầu trùng với đỉnh cuối (tức là u trùng với v) đợc gọi là chu
trình. Đờng đi hay chu trình đợc gọi là đơn nếu không có cạnh nào bị lặp lại.
Hỡnh2.3
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 trờng hợp đồ thị vô hớng, chỉ khác là ta có chú ý đến
hớng trên các cung.
4. Đờng đi và chu trình của đồ thị có hớng:
Đờng đi có độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dơng,
trên đồ thị có hớng là dãy:
x
0
, x
1
, , x
n-1
, x
n.
Trong đó:
u=x

GVHD: TS. Nguyễn Trung Hoà
EE
10
A
B
C
D
E
ờ ti thc tp chuyờn ngnh Nhúm thc hin: Lp 46B2_CNTT
Ví dụ nh hình 2.3 là một đồ thị liên thông vì luôn có đờng đi nối hai đỉnh bất kỳ
của đồ thị, còn đồ thị nh hình 2 là không liên thông vì không có đờng đi từ A tới
D hoặc từ D tới F v.v..
Xét 2 đồ thị liên thông
G
1
= <V
1
, E
1
> và G
2
= <V
2
, E
2
>
Trong đó: V
1
V
2

1
= {AB, AC, CB}
G
2
= <V
2
, E
2
> với V
2
= {D, E} và E
2
= {DE}
G
3
= <V
3
, E
3
> với V
3
= {F} và U
3
=
Cho đồ thị có hớng G = <V,E>
- G đợc gọi là đồ thị liên thông yếu nếu đồ thị vô hớng tơng ứng với nó là liên
thông
- G là liên thông một chiều nếu với hai đỉnh u,v khác nhau bất kỳ của G luôn có
đờng đi u - v hoặc đờng đi v - u.
- G là liên thông mạnh (liên thông 2 chiều) nếu hai đỉnh u,v khác nhau bất kỳ

Trờn hình 2.5 đồ thị H
1
là liên thông mạnh, giả sử cặp đỉnh (A,C) ta có chiều
đi từ C tới A, và đồng thời cũng có chiều đi từ A tới C, và bất kỳ các cặp đỉnh
khác cũng tơng tự nh vậy. H
2
là liên thông một chiều vì xét cặp đỉnh (A,D) có
chiều đi từ D tới A nhng không có chiều đi từ A tới D. H
3
là liên thông yếu vì tồn
tại cặp đỉnh (B,C) không có chiều đi B - C cũng không có chiều đi C - B, nhng đồ
thị vô hớng tơng ứng là liên thông
6. ng i Euler v chu trinh Euler
ng i Euler: Mt ng i trong th c gi l ng i euler nu
nú i qua tt c cỏc cnh hoc cung ca th vi mi cnh hoc cung i qua
ỳng mt ln.
Chu trỡnh Euler: Mt chu trỡnh c gi l chu trỡnh Euler nu nú l mt
ng i Euler
ng i Euler l mt ng i n cha tt c cỏc cnh hoc cung ca
th. Cũn chu trỡnh Euler l mt chu trinh n cha tt c cỏc cnh hoc cung
ca th.
Mt th cú ng i Euler thỡ c gi l th na Euler.Cũn th cú
chu trỡnh Euler thỡ gi l th Euler.

Hỡnh 2.6 Hinh 2.7
- Chn nh khi u l A ,trờn hỡnh 2.6 cú chu trỡnh Euler l:
A->B ->C->A->F->C->D->E->A
GVHD: TS. Nguyễn Trung Hoà
B
A

Trong lý thuyết đồ thị, bài toán đường đi ngắn nhất nguồn đơn là bài
toán tìm một đường đi giữa hai đỉnh sao cho tổng các trọng số của các cạnh
tạo nên đường đi đó là nhỏ nhất. Định nghĩa một cách hình thức, cho trước
một đồ thị có trọng số (nghĩa là một tập đỉnh V, một tập cạnh E, và một hàm
trong số có giá trị thực f : E → R), cho trước một đỉnh v thuộc V, tìm một
đường đi P từ v tới mỗi đỉnh v' thuộc V sao cho:
là nhỏ nhất trong tất cả các đường nối từ v tới v' . Bài toán đường đi ngắn nhất
giữa mọi cặp đỉnh là một bài toán tương tự, trong đó ta phải tìm các đường đi
ngắn nhất cho mọi cặp đỉnh v và v' .
Thuật toán Dijkstra, mang tên của nhà khoa học máy tính người Hà Lan
Edsger Dijkstra, là một thuật toán giải quyết bài toán đường đi ngắn nhất
nguồn đơn trong một đồ thị có hướng không có cạnh mang trọng số âm.
Bài toán:
Cho một đồ thị có hướng G=(V,E), một hàm trọng số w: E → [0, ∞) và
một đỉnh nguồn s. Cần tính toán được đường đi ngắn nhất từ đỉnh nguồn s đến
mỗi đỉnh của đồ thị.
Ví dụ: Chúng ta dùng các đỉnh của đồ thị để mô hình các thành phố và
các cạnh để mô hình các đường nối giữa chúng. Khi đó trọng số các cạnh có
thể xem như độ dài của các con đường (và do đó là không âm). Chúng ta cần
GVHD: TS. NguyÔn Trung Hoµ
13
ờ ti thc tp chuyờn ngnh Nhúm thc hin: Lp 46B2_CNTT
vn chuyn t thnh ph s n thnh ph t. Thut toỏn Dijkstra s giỳp ch ra
ng i ngn nht chỳng ta cú th i.
Trng s khụng õm ca cỏc cnh ca th mang tớnh tng quỏt hn
khong cỏch hỡnh hc gia hai nh u mỳt ca chỳng.
Vớ d: Vi 3 nh A, B, C ng i A-B-C cú th ngn hn so vi
ng i trc tip A-C.
Thut toỏn Dijkstra cú th mụ t nh sau:
- Ta qun lý mt tp hp ng S. Ban u S={s}.