MỤC LỤC
CHƯƠNG 1. ĐẠI CƯƠNG VỀ ĐỒ THỊ 4
CHƯƠNG 2. CHU TRÌNH EULER VÀ BÀI TOÁN NGƯỜI ĐƯA THƯ 8
2.1. Định nghĩa 8
2.2. Điều kiện cần và đủ 8
2.2.1. Định lý 1 (Định lý Euler) 8
2.3. Các thuật toán tìm chu trình Euler 10
2.4. Thiết kế cấu trúc dữ liệu và giải thuật tìm đường đi, chu trình Euler 12
2.5. Bài toán người đưa thư 14
3.1. Tìm đường đi, chu trình Euler 18
3.2. Giải bài toán người đưa thư 21
Toán ứng dụng Chu trình Euler và bài toán người đưa thư
GIỚI THIỆU
Lý thuyết đồ thị là ngành khoa học được phát triển từ lâu nhưng lại có
nhiều ứng dụng hiện đại. Những ý tưởng cơ bản của nó được đưa ra từ thế
kỷ XVIII bởi nhà toán học Thụy sĩ tên là Leonhard Euler.
Lý thuyết đồ thị được dùng để giải các bài toán trong nhiều lĩnh vực
khác nhau. 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…
Ngày nay Lý thuyết đồ thị đã phát triển thành một ngành Toán học
ứng dụng có vị trí đặc biệt quan trọng về mặt lý thuyết cũng như ứng dụng.
Trong nội dung cuốn tiểu luận này nhóm chúng tôi xin trình bày về
“Chu trình Euler và bài toán người đưa thư”.
Đồng Hới, tháng 05 năm 2012
Tiểu luận nhóm 1 Trang
Toán ứng dụng Chu trình Euler và bài toán người đưa thư
- Đề tài: Chu trình Euler và bài toán người đưa thư

- V ≠ Ø là tập hợp hữu hạn gồm các đỉnh của đồ thị.
- E là tập hợ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.
Như vậy, theo định nghĩa trên, trong một đơn đồ thị không thể có các cặp
cạnh nối cùng một cặp đỉnh (do E là tập hợp nên không thể có 2 cặp trùng nhau),
các cạnh đều không phân biệt thứ tự nên cạnh [u,v] và cạnh [v,u] đều được coi là
một cạnh duy nhất, điều này phù hợp với việc biểu diễn các con đường 2 chiều,
và hiển nhiên là không có cặp [u,u] nào đó trong E.
Ví dụ 1.1.

Định nghĩa 1.2.2. Đa đồ thị vô hướng là một bộ G=<V,E>, trong đó
- V ≠ Ø là tập hợp hữu hạn gồm các đỉnh của đồ thị.
- E là một họ các cặp không có thứ tự của V gọi là các cạnh.
Định nghĩa 1.2.3. Đơn đồ thị có hướng là một bộ G=<V,E>, trong đó:
- V ≠ Ø là tập hợp hữu hạn gồm các đỉnh của đồ thị.
- E là tập hợ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.
Ví dụ:
Tiểu luận nhóm 1 Trang
a. Đơn đồ thị
vô hướng
b. Không phải đơn
đồ thị vô hướng do
có các cặp cạnh nối
cùng một cặp đỉnh
c. Không phải đơn đồ
thị vô hướng do có

Định nghĩa 1.4.1. Cho đồ thị *G = <V,E> (* ký hiệu cho dùng chung cả đồ thị
vô hướng và có hướng). Đường đi độ dài n từ đỉnh u đến đỉnh v (n là số nguyên
dương) là dãy:
Tiểu luận nhóm 1 Trang
Toán ứng dụng Chu trình Euler và bài toán người đưa thư

trong đó
* Ta sẽ dùng thuật ngữ đồ thị để chỉ chung cho cả đồ thị vô hướng và đồ thị có
hướng Đường đi nói trên còn có thể được biểu diễn bằng dãy các cạnh/cung:

