Đường đi Euler
Hỏi: Các hình này có vẽ được một nét không?
Trả lời: Được! Nhưng điểm cuối không trùng điểm xuất phát
Trong lý thuyết đồ thị, một đường đi trong đồ thị G=(X,E) được gọi là đường đi Euler nếu nó đi
qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần. Đường đi Euler có đỉnh cuối cùng trùng với
đỉnh xuất phát gọi là chu trình Euler. Khái niệm chu trình Euler xuất phát từ bài toán bảy cây cầu
do Euler giải quyết vào khoảng năm 1737. Đường đi Euler có thể tìm thấy trong các bài toán vui vẽ
một nét (vẽ một hình nào đó mà không nhấc bút khỏi mặt giấy, không tô lại cạnh nào hai lần).
Carl Hierholzer là người đầu tiên mô tả hoàn chỉnh đồ thị Euler vào năm 1873, bằng cách chứng
minh rằng đồ thi Euler là đồ thị liên thông không có đỉnh bậc lẻ.
Định nghĩa về chu trình và đường đi Euler
1. Đường đi Euler (tiếng Anh: Eulerian path, Eulerian trail hoặc Euler walk) trong đồ thị vô
hướng là đường đi của đồ thị đi qua mỗi cạnh của đồ thị đúng một lần.
2. Chu trình Euler (tiếng Anh: Eulerian cycle, Eulerian circuit hoặc Euler tour) trong đồ thị vô
hướng) là một chu trình đi qua mỗi cạnh của đồ thị đúng một lần.
3. Đồ thị gọi là đồ thị Euler khi nó chứa chu trình Euler, và được gọi là nửa Euler khi nó chứa
đường đi Euler.
4. Đối với các đồ thị có hướng, các thuật ngữ đường đi và chu trình được thay bằng đường đi
có hướng và chu trình có hướng.
• Ghi chú: Một đồ thị là Euler thì sẽ là nửa Euler; điều ngược lại không đúng.
Định lý Euler về chu trình và đường đi Euler
Đồ thị Bảy cây cầu Königsberg có 4 đỉnh bậc lẻ nên không là đồ thị Euler
1. Đồ thị vô hướng liên thông G=(X, E) có chu trình Euler khi và chỉ khi G không có đỉnh bậc
lẻ.
1
2. Đồ thị vô hướng liên thông G=(X, E) có đường đi Euler khi và chỉ khi G có không quá hai
đỉnh bậc lẻ. Nếu G có hai đỉnh bậc lẻ thì đường đi Euler có hai đầu đường đi nằm ở hai đỉnh
bậc lẻ.
Các tính chất khác
1. Một đồ thị vô hướng là đồ thị Euler nếu nó liên thông và có thể phân tích thành các chu trình
có các cạnh rời nhau.

