1
Chương 2
ĐƯỜNG ĐI VÀ CHU TRÌNH
•
I. ĐƯỜNG ĐI VÀ CHU TRÌNH EULER
•
II. ĐƯỜNG ĐI VÀ CHU TRÌNH HAMILTON
•
III. BÀI TOÁN ĐƯỜNG NGẮN NHẤT
2
I. ĐƯỜNG ĐI VÀ CHU TRÌNH EULER
•
1. nh ngh a.Đị ĩ Đường đi Euler trong G là đường
đi đơn chứa mọi cạnh của G.
•
Chu trình đơn chứa tất cả các cạnh của đồ thị G
được gọi là chu trình Euler.
•
a b a b
•
e
•
c d e

•
c d
Có chu trình Euler Có đường đi Euler
3
I ĐƯỜNG ĐI VÀ CHU TRÌNH EULER
2. Điều kiện cần và đủ để tồn tại chu trình Euler.
•

Định lý 1.
•
Một đa đồ thị liên thông có chu trình Euler
⇔
mọi đỉnh
đều có bậc chẵn.
•
Điều kiện cần. G có CT Euler ∀đỉnh có bậc chẵn.
•
Thật vậy, CT Euler bắt đầu tại a và tiếp tục là {a,b}. Cạnh
{a,b} góp 1 vào deg(a).
•
Mỗi lần khi CT đi qua một đỉnh, nó cộng 2 đơn vị cho bậc
của đỉnh đó. Cuối cùng chu trình kết thúc ở đỉnh a nó cộng
thêm 1 vào deg(a).
•
Vậy mọi đỉnh đều có bậc chẵn.
4
I ĐƯỜNG ĐI VÀ CHU TRÌNH EULER
•
Điều kiện đủ. G -liên thông và mọi đỉnh có bậc chẵn
⇒

Tồn tại chu trình Euler.
•
Thật vậy, xây dựng CT đơn bắt đầu từ x
0
=a tùy ý. Chọn
tùy ý cạnh {x
0

, x
1
} liên thuộc a, tiếp tục xây dựng đ/đi đơn
{x
0
, x
1
}, {x
1
, x
2
}, , {x
n-1
, x
n
} càng dài càng tốt.
•
đường đi sẽ kết thúc vì đồ thị có hữu hạn đỉnh.
•
Nó bắt đầu tại a với cạnh {a,x} và kết thúc tại a với cạnh
{y,a} vì mỗi đỉnh có bậc chẵn.
•
Chu trình nhận được có thể chứa tất cả các cạnh hoặc
có thể không.
5
I ĐƯỜNG ĐI VÀ CHU TRÌNH EULER
•
Ví dụ
•
a b

•
f c d c d
•
G e e H
•
Tất cả các cạnh được sử dụng ⇒ nhận được chu trình
Euler.
•
Ngược lại, gọi H là đồ thị con nhận được từ G bằng
cách xóa các cạnh đã dùng và các đỉnh không liên thuộc
với các cạnh còn lại. H có thể là không liên thông
6
I ĐƯỜNG ĐI VÀ CHU TRÌNH EULER
•
Vì G là liên thông ⇒∃ w∈H và w ∈ CT đã bị xóa.
•
Mỗi đỉnh của H có bậc chẵn. Bắt đầu từ w ta xây dựng
đường đi đơn trong H như đã làm đối với G. Đường này
phải kết thúc tại w.
•
Tạo một CT trong G bằng cách ghép CT trong H và CT
ban đầu trong G.
•
Tiếp tục cho tới khi tất cả các cạnh được sử dụng. Nhận
được CT Euler.
•
Vậy nếu các đỉnh của một đa đồ thị liên thông có bậc
chẵn thi đồ thị có CT Euler. đpcm
7
I ĐƯỜNG ĐI VÀ CHU TRÌNH EULER