Đỉnh u gọi là đỉnh đầu của đường đi, đỉnh v gọi là đỉnh cuối của đường đi.
Đường đi có đỉnh đầu và đỉnh cuối trùng nhau (u=v) gọi là chu trình.
Ví dụ: Cho đồ thị vô hướng sau:

Một số đường đi từ đỉnh 2 đến đỉnh 7:
- Đường đi d1: 2 3 4 7 (đường đi độ dài 3)
- Đường đi d2: 2 3 4 1 3 6 7 (đường đi độ dài 6)
Một số chu trình trên đồ thị trên:
- Chu trình C1: 1 2 3 1 (chu trình có độ dài 3)
- Chu trình C2: 1 2 3 7 6 3 4 1 (chu trình có độ dài 7)
Định nghĩa 1.4.2. Đồ 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ó.
Ví dụ: Xét các đồ thị vô hướng sau:Trong 2 đồ thị trên thì G1là đồ thị liên thông, còn G2 không phải là đồ thị liên
thông vì giữa hai đỉnh 1 và 2 không tồn tại một đường đi nào.
Định nghĩa 1.4.3 Cho đồ thị G = (V,E). Đồ thị H = <W,F> được gọi là đồ thị
con của G nếu và chỉ nếu W € V và F € E.
Trong trường hợp một đồ thị vô hướng G không liên thông, nó sẽ được phân


Tiểu luận nhóm 1 Trang
Toán ứng dụng Chu trình Euler và bài toán người đưa thư
CHƯƠNG 2.
CHU TRÌNH EULER VÀ BÀI TOÁN NGƯỜI ĐƯA THƯ
2.1. Định nghĩa
Cho đồ thị G=(V,E), V là tập hợp các đỉnh, E là tập hợp các cạnh
Chu trình Euler là chu trình qua mọi cạnh và mọi đỉnh đồ thị, mỗi cạnh
không đi quá 1 lần.
Đường đi Euler là đường đi qua mọi cạnh và mọi đỉnh đồ thị, mỗi cạnh
không đi quá 1 lần.
Cho đồ thị có hướng G=(V,E).
Chu trình có hướng Euler là chu trình có hướng qua mọi cung và mọi đỉnh
đồ thị, mỗi cung không đi quá 1 lần.
Đường đi có hướng Euler là đường đi có hướng qua mọi cung và mọi đỉnh
đồ thị, mỗi cung không đi quá 1 lần.
Đồ thị chứa chu trình Euler gọi là Đồ thị Euler.
2.2. Điều kiện cần và đủ
2.2.1. Định lý 1 (Định lý Euler)
Đồ thị G có chu trình Euler khi và chỉ khi G liên thông và mọi đỉnh có bậc
chẵn khác 0.
Chứng minh
(i) (⇒): Giả sử G có chu trình Euler và v là đỉnh bất kỳ của G. Khi đó chu
trình Euler đến v theo cạnh e thì ra khỏi v bằng cạnh e’ ≠ e. Do đó bậc của v phải
là số chẵn. G hiển nhiên là liên thông.
(ii) (⇐): Giả sử G liên thông và mọi đỉnh có bậc chẵn khác 0. Ta chứng
minh G có chu trình Euler quy nạp theo số cạnh m của G.
• m = 1: Vì G liên thông và mọi đỉnh bậc chẵn nên G chỉ có 1 đỉnh và 1
khuyên. Khuyên đó cũng tạo thành chu trình Euler.
• Giả sử G có m cạnh, số đỉnh n > 0 và mọi đồ thị liên thông có số cạnh nhỏ

. Ta xây dựng chu trình Euler C của G như sau. Xuất phát từ đỉnh a đi theo chu
trình C
1
quay về a, sau đó đi theo cạnh x = (a,b) đến đỉnh b, từ b đi theo chu trình
C
2
quay về b, sau đó đi theo cạnh z = (b,c) và y = (c,a) quay về a.
2.2.2. Định lý 2
Cho đồ thị G có k đỉnh bậc lẻ. Khi đó số đường đi tối thiểu phủ G là k/2.
Chứng minh.
Ta đã biết số đỉnh bậc lẻ là chẵn, k=2n. Chứng minh quy nạp theo n.
(i) n=1: Nối 2 đỉnh bậc lẻ với nhau bằng cạnh z ta thu được đồ thị G’
thoả định lý Euler. Như vậy G’ có chu trình Euler C’. Bỏ cạnh z trên C’ ta thu
được đường đi Euler phủ G.
(ii) Giả sử G có số đỉnh bậc lẻ là 2n và định lý đúng với k<2n. Nối 2
đỉnh bậc lẻ a,b nào đó với nhau bằng cạnh z ta thu được đồ thị G’ có 2n-2 đỉnh
bậc lẻ. Theo giả thiết quy nạp G’ có n-1 đường đi phủ G’. Gọi P là đường đi qua
cạnh z. Hiển nhiên a, b không phải đỉnh đầu hoặc cuối của P, vì vậy nếu bỏ cạnh
z ta thu được 2 đường đi P
1
và P
2
cùng với n-2 đường đi còn lại phủ đồ thị G.
(đpcm)
Bây giờ xét đồ thị có hướng G = (V, A). Ký hiệu
R = {u ∈ V : d
I
(v) = d
O
(v)}

( )
∑
∈
−
Tv
IO
vdvd )()(
Ta ký hiệu
k =
( )
∑
∈
−
Sv
OI
vdvd )()(
=
( )
∑
∈
−
Tv
IO
vdvd )()(
2.2.3. Định lý 3
Tiểu luận nhóm 1 Trang
Toán ứng dụng Chu trình Euler và bài toán người đưa thư
(i) Đồ thị có hướng G có chu trình có hướng Euler khi và chỉ khi G liên
thông yếu và mọi đỉnh có nửa bậc vào bằng nửa bậc ra, tức S = ∅ và T = ∅
(ii) Nếu S ≠ ∅, thì số đường đi có hướng tối thiểu phủ G là k. Các đường

Nếu H và C có đỉnh chung. Chọn v là đỉnh chung của H và C. Đặt k :=
k+1. Quay lại bước (2).
Ví dụ
Cho G là đồ thị Thanh mã tấu Mohammed.
Tiểu luận nhóm 1 Trang 10
e
f
k
h
i
j
g
c
d
b
a
A
B
C
D
Toán ứng dụng Chu trình Euler và bài toán người đưa thưTa áp dụng thuật toán 1 để tìm chu trình Euler.
(1) Đặt H := G, k := 1, C := ∅, v := f.
(2) Ta xây dựng chu trình C
1
trong H:
C
1

Tiểu luận nhóm 1 Trang 11
e
f
h
i
j
g
d
b
a
e
f
k
h
i
j
g
c
d
b
a
Toán ứng dụng Chu trình Euler và bài toán người đưa thư
+ Đầu vào. Đồ thị G ≠ ∅, không có đỉnh cô lập.
+ Đầu ra . Chu trình Euler C của G, hoặc kết luận G không có chu trình
Euler.
+ Phương pháp.
(1) Chọn đỉnh xuất phát bất kỳ v
0
. Đặt v
1

) bất kỳ không phải là cầu trong H. Thêm vào
đường đi C đỉnh v
2
. Sang bước (4).
(4) Xoá cạnh vừa đi qua, và xoá đỉnh cô lập:
Loại khỏi H cạnh (v
1
, v
2
). Nếu H có đỉnh cô lập, thì loại chúng khỏi H.
Đặt v
1
:= v
2
. Sang bước (2).
Ví dụ
Cho G là đồ thị hình sau
Đồ thị liên thông và có các đỉnh bậc chẵn. Ta có chu trình Euler sau
(v
6
, v
4
, v
7
, v
5
, v
1
, v
3

v
7
v
5
v
4
v
2
v
1
Toán ứng dụng Chu trình Euler và bài toán người đưa thư
- Sử dụng một ngăn xếp CE[max] để lưu chu trình Euler tìm được.
Giải thuật :
Bước 1 : Kiểm tra đồ thị liên thông hay không
Hàm int lienthong() ;
Bước 2 : Kiểm tra dồ thị là đồ thị Euler hay không phải là đồ thị Euler (dựa
vào bậc của mỗi đỉnh).
Hàm int kiemtraEuler() ;
Bước 3 : Nếu đồ thị liên thông và không Euler thì ta sử dụng định lý
Goodman để chuyển đồ thị thành Euler.
Ta sử dụng các hàm sau đây :
void timdinhle() ; //Tìm các đỉnh lẻ của đồ thị ban đầu
void phanhoach() ; // Dùng để phân hoạch các đỉnh lẻ thành các cặp.
void Hoanvi ;//sinh ra các hoán vị phân hoạch và chọn phân hoạch tối
ưu.
void Themcanh() ; // Thêm cạnh vào đồ thị ban đầu để trở thành đồ thị
Euler.
Int duongdi(int s, int d) ; // tìm đường đi ngắn nhất giữa đỉnh s và t
Bước 4 : Từ đồ thị Euler ta đi tìm chu trình Euler
void Euler(dothi G) ; // tìm chu trình Euler

chua rong.
End.
2.5. Bài toán người đưa thư
2.5.1. Phát biểu bài toán
Bài toán người đưa thư Trung Hoa (Chinese postman problem) phát biểu rằng:
Một người đưa thư xuất phát từ bưu điện phải đến một số con đường để
phát thư rồi quay trở về điểm xuất phát, hỏi người đó phải đi như thế nào để số
đường đi là ít nhất.
Trong phần đồ thị, bài toán người đưa thư Trung Hoa tương đương với
bài toán tìm chu trình ngắn nhất đi qua tất cả các cạnh của một đồ thị cho trước.
Tên gọi "bài toán người đưa thư Trung Hoa" được Alan Goldman của cục tiêu
chuẩn quốc gia Hoa Kỳ (U.S. National Bureau of Standards) đặt cho, vì nó được
nhà toán học Trung Hoa Mei-Ku Guan nêu ra đầu tiên vào năm 1962.
Bài toán giải bằng phương pháp đồ thị. Dựng một đồ thị có các cạnh
tương ứng với các con đường mà người đưa thư phải đi qua. Một chu trình đi qua
tất cả các cạnh gọi là một hành trình. Đỉnh xuất phát của chu trình này tương ứng
với vị trí của bưu điện. Nếu đồ thị là đồ thị Euler (các đỉnh đều có bậc chẵn) thì
sẽ tồn tại hành trình là chu trình đơn.
Ta xét trường hợp đồ thị có một số đỉnh bậc lẻ. Như thế hành trình của
người đưa thư sẽ đi qua một số cạnh hai lần.
2.5.2. Giải thuật
B1: Khởi tạo. Tính tập đỉnh bậc lẻ U, |U|=2k. Tính khoảng cách d(u,v) từng cặp
phần tử (u,v) của U, min=vô cùng
Tiểu luận nhóm 1 Trang 14
Toán ứng dụng Chu trình Euler và bài toán người đưa thư
B2: Tìm phân hoạch s
min
có tổng khoảng cách min.
Với mỗi phân hoạch s gồm k cặp phần tử của U thực hiện.
{ Tính tổng T(s) = tổng d(u,v)

socap;=0; //biến số cặp
For i:= 1 to số đỉnh lẻ -1 do
For j:= i+1 to số đỉnh lẻ do
Begin socap:=socap+1;
//lưu các cặp đỉnh vào các cạnh dưới 2 mảng dau, cuoi
Dau[socap]:=B[i]; Cuoi[socap]:=B[j];
disjtra(A,B[i],B[j]);
D[socap]:=min;
// D la mang chua khoang cách ngắn nhất hai dinh
// thủ tục disjtra được xd phần sau.
End;
B2: Tìm phân hoạch Smin có tổng khoảng cách min
For mỗi cặp đỉnh (i,j) thuộc B do
Begin
danhdau[i]=danhdau[j]=False;//chưa đánh dấu
Cap[i,j]=False; //chưa đánh dấu
End;
For k:cặp đỉnh lẻ (i,j) thuộc B do
If(i,j chưa đánh dấu)and (cặp i,j chưa đánh dấu) then
Begin
Tính tổng khoảng cách của phân hoạch
Đếm số cặp DSC
Tiểu luận nhóm 1 Trang 15
Toán ứng dụng Chu trình Euler và bài toán người đưa thư
//Lưu số thứ tự cặp đỉnh được chọn vào mảng C
C[DSC]=k;
If (số cặp đỉnh lẻ = đếm số cặp) then
If Tổng k/c<Smin then
Begin
Smin:=tổng k/c;

if cạnh có đầu là x then //tìm được đỉnh kề x
begin
stackcuoi1[i];
{loai bo canh x,y khỏi dau1,cuoi1}
while i<=n-2 do
begin
dau1[i]:=dau1[i+1];
cuoi1[i]:=cuoi1[i+1];
i:=i+1;
end;
t:=t-1;
end
else //không tìm thấy đỉnh kề nó
begin
c:=c+1;
CE[c]:=x;
Tiểu luận nhóm 1 Trang 16
Toán ứng dụng Chu trình Euler và bài toán người đưa thư
end;
end;
end;
B4:// Chu trình euler được lưu vào mảng CE, thay các cạnh ảo bằng các đường đi
ngắn nhất
J:=1;
For mỗi cặp thứ i thuộc phân hoạch M do
Begin
x:=dau[M[i]]; y:=cuoi[M[i];
//c là số đỉnh trong chu trình Euler
While (j<=c) và (cặp đỉnh liền nhau j,j+1 ko thuộc
Smin) do

const vocung=32767;
struct dothi {
int n;
int A[max][max];
};
struct stack {
int top;
int A[max];
};
dothi G;
int chuaxet[max];
int m,i,j,sodinh, dodaimin=32767;
stack s,ce;
void khoitao();
void duyetdothi(int s);
int lienthong();
int kiemtraEuler();
void Euler(dothi G);
void main()
{
khoitao();
if (!lienthong()) {
printf("do thi khong lien thong");
}
else {
printf ("do thi lien thong");
if (kiemtraEuler()) {
printf(" va la do thi Euler");
Euler(G);
}

printf("\n so canh cua do thi m= %d",m);
printf("\n Ma tran trong so: \n");
for (i=1;i<=G.n ;i++ ){
for (j=1;j<=G.n ;j++ )
printf(" %d ",G.A[i][j]); printf("\n");
}
}
fclose(fp);
sodinh=G.n ;
}
void duyetdothi(int s)
{
int v;
for (v=1;v<=G.n ;v++ ){
if ((G.A[s][v]) && (chuaxet[v])) {
chuaxet[v]=0; duyetdothi(v);
}
}
}
int lienthong()
{
int i;
for (i=1;i<=G.n ;i++ )
chuaxet[i]=1;
chuaxet[1]=0; duyetdothi(1);
for (i=1;i<=G.n ;i++ )
if (chuaxet[i]) return 0;
return 1;
}
int kiemtraEuler()

if (x>G.n){
ce.top=ce.top+1; ce.A[ce.top]=v;
s.top=s.top-1;
}
else {
s.top=s.top+1; s.A[s.top]=x;
G.A[v][x]=0; G.A[x][v]=0;
}
}while (s.top);
v=1;
while (v<ce.top) {
while (ce.A[v]<=sodinh)
v=v+1;
if (v<ce.top) {
for (x=v+1;x<=ce.top ;x++ )
ce.A[x-1]=ce.A[x]; ce.top=ce.top-1;
}
}
d=0;
for (u=1;u<ce.top ;u++ ) {
d= d + W[ce.A[u]][ce.A[u+1]]; printf(" \n d = %d", d);
}
d= d + W[ce.A[u]][ce.A[1]];
printf(" \n do dai = %d", d);
printf("\n Hanh trinh cua nguoi dua thu nhu sau: ") ;
for (u=1;u<=ce.top ;u++ ) {
printf("%d=>", ce.A[u]);
}
printf("%d",ce.A[1]);
getchar();

typedef int mangphanhoach[max];
dothi G;
int chuaxet[max]; int W[max][max];
dinhbacle dinhle,H, vetdi;
mangphanhoach b,q;
int m, i,j,sodinh, dodaimin=500; stack s,ce;
void khoitao();
void duyetdothi(int s);
int lienthong();
int kiemtraEuler();
void timdinhle();
int duongdi(int s, int t);
void hoanvi(int k,int i,mangphanhoach B);
void phanhoach();
void themcanh(int i,int j);
void vetduongdi(int s, int t);
void suadothi();
void Euler(dothi G);
void main()
{
khoitao(); if (!lienthong())
{
printf("do thi khong lien thong");
}
Else {
printf ("do thi lien thong");
if (kiemtraEuler())
{
printf("va la do thi Euler");
} else

printf("\n Ma tran trong so: \n");
for (i=1;i<=G.n ;i++ ){
for (j=1;j<=G.n ;j++ )
printf(" %d ",G.A[i][j]); printf("\n");
}
}
fclose(fp); sodinh=G.n ;
}
void duyetdothi(int s)
{
int v;
for (v=1;v<=G.n ;v++ ){
if ((G.A[s][v]) && (chuaxet[v])) {
chuaxet[v]=0;
duyetdothi(v);
}
}
}
int lienthong()
{
int i;
for (i=1;i<=G.n ;i++ )
chuaxet[i]=1;
chuaxet[1]=0;
duyetdothi(1);
for (i=1;i<=G.n ;i++ )
if (chuaxet[i])
return 0; return 1;
}
int kiemtraEuler()

int min,u,i; int L[max];
int W[max][max];
for (i=1;i<=G.n ;i++ )
for (j=1;j<=G.n ;j++ )
if (G.A[i][j]>0)
W[i][j]=G.A[i][j];
else
W[i][j]=vocung;
for (i=1;i<=G.n ;i++ ){
L[i]=vocung; chuaxet[i]=1;
}
L[s]=0;
while (chuaxet[t]){
min=vocung;
for (i=1;i<=G.n ;i++ ){
if ((chuaxet[i]==1) && (min>L[i])) {
min=L[i]; u=i;
}
}
chuaxet[u]=0; for (i=1;i<=G.n ;i++ )
if ((chuaxet[i]==1) && (L[i]>L[u]+W[u][i]))
L[i]=L[u]+W[u][i];
}
// printf("duong di %d ",L[t]);
return L[t];
}
void hoanvi(int k,int i,mangphanhoach B)
{
int j,dodai,u;
if (k==H.n){

chuaxet[i]=1;
}
}
void themcanh(int i,int j)
{
int k;
G.n=G.n+1;
for (k=1;k<=G.n ;k++ )
G.A[k][G.n]=0;
for (k=1;k<=G.n ;k++ )
G.A[G.n][k]=0; G.A[i][G.n]=1;
G.A[G.n][i]=1; G.A[j][G.n]=1; G.A[G.n][j]=1;
printf("\n Them dinh %d va them canh %d,%d va canh %d,
%d",G.n,i,G.n,G.n,j);
}
void vetduongdi(int s, int t)
{
int min,u,i;
int L[max];
int p[max];
int W[max][max];
for (i=1;i<=G.n ;i++ )
for (j=1;j<=G.n ;j++ )
if (G.A[i][j]>0)
W[i][j]=G.A[i][j];
else
W[i][j]=vocung;
for (i=1;i<=G.n ;i++ ) {
L[i]=vocung;
chuaxet[i]=1; p[i]=s;