bỏ tất cả các chi tiết ngoại trừ các vùng đất và các cây cầu, sau đó thay thế mỗi vùng đất bằng một
điểm, gọi là đỉnh hoặc nút, và thay mỗi cây cầu bằng một đoạn nối, gọi là cạnh hoặc liên kết. Cấu
trúc toán học thu được được gọi là một đồ thị.
→ →
Hình thù của đồ thị có thể bị bóp méo theo đủ kiểu nhưng không làm đồ thị bị thay đổi, miễn là các
liên kết giữa các nút giữ nguyên. Việc một liên kết thẳng hay cong, một nút ở bên phải hay bên trái
một nút khác là không quan trọng.
Euler nhận ra rằng bài toán có thể được giải bằng cách sử dụng bậc của các nút. Bậc của một nút là
số cạnh nối với nó; trong đồ thị các cây cầu Königsberg, ba nút có bậc bằng 3 và một nút có bậc 5.
Euler đã chứng minh rằng một chu trình có dạng như mong muốn chỉ tồn tại khi và chỉ khi không có
nút bậc lẻ. Một đường đi như vậy được gọi là một chu trình Eul er . Do đồ thị các cây cầu Königsberg
có bốn nút bậc lẻ, nên nó không thể có chu trình Euler.
3
Có thể sửa đổi bài toán để yêu cầu một đường đi qua tất cả các cây cầu nhưng không cần có điểm
đầu và điểm cuối trùng nhau. Đường đi như vậy được gọi là một đường đi Euler. Một đường đi như
vậy tồn tại khi và chỉ khi đồ thị có đúng hai đỉnh bậc lẻ. (Như vậy điều này cũng không thể đối với
bảy cây cầu ở Königsberg.)
Ý nghĩa của bài toán đối với lịch sử toán học
Trong lịch sử toán học, lời giải của Euler cho bài toán bảy cây cầu ở Königsberg được coi là định lý
đầu tiên của lý thuyết đồ thị, ngành nghiên cứu mà nay được coi là một nhánh của toán học tổ hợp
(combinatorics), tuy các bài toán tổ hợp đã được quan tâm đến từ sớm hơn rất nhiều.
Ngoài ra, nhận xét của Euler rằng thông tin quan trọng là số cây cầu và danh sách các vùng đất ở đầu
cầu (chứ không phải vị trí chính xác của chúng) đã là dấu hiệu cho sự phát triển của ngành tôpô học.
Sự khác biệt giữa sơ đồ thực và sơ đồ đồ thị là một ví dụ tốt rằng tôpô học không quan tâm đến hình
thù cứng nhắc của các đối tượng.
4
Đường đi Hamilton
Trong toán học, ngành lý thuyết đồ thị, một đường đi Hamilton là một đường đi trong đồ thị vô
hướng đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần. Một Chu trình Hamilton là một
đường đi Hamilton sau đi qua tất cả các đỉnh của đồ thị thì trở về đỉnh xuất phát.

đến là thuật toán Prim và thuật toán Krusskal.
• Xem thêm Thuật toán tìm cây bao trùm
Bài toán
Cho G=(X,E) là một đồ thị liên thông. Ngoài ra, một hàm trọng số W(e) nhận các giá trị thực, xác
định trên tập các cạnh E của G. Cả hai thuật toán Prim và Kruskal đều dựa trên tư tưởng của các giải
thuật tham lam: Ở mỗi bước của thuật toán ta chọn và bổ sung vào cây cạnh có trọng số nhỏ nhất có
thể.
Giải thuật Prim
Giải thuật Prim dựa trên cấu trúc của giải thuật tìm cây bao trùm theo chiều rộng hoặc chiều sâu, chỉ
thay đổi về tiêu chuẩn chọn đỉnh sẽ bổ sung vào cây ở từng bước.
// Vài nét R. C. Prim
Robert Clay Prim (sinh 1921 tại Sweetwater, Texas) là một nhà toán học và khoa học máy tính Mỹ.
Năm 1941 ông đã lấy bằng cử nhân ở khoa kỹ thuật điện đại học Princeton. Sau này năm 1949, ông
nhận bằng Ph.D. về toán học cũng tại đây. Giải thuật mang tên Prim được tìm ra từ năm 1930 bởi
nhà toán học Vojtěch Jarník và do Prim hoàn thiện vào năm 1957.
Mô tả
7
Gọi T là cây bao trùm sẽ xây dựng
1. Chọn một đỉnh s bất kỳ của G cho vào cây T. Khi đó T là một cây chỉ có một đỉnh và chưa có
cạnh nào.
2. Nếu T đã gồm tất cả các đỉnh của G thì T là cây bao trùm cần tìm. Kết thúc.
3. Nếu G còn có các đỉnh không thuộc T, vì G liên thông nên có các cạnh nối một đỉnh trong T
với một đỉnh ngoài T, chọn một cạnh có trọng số nhỏ nhất trong số đó cho vào T.
4. Quay lại 2.
Giả mã
Giải thuật trình bày Prim ở trên dễ dàng thực hiện khi ta quan sát một đồ thị được biểu diễn trên mặt
phẳng với một số ít đỉnh. Tuy nhiên để cài đặt thành một chương trình chạy trên máy tính cũng cần
phân tích thêm một số điểm.
Liệu có thể sử dụng một hàng đợi (queue) giống như trong giải thuật tìm cây bao trùm theo chiều sâu
không? Có. Nhưng điều khác biệt là ta sẽ sử dụng một hàng đợi có ưu tiên, tiêu chuẩn ưu tiên ở đây

For each v of Ajd(u) {
if (Color(v)=WHITE)
or ((Color(v)=GRAY) and (DISTAN(v)<W(u,v)
8
then
{
COLOR(v)=GRAY
PARENTS(v)=u
DISTAN(v)=W(u,v)
if Color(v)=WHITE then InsertHeap(H,v)
else UpHeap(H,HeapIndex(v))
}
}
}

Một chương trình đầy đủ bằng ngôn ngữ Pascal
program Prim_Algorithm;
uses dos,crt;
const max=150;
type
filename=string[12];
var
TrongSo: array[1 max,1 max] of integer;
DinhKe: array[1 max] of integer;
CanhKe: array[1 max] of integer;{}
n, DodaiCayKhung: integer;
i,j: integer;
fname: filename;
ch: char;
h,m,s, hund:word;

readln(f);
9
end;
close(f);
PrintMatrix;
end;
procedure Prim;
var
v,i,k: integer;
min: integer;
begin
for v:=2 to n do
begin
DinhKe[v]:=1;
CanhKe[v]:=TrongSo[1,v];
end;
for i:=2 to n do
begin
min:=MaxInt;
for k:=2 to n do
if (CanhKe[k]>=0) and (CanhKe[k]<min) then
begin
min:=CanhKe[k]; (
v:=k;
end;
CanhKe[v]:=-1;
for k:=2 to n do
if (TrongSo[v,k]<CanhKe[k]) and (TrongSo[v,k]>0) then
begin
CanhKe[k]:=TrongSo[v,k];

writeln(f,'Length: ',DodaiCayKhung);
close(f);
10
end;
begin
repeat
clrscr;
writeln('THUAT TOAN PRIM TIM CAY KHUNG NHO NHAT');
writeln(' DUNG MA TRAN KE');
writeln(' ');
writeln(' Hay bam phim chuc nang:');
Writeln;
writeln(' K(eyboard). Chay chuong trinh - Du lieu nhap tu ban phim.');
Writeln;
writeln(' F(ile). Chay chuong trinh - Du lieu lay tu File.');
Writeln;
writeln(' R(andom). Chay chuong trinh - Du lieu Random.');
Writeln;
writeln(' Q(uit). Thoat khoi chuong trinh.');
Writeln;
ch:=ReadKey;
case UpCase(ch) of
'F':
begin
write(' Hay nhap ten tep du lieu:'); readln(fname);
ReadInputFile(fname);
gettime(h,m,s,hund);
Writeln('Bat dau chay: ',h,':',m,':',s,':',hund);
Prim;
gettime(h,m,s,hund);

Writeln;
writeln('Gia cua cay khung : ',DodaiCayKhung);
writeln;
11
writeln('***************************************');
writeln('Nhan phim Enter de tiep tuc.');
readln;
end;
'K':
begin
write('Hay nhap so dinh cua do thi:'); readln(n);
for i:=1 to n do TrongSo[i,i]:=0;
for i:=1 to n-1 do
For j:=i+1 to n do
Begin
Write('a[',i,j,']=');
readln(TrongSo[i,j]); (* Nua tren *)
End;
for i:=2 to n do
For j:=1 to i-1 do TrongSo[i,j]:=TrongSo[j,i];
PrintMatrix;
for i:=1 to n do
for j:=1 to n do
if TrongSo[i,j]=0 then TrongSo[i,j]:=MaxInt;
gettime(h,m,s,hund);
Writeln('Bat dau chay: ',h,':',m,':',s,':',hund);
Prim;
gettime(h,m,s,hund);
Writeln('Ket thuc chay: ',h,':',m,':',s,':',hund);
write('Cac canh cua cay khung be nhat:');

IndexHeap(v)=n
UpHeap(H,n)
}
Procedure UpHeap (H,k){
i:= Lshift(k,1) /*Chia đôi lấy phần nguyên*/
While (k>0) and DISTAN(H(k))<DISTAN(H(i)) {
Swap(H(k),H(i)) /*Đổi chỗ H(k) H(i)*/
k:=i
i:=LShift(k,1) /*Chia đôi lấy phần nguyên*/
}
}
13
Giải thuật Kruskal
Giải thuật Kruskal không dựa trên tư tưởng của các thuật toán tìm kiếm theo chiều rộng hoặc chiều
sâu. Trong các thuật toán này, tại từng bước của quá trình xây dựng T luôn là một cây, chỉ có điều
kiện về số đỉnh của T phải đến bước cuối cùng mới thỏa mãn. Còn trong thuật toán Kruskal, trong
quá trình xây dựng T có thể chưa là cây, nó chỉ thỏa mãn điều kiện không có chu trình.
Mô tả
Giả sử G liên thông có n đỉnh. Gọi T là cây bao trùm sẽ xây dựng.
1. Khởi tạo: T lúc đầu là một đồ thị rỗng.
2. Nếu T đã gồm đúng n-1 cạnh của G thì T là cây bao trùm cần tìm. Kết thúc.
3. Nếu T còn chưa đủ n-1 cạnh, thì vì G liên thông, nên G có không ít hơn n-1 cạnh, do đó còn
các cạnh của G chưa thuộc T. Trong các cạnh của G chưa thuộc T có các cạnh không tạo ra
chu trình với các cạnh đã có trong T, Chọn cạnh v có trọng số nhỏ nhất trong các cạnh ấy bổ
sung (cùng với các đỉnh chưa thuộc T của nó) vào T.
4. Quay lại 2.
Một vài tác giả có cách trình bày khác của giải thuật Kruskal, tuy bản chất quá trình là giống nhau
1. Khởi tạo: T lúc đầu gồm tất cả các đỉnh của G và chưa có cạnh nào,như vây T lúc đầu là một
rừng n cây,mỗi cây gồm đúng một đỉnh.
2. Nếu T chỉ gồm một cây thì dừng

đỉnh u trong mảng V.
Hàm trọng số W(u,v) xác định trên các cạnh . Với mỗi cạnh e=(u,v) ký hiệu e.x u,
e.y=v là hai đỉnh liên thuộc với cạnh e.
• Các biến sau được đưa vào
o Hàng đợi Q của các cạnh xếp theo thứ tự trọng số từ nhỏ đến lớn.
o Với mỗi cây con, hàm PARENTS(u) xác định trên V, biểu diễn chỉ số của đỉnh cha
của đỉnh u trong một cây. Riêng đỉnh gốc u của mỗi cây hàm PARENTS(u)lưu trữ số
đỉnh trong cây với dấu âm.
Mã
Procedure Kruskal (G)
T = V;
Q =Sort(E)
/* Tạo n cây, mỗi cây gồm một đỉnh*/
For each u of X do Parent(u):=-1;
m = |E|
For j:=1 to m do {
u:=NodeStart(Q(j)); V:=NodeEnd(Q(j))
If Find_tree(u)<>Find_tree(V) then
T:=T U Q[j];
Union(u,v;)

15
Thuật toán Dijkstra
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

• Để tính được giá trị nhỏ nhất này, như thông thường khi khởi tạo ta phải gán cho d(v)= ,
sau đó gặp giá trị nhỏ hơn thì thay thế lại.
• Những đỉnh đã tính được d(v)hữu hạn được cho vào một hàng đợi có ưu tiên. Hàng đợi này
luôn được bổ sung và sắp xếp lại nên một cấu trúc hợp lý là cấu trúc đống nhị phân (heap).
• Để theo dõi trạng thái của các đỉnh trong quá trình xét, ta dùng hàm COLOR(u) xác định với
mọi . Lúc đầu các đỉnh được tô màu trắng (WHITE), khi cho vào hàng đợi nó được tô
màu xám (GRAY), khi đã tính xong khoảng cách nó được tô màu đen(BLACK).
• Nếu cần ghi lại đường đi ta sẽ phải dùng một hàm con trỏ PRE(u) để chỉ đỉnh đứng ngay
trước đỉnh u trên đường đi ngắn nhất từ s tới u.
Mã
Procedure Dijkstra {
For each v of V do {
d(v)=M
COLOR(v)=WHITE
d(s)=0

InsertHeap(Q,s)
k=1
While Q khác rỗng do {
u=Head(Q)
Push(Q,u)
k=k-1
COLOR(u)=BLACK
For each v of Ajd(u) {
if COLOR(v)=WHITE then {
k=k+1
HeapIndex(v)=k
InsertHeap(Q,v)
COLOR(v)=GRAY
PRE(v)=u

Thuật toán Dijkstra bình thường sẽ có độ phức tạp là O( n^2+m ). Tuy nhiên ta có thể sử dụng kết
hợp với cấu trúc heap, khi đó độ phức tạp sẽ là O( (n+m)*log2(n) )
18
Cây bao trùm
Cây bao trùm (tiếng Anh: spanning tree), còn được gọi là cây khung, của đồ thị G là cây con của
đồ thị G, chứa tất cả các đỉnh của G. Nói cách khác, cây bao trùm của một đồ thị G là một đồ thị con
của G, chứa tất cả các đỉnh của G, liên thông và không có chu trình.
Cây bao trùm của đồ thị liên thông G cũng có thể định nghĩa như một đồ thị con không chu trình lớn
nhất, hay một đồ thị con liên thông nhỏ nhất của G.
Mọi đồ thị liên thông đều có cây bao trùm.
Số các cây bao trùm của một đồ thị liên thông
Gọi t(G) là số các cây bao trùm của đồ thị liên thông G. Trong một số trường hợp, số t(G) có thể tính
trực tiếp. Chảng hạn nếu G là một cây, khi đó t(G)=1, còn khi G là một đồ thị vòng C
n
với n đỉnh thì
t(G)=n. Với đồ thị G bất kỳ, số t(G) có tính nhờ Định lý Kirchhoff.
Công thức Cayley là công thức cho số các cây bao trùm của đồ thị đầy đủ K
n
với n đỉnh: t(K
n
) = n
n −
2
.
Nếu G là đồ thị hai phía đầy đủ K
p,q
, thì t(G) = p
q − 1
q
p − 1

4. Quá trình dừng lại khi tất cả các đỉnh đã nằm trong T đã được xét.
3. T là cây bao trùm cần tìm.
Ví dụ
Với sự mô tả trên đây có thể tìm cây bao trùm dễ dàng trên các đồ thị có số các đỉnh và cạnh tương
đối nhỏ.
Mã giả
Để xây dựng giải thuật trên máy tính cần làm rõ các cấu trúc dữ liệu biểu diễn đồ thị cũng như quá
trình xét các đỉnh và các cạnh. Giả sử đồ thị G cho bởi các danh sách các cạnh kề với từng đỉnh.
Danh sách này thường được ký hiệu là Adj[u] đối với danh scáh các cạnh kề đỉnh u. Để phân biệt
các đỉnh chưa nằm trong T, các đỉnh trong T đã xét xong và chưa xét, ta hình dung một quá trình tô
màu các đỉnh: Đỉnh mới bổ sung vào T thì tô màu xám (GRAY), đỉnh trong T đã xét xong thi tô màu
đen (BLACK), các đỉnh chưa nằm trong T thi tô mầu trắng (WHITE). Ta còn muốn xác định các
cạnh nào nằm trên cây. Xem T như một cây có gốc, trừ gốc, mỗi cạnh trong cây nối một đỉnh với
cha của nó, vì vậy ta dùng một hàm Parent(u) để xác định các cạnh được đưa vào cây T. Vì thế, khi
khởi tạo ta có các biến danh sách COLOR(u) và PARENTS(u). Theo nguyên tắc xét đỉnh gần gốc
nhất, các đỉnh gia nhập cây sớm sẽ được xét trươc. Để "theo dõi" chặt chẽ thứ tự các đỉnh được đưa
vào T ta dùng một cấu trúc hàng đợi Q (Queue).
20
Procedure BFS(G,r) {
Var list COLOR(u),PARENTS(u),Queue Q
/* Khởi tạo */
For each u of E do {
GRAY(u)=WHITE
PARENTS(u)=Null
}
Push(Q,r) /*Đẩy đỉnh đầu tiên vào hàng đợi*/

/*Xét các đỉnh*/
While Q <> rỗng do {
u = Pop(Q);/*Lấy đỉnh đầu hàng đợi Q ra để xét*/

3. Quá trình dừng lại khi tất cả các đỉnh nằm trong T đã được xét.
3. T là cây bao trùm cần tìm.
Ví dụ
Mã giả
Trong mã của giải thuật tìm kiếm theo chiều sâu ta cũng đưa vào các biến danh sách CORLOR(u) và
PARENTS(u) trên tập các đỉnh. Sau khi khởi tạo ta dùng cách gọi đệ quy để tìm cây bao trùm của
G(X,E)
Procedure DFS ( G ){
/*Khởi tao*/
For each đỉnh of E do {
COLOR[u] := WHITE
PARENTS(u)=Null
}
/* Tìm kiếm đệ quy*/
For each đỉnh u of E do
if if COLOR[u] = WHITE
then DFS-Visit (u)
Return PARENTS;
}
Procedure DFS-Visit(u) {
COLOR[u]:= GRAY /*Bắt đầu xét u*/
for each v of Adj[u] do {
if COLOR[v] = WHITE
then {
PARENTS[v] := u
DFS-Visit (v)
}
}
COLOR[u]:=BLACK /*Xét xong u*/
}

Breack
find=TRUE
}
if not Find then {
COLOR(u)=BLACK
Pos(S,u) /*Lấy u khỏi Stack */
}
}
}
Trong giải thuật này mỗi lần xét một đỉnh cuối trong ngăn xếp, ta không vội vã đưa nó ra khỏi ngăn
xếp. Nó chỉ được xét xong và đưa khỏi ngăn xếp khi tất cả các đỉnh kề với nó đã được đưa vào cây
(nằm chờ trong ngăn xếp hoặc đã xét xong). Mỗi lần một đỉnh đưa khỏi ngăn xếp ta quay lại xét
phần tử đứng trước nó trong ngăn xếp là ta đã thức hiện một thao tác "quay lui". Như vậy đỉnh đưa
vào đầu tiên bao giờ cũng là đỉnh cuối cùng ra khỏi ngăn xếp.
Thay cho thao tác tìm đỉnh trắng trong danh sách kề với đỉnh u, ta cũng có thể lấy ngay phần tử đầu
tiên v trong danh sách kề Adj(u) (nếu nó khác rỗng) vào ngăn xếp và xóa v khỏi danh sách kề. Khi
đó toàn bộ các đỉnh trong danh sách kề của u đều chưa được xét.
Ta có:
Procedure DFS(G,r){
Var Stack S, list COLOR(u), PARENTS(u)
/*Khởi tạo: Tất cả các đinh chưa xét */
For each' v of E do {
COLOR(u):=WHITE
PARENTS(u):=NULL
}
/* Cho đỉnh đầu tiên vào Stack*/
COLOR(r):=GRAY
Push(S,r)
23
/*lần lượt xét các đỉnh*/