•
Định lý 2. G liên thông có đường đi Euler nhưng không có
CT Euler
⇔
G có đúng 2 đỉnh bậc lẻ .
•
Điều kiện cần. G có đường đi Euler từ a tới b, nhưng
không có CT Euler.
•
Cạnh đầu tiên của đ/đi góp 1 vào deg(a). Mỗi lần đ/đi qua
đỉnh a nó thêm 2 đơn vị cho deg(a). Do vậy, a có bậc lẻ.
•
Cạnh cuối cùng góp 1 cho deg(b) và mỗi lần đi qua b nó
cũng thêm 2 cho deg(b). Vậy b có bậc lẻ
•
Các đỉnh trung gian đều có bậc chẵn, do mỗi lần đường đi
đến rồi lại rời nó nên thêm 2 đơn vị cho bậc của các đỉnh
này.
8
I ĐƯỜNG ĐI VÀ CHU TRÌNH EULER
•
Điều kiện đủ
•
G có đúng hai đỉnh bậc lẻ, chẳng hạn a và b. Nối
a với b.
•
Xét đồ thị G*= G + {(a,b)}. ⇒ tất cả các đỉnh của
G* đều có bậc chẵn.
•
Theo định lý 1, G* có CT Euler.

•
Xóa cạnh mới vẽ thêm vào ta sẽ nhận được
đường đi Euler trong G.
9
I ĐƯỜNG ĐI VÀ CHU TRÌNH EULER
Ví dụ. Đồ thị nào có đường đi Euler?
a b a g f e a b
f g
c
d c b c d e d
G1 G2 G3
.
10
II ĐƯỜNG ĐI VÀ CHU TRINH HAMILTON
•
ĐỊNH NGHĨA. Đường đi x
0
, x
1
, ,x
n-1
,x
n
trong đồ thị
G=(V,E), V={x
0
, x
1
, ,x
n-1

,x
n
}, là đường đi Hamilton
nếu x
i
≠x
j
với 0 ≤ i <j ≤ n. Chu trinh x
0
,x
1
, ,x
n-1
, x
n
,x
0

(n>1) trong đồ thị G=(V,E) được gọi là chu trinh
Hamilton nếu x
0
, x
1
, ,x
n-1
,x
n
là đường đi Hamilton.
a b a b a b g
e c d c d c e f

d
G1 có chu trình H, G2 không có chu trình, nhưng có đường đi H, G3
không có đường đi và chu trình H
11
II.ĐƯỜNG ĐI VÀ CHU TRÌNH HAMINTON
•
Định lý. Gỉa sử G là một đơn đồ thị liên thông
với n đỉnh trong đó n≥3, khi đó G có CTHamilton
nếu bậc của mỗi đỉnh ít nhất bằng n/2 (điều kiện
đủ).
•
Chứng minh. (Xem trong giáo trình)
•
n= 5 n=6
12
III BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT
•
Đồ thị có trọng số.
•
Mỗi cạnh được gán một số (nguyên hoặc thực)
gọi là trọng số ứng với cạnh đó.
•
Trọng số có thể: khoảng cách, thời gian, tiền vé,
thời gian trả lời qua mạng máy tính, cước phí
truyền thông
•
Trọng số đôi khi gọi là độ dài của một cạnh.
•
Xác định đường đi ngắn nhất giữa hai đỉnh?
13

III BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT
•
1.Thuật toán tìm đường đi ngắn nhất.
•
Đường đi ngắn nhất giữa 2 đỉnh của một
đồ thị có thể tìm được bằng kiểm tra trực
tiếp. Dùng được khi có ít cạnh.
•
Có một số thuật toán khác:
•
Thuật toán do E. Dijkstra (Hà-lan), 1959.
•
Ví dụ minh hoạ thuật toán Dijkstra: Tìm
đường đi ngắn nhất giữa 2 đỉnh a và z?
14
B c 0ướ


b ∞
d ∞
c ∞ e ∞
z ∞
a 0
3
5
1 8
2
10
4
6

2
z ∞
4
5
2
10
8
6
2a 0
c 2
b 4
d ∞
e ∞
B c 1ướ
3
1
15



