Chương 6

CÁC BÀI TOÁN VỀ ĐƯỜNG ĐI
[email protected]
http://www.math.hcmus.edu.vn/~luyen/cautrucroirac

FB: fb.com/cautrucroirac
CuuDuongThanCong.com

https://fb.com/tailieudientucntt


Nội dung
1. Tìm đường đi ngắn nhất

2. Đồ thị Euler
3. Đồ thị Hamilton

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

2


1. TÌM ĐƯỜNG ĐI NGẮN
NHẤT

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

có trọng số. Ma trận khoảng cách của G là ma
trận D= (dij) xác định như sau:
0
khi i  j

dij   w(v i v j ) khi vi v j  E

khi vi v j  E


Nhận xét. Mọi đồ thị được hoàn toàn xác định bởi
ma trận khoảng cách.

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

5


Ví dụ. Tìm ma trận khoảng
cách của đồ thị sau

CuuDuongThanCong.com

0






https://fb.com/tailieudientucntt


73
49

0
23
10



25
16

0



 
38


9

12 
0 

6



6
10 

5
0 

Đáp án.
5

D

16
12

B

A

6

7

5

15

C
CuuDuongThanCong.com

Đối với các khuyên có trọng lượng không âm thì
cũng có thể bỏ đi mà không làm ảnh hưởng đến kết
quả của bài toán.
Đối với các khuyên có trọng lượng âm thì có thể
đưa đến bài toán tìm đường đi ngắn nhất không có
lời giải.

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

9


Nguyên lý Bellman
Gọi P là đường đi ngắn nhất từ đỉnh u đến đỉnh v; t 
P. Giả sử P=P1P2 với P1 là đường đi con của P từ u
đến t và P2 là đường đi con của P từ t đến v. Khi đó
P1 cũng là đường đi ngắn nhất từ u đến t.
Chứng minh. Giả sử tồn tại P1’ là đường đi ngắn hơn
t
P1 ta có
P1
P2
v

u

P1’




Trước tiên đỉnh có khoảng cách nhỏ nhất đến u0 là u0.



Trong V\{u0} tìm đỉnh có khoảng cách đến u0 nhỏ nhất
(đỉnh này phải là một trong các đỉnh kề với u0) giả sử
đó là u1



Trong V\{u0,u1} tìm đỉnh có khoảng cách đến u0 nhỏ
nhất (đỉnh này phải là một trong các đỉnh kề với u0
hoặc u1) giả sử đó là u2
CuuDuongThanCong.com

https://fb.com/tailieudientucntt

12


Tiếp tục như trên cho đến bao giờ tìm được khoảng
cách từ u0 đến mọi đỉnh.
Nếu G có n đỉnh thì:
0 = d(u0,u0) < d(u0,u1)  d(u0,u2) … d(u0,un-1)

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

7

1
4

3

3

x

u
1

2

t

1
y
CuuDuongThanCong.com

3

3

4
z

w


3

3

4
z

w
5

u
0*

r
s
t
x
y
(,-) (,-) (,-) (,-) (,-)

-

(4,u0) (,-) (,-) (,-) (1,u0)* (,-) (,-)

-

(3,y)* (,-) (,-) (,-) CuuDuongThanCong.com

z

(,-) (,-) (,-) (,-) (,-) (,-) (,-)

-

(4,u0) (,-) (,-) (,-) (1u0)* (,-) (,-)

-

(3,y)* (,-) (,-) (,-) -

-

CuuDuongThanCong.com

(10,r) (6,r)

x

3

4
z

3

t

1

3


Cây đường đi

s
r

1
3

x

1

t
u
2
1
y

CuuDuongThanCong.com

3

z

5

w

https://fb.com/tailieudientucntt


CuuDuongThanCong.com

https://fb.com/tailieudientucntt


CuuDuongThanCong.com

https://fb.com/tailieudientucntt

20


v1

v3

v4

v5

v6

v7

(,-)

(,-)

0*

-

-

(39,v3)*

(78,v2) (56,v3) (69,v3)

-

-

-

-

(78,v2) (55,v4)* (69,v3)

-

-

-

-

(78,v2) -

(67,v6)*


nhất từ đỉnh a đến đỉnh z.

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

23


a

b

c

d

e

f

g

z

0*

(,-)

(,-)


(6,c)

(9,c)

(,-)

(,-)

(,-)

-

-

-

(6,c)*

(9,c)

(,-)

(,-)

(,-)

-

-


-

-

-

(12,e )*

(18,f )

-

-

-

-

-

-

(16,g )*

-

24
CuuDuongThanCong.com


5

g

https://fb.com/tailieudientucntt