a 0
c 2(a)
a 0
e 12(a,c)
z ∞
d 10(a,c)b 3(a,c)
4
b 3 (a,c)
c 2 (a) e 12 (a,c)
d 8 (a,c,b)

z ∞
2
4
2
5
6
3
6
2
5
1
8
10
10
1
2
8
3
B c 3ướ
B c 2ướ
16
e 10 (a,c,b,d)
d 8 (a,c,b)
b 3 (a,c)
a 0
c 2(a)
10
6
2 8
5

1
2
4
10
2
1
4
2
3
6
5
3
z 14(a,c,b,d)
8
a 0
c 2(a)
b 3 (a,c) d 8 (a,c,b)
e 10 (a,c,b,d)
z 13(a,c,b,d,e)
B c 4ướ
B c 5ướ
17
B c 6ướ
4
3
6
2
10
8
5

1
2
Đường đi ngắn nhất từ a đến z là
a,c,b,d,e,z với độ dài 13
e 10(a,c,b,d)
d 8(a,c,b)
c 2(a)
b 3(a,c)
a 0
z 13(a,c,b,d,e)
18
III BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT
•
THUẬT TOÁN DIJKSTRA (Thuật toán gán nhãn).
•
S ={ các đỉnh đã gán nhãn}.
•
Bước 0: S
0
=
∅
: Gán nhãn: L
0
(a)=0 và L
0
(v)=
∞
,
∀
v≠ a. Các nhãn = độ dài của ĐĐNN từ đỉnh a

tới các đỉnh này, đường đi này chỉ chứa đỉnh a.
•
Bước 1: a -đỉnh có nhãn nhỏ nhất , S
1
=S
0
+{a}.
Sửa nhãn của các đỉnh v
∉
S
1
bằng ĐĐNN từ a
đến v, ĐĐ có a là đỉnh trong.
•
Cuối bước k-1 ta có S
k-1
và các đỉnh v
∉
S
k-1
đã
được gán: nhãn (v) = độ dài ĐĐNN từ a tới v và
ĐĐ này có các đỉnh trong thuộc S
k-1

19
III BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT
•
Bước k: Gọi u
∉

S
k-1
có nhãn nhỏ nhất.
•
S
k
=S
k-1
+{u}.
•
Sửa nhãn của ∀v ∉ S
k
với L
k
(v) = độ dài của
ĐĐNN từ a tới v và có các đỉnh trong
∈
S
k
.
•
Quá trình lặp kết thúc khi đỉnh z ∈S
20
III BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT
•
Chú ý: ĐĐ từ a tới v với các đỉnh trong thuộc S
k

gồm hai loại: loại 1 là ĐĐ từ a tới v chỉ chứa các
đỉnh trong thuộc S

k-1
, loại 2 là ĐĐ từ a tới u ở
bước k-1 tiếp theo là cạnh (u,v). TL ta có
•
L
k
(a,v) = min { L
k-1
(a,v), L
k-1
(a,u)+w(u,v)}.
S
k-1
S
k
u
a
v
V
21
•
Procedure Dijkstra (G: đơn, liên thông có trọng
số dương)
•
for i:=1 to n do L(vi):= ∞
•
L(a):=0; S:=∅
•
While (z ∉S )
•

{
•
u:= đỉnh không thuộc S có nhãn L(u) nhỏ nhất
•
S := S∪{u}
•
for tất cả các đỉnh v ∉ S
•
If L(u) + w(u,v) < L(v) then L(v) := L(u)
+w(u,v)
•
} {L(z) =độ dài đường đi ngắn nhất từ a tới z}
22
III BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT
•
Định lý 1. Thuật toán Dijkstra tìm được
đường đi ngắn nhất giữa hai đỉnh trong đồ
thị đơn vô hướng liên thông có trọng số.
•
Định lý 2. Thuật toán Dijkstra dùng O(n
2
)
phép toán (cộng và so sánh) để tìm độ dài
của đường đi ngắn nhất giữa hai đỉnh
trong đồ thị đơn vô hướng liên thông có
trọng số.
23
HẾT CHƯƠNG 3