ĐẠI HỌC QUỐC GIA HÀ NỘI
ĐẠI HỌC KHOA HỌC TỰ NHIÊN
Khoa Toán - Cơ - Tin học

BÀI TẬP LỚN

Tìm cây bao trùm nhỏ nhất từ một đồ
thị liên thông có trọng số
Sinh viên thực hiện:
Lớp:
Môn học:
Giáo viên hướng dẫn:

HÀ NỘI - 2012

Phan Anh Quân
K61 - CNKHTN Toán
Thực hành Tính toán
Nguyễn Hữu Điển


51
89/176-05
GD-05

Mã số: 8I092M5


Phan Anh Quân : K61 - CNKHTN Toán

2

LỜI NÓI ĐẦU
Bài toán tìm cây bao trùm nhỏ nhất là một bài toán rất nổi tiếng trong lý thuyết
đồ thị, nó có rất nhiều ứng dụng quan trọng như trong việc thiết kế các mạng lưới
(điện thoại, TV, điện, internet,...), tìm thuật toán xấp xỉ cho các bài toán độ khó NP,...
Để tìm được cây bao trùm nhỏ nhất ta có thể áp dụng các thuật toán như Thuật
toán Boruvka,
Thuật toán Prim, Thuật toán Kruskal. Trong bài viết này, ngoài việc
˚
giới thiệu về phần mềm Maple cũng như một số kiến thức cơ bản về cây, em xin được
trình bày về hai thuật toán Prim và Kruskal và viết chương trình Maple cho hai thuật
toán trên.
Nhân đây, em xin bày tỏ sự biết ơn sâu sắc tới PGS.TS Nguyễn Hữu Điển, người
đã tận tình giúp đỡ để em có thể hoàn thành bài tập lớn.
Mọi sự đóng góp xin gửi về địa chỉ:
Sinh viên: Phan Anh Quân
Lớp học: K61 - CNKHTN Toán


MỤC LỤC

3

Mục lục
1

Giới thiệu về Maple
1.1 Maple là gì? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Một số chức năng chính của Maple . . . . . . . . . . . . . . . . . . . . .
1.3 Cấu trúc của Maple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


4
4
4
5

2

Một số khái niệm cơ bản
2.1 Cây . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Cây bao trùm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Cây bao trùm nhỏ nhất . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6
6
8
9

3

Một số thuật toán tìm cây bao trùm nhỏ nhất
10
3.1 Thuật toán Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Thuật toán Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

Tài liệu tham khảo

21



1. Giới thiệu về Maple

1

4

Giới thiệu về Maple

Trong phần này chúng ta sẽ điểm qua một số thông tin liên quan đến phần mềm
Maple

1.1

Maple là gì?

Maple là một phần mềm tính toán chuyên dụng do Đại học Tổng hợp Waterloo
(Canada) và trường Đại học Kỹ thuật Zurich (ETZ) xây dựng và đưa vào thương
mại đầu tiên năm 1985. Phần mềm đã trải qua nhiều lần cải tiến và phát triển với
nhiều phiên bản khác nhau, trở nên ngày càng hoàn thiện. Maple chạy trên tất cả các
hệ điều hành, đòi hỏi cấu hình máy tính không lớn, thích hợp nhu cầu sử dụng của
nhiều loại đối tượng: học sinh, sinh viên, giáo viên,... Từ phiên bản 7, Maple cung cấp
càng nhiều các công cụ trực quan, các gọi lệnh tự học gắn liền với toán phổ thông và
đại học. Ưu điểm đó khiến ngày càng có nhiều nước trên thế giới lựa chọn sử dụng
Maple trong dạy - học toán tương tác trước đòi hỏi của thực tiễn và sự phát triển của
giáo dục

1.2

Một số chức năng chính của Maple


• Thực hiện các tính toán khối lượng lớn trong thời gian ngắn với độ chính xác
cao, đáp ứng nhu cầu khắt khe trong nghiên cứu Khoa học kỹ thuật.
• Giải quyết các bài toán cụ thể như: Giải tích (Tính giới hạn các hàm số
thực/phức, tính vi phân, nguyên hàm, tích phân,...), Đại số tuyến tính(sử dụng
gói lệnh LinearAlgebra), Giải phương trình (Phương trình đại số, phương trình
Diophantine, ODEs, PDEs, DAEs, DDEs), hình học (gói geometry), lý thuyết số
(gói numtheory),...
• Thuận tiện trong việc minh họa hình học: Vẽ các đồ thị (đồ thị chu tuyến, đồ
thị điểm,...) trong các tọa 2 chiều Oxy, tọa độ Oxyz, tọa độ cực,... ; cho phép
thực hiện các phép biến đổi đồ thị (co giãn, tịnh tiến, quay,...), minh họa đồ thị
động cho phép thấy sự biến thiên của hàm số có tham số.
• Một công cụ hữu ích cho học sinh, sinh viên trong việc tự học.
• Một công cụ hữu ích cho giáo viên trong việc biên soạn giáo án và bài giảng
điện tử, thích hợp với các lớp học tương tác trực tiếp.
• Ngôn ngữ lập trình đơn giản, mạnh mẽ, có khả năng tương tác với nhiều
ngôn ngữ lập trình khác như C, C#, Fortran, Java, JavaScript, Julia, Matlab,
Perl, Python, R, và Visual Basic.
• Có khả năng thúc đẩy tương tác giữa người và máy, cho phép người dùng phát
triển các module chuyên dụng, lập trình hoặc thư viện riêng ngay trong phần
mềm.
• Và nhiều tính năng khác ...


1.3

1.3

Cấu trúc của Maple

5


Cấu trúc của Maple

Maple dựa trên một hạt nhân nhỏ, được viết bằng C, từ đó cung cấp ngôn ngữ lập
trình Maple. Hầu hết các tính năng được cung cấp bởi các thư viện chuyên dụng đến
từ nhiều nguồn khác nhau. Hầu hết các thư viện được viết bằng ngôn ngữ Maple,
với mã nguồn có thể xem được. Nhiều các tính toán số được thực hiện bởi Thư viện
số NAG. thư viện ATLAS hoặc thư viện GMP.
Chức năng khác nhau trong Maple đòi hỏi dữ liệu số ở dưới các định dạng khác
nhau. Các ký hiệu, biểu tượng được lưu trữ trong bộ nhớ dưới dạng các đồ thị có
hướng không chu trình. Giao diện chuẩn và giao diện máy tính (calculator interface)
của Maple được viết bằng Java.


2. Một số khái niệm cơ bản

2

6

Một số khái niệm cơ bản

Trong chương này ta sẽ trình bày một số khái niệm liên quan đến bài viết: cây,
cây bao trùm.

2.1

Cây

Ta có một số ví dụ về cây như sau:


Hình 2.1: Gia đình Toán học Bernoulli

Hình 2.2: Các đồ thị là cây (G1 , G2 ) và không phải là cây (G3 , G4 )


2.1

Cây

7

Ta định nghĩa cây như sau
Định nghĩa 2.1. Một cây là một đồ thị vô hướng, liên thông và không có chu trình.
Bởi vì một cây thì không có chu trình, nó không thể chứa các đa cạnh (qua hai
đỉnh có nhiều hơn một cạnh) hay cạnh khuyên (cạnh có hai đầu mút trùng nhau). Vì
vậy, một cây phải là một đồ thị đơn.
Ví dụ 2.1. Trong Hình 2.2, các đồ thị G1 , G2 là cây bởi vì chúng đều liên thông và
không có một chu trình đơn nào. Trong khi đó đồ thị G3 không là cây do nó có một
chu trình là ( a, b, c, d, a). Còn đồ thị G4 thì không liên thông do đó nó cũng không là
cây.
Dưới đây ta sẽ nói qua một số kiểu cây đặc biệt.
Định nghĩa 2.2. Một cây được gọi là cây có gốc nếu như một đỉnh của nó được xác
định là gốc và các cạnh đều được hướng ra từ gốc.
Ví dụ 2.2. Cây có gốc

Hình 2.3: Một cây và các cây có gốc được tạo bằng cách đặt hai gốc khác nhau
Trong một cây có gốc :
• Với mọi đỉnh v trong cây khác gốc, tồn tại duy nhất một đỉnh u sao cho có một
cạnh hướng ra (u, v) (tồn tại duy nhất do không có chu trình trong cây). u được

gọi là đỉnh mẹ của v, v được gọi là đỉnh con của u.
• Các đỉnh có cùng một đỉnh mẹ được gọi là anh em
• Tổ tiên của một đỉnh v khác gốc là các đỉnh nằm trên đường đi từ gốc đến đinh
v khác chính v (tức là đỉnh mẹ, đỉnh mẹ của đỉnh mẹ, tiếp tục cho đến gốc)
• Hậu duệ của một đỉnh v là tất cả các đỉnh nhận v là tổ tiên.
• Một đỉnh không có con được gọi là lá của cây. Một đỉnh có con được gọi là một
đỉnh trong của cây.
• Nếu v là một đỉnh trong cây, cây con gốc v là một đồ thị con chứa v cùng với
tất cả hậu duệ của v và các cạnh nối đến chúng.


2.2

Cây bao trùm

8

Định nghĩa 2.3. Một cây có gốc được gọi là một cây m-phân nếu mỗi đỉnh trong có
không quá m đỉnh con. Cây này được gọi là m-phân đầy đủ nếu mỗi đỉnh có chính
xác m đỉnh con. Một cây m-phân với m = 2 được gọi là một cây nhị phân.
Ví dụ 2.3. Trong Hình 2.4 dưới đây, T1 là một cây nhị phân đầy đủ, T2 là một cây
3-phân đầy đủ, T3 là một cây 5-phân đầy đủ, T4 là một cây 3-phân.

Hình 2.4: Cây m-phân
Để nhận biết khi nào đồ thị là một cây, ta có định lý sau
Định lý 2.1 (Định lý cơ bản về cây). Cho G = (V, E) là một đồ thị vô hướng, các mệnh
đề sau là tương đương:
1. G là cây
2. G liên thông và | E| = |V | − 1
3. G không có chu trình, | E| = |V | − 1

4. G liên thông, nhưng nếu xóa đi một cạnh bất kỳ thì G không còn liên thông nữa
5. G không có chu trình, nhưng nếu thêm một cạnh vào thì G sẽ có chu trình
6. Giữa hai đỉnh bất kỳ của G luôn tồn tại duy nhất một đường đi

2.2

Cây bao trùm

Định nghĩa 2.4. Cho G là một đồ thị đơn. Một cây bao trùm (spanning tree) của G
là một đồ thị con là cây chứa tất cả các đỉnh của G

Hình 2.5: Cây bao trùm (được tô đậm) của một đồ thị
Ta có một định lý đơn giản sau đây.
Định lý 2.2. Một đồ thị đơn là liên thông khi và chỉ khi nó chứa một cây bao trùm


2.3

Cây bao trùm nhỏ nhất

2.3

9

Cây bao trùm nhỏ nhất

Trước tiên ta sẽ nêu định nghĩa sau.
Định nghĩa 2.5 (Đồ thị có trọng số). Một đồ thị có trọng số (weighted graph) là một
đồ thị mà mỗi cạnh của nó được gắn với một hằng số cụ thể. Hằng số đó được gọi là
trọng số (weight) của cạnh đó.

Trên thực tế, một đồ thị có trọng số xuất hiện vô cùng phổ biến. Ví dụ, trong một
bản đồ với mỗi điểm là các địa điểm riêng biệt và các cạnh là các đường đi nối hai
điểm, trọng số của mỗi cạnh sẽ là độ dài của đường đi đó hoặc giá tiền để đi trên
đường đi đó. Hay trong một hệ thống dẫn nước, các cạnh sẽ là các ống nước và trọng
số sẽ là khả năng chịu tải lượng nước chảy qua tối đa của mỗi ống nước.
Trong phần này ta sẽ làm việc với các đồ thị đơn liên thông có trọng số. Bài toán
tìm cây bao trùm nhỏ nhất là bài toán tìm một cây bao trùm của một đồ thị đơn liên
thông có trọng số sao cho tổng trọng số các cạnh trong cây bao trùm đó là nhỏ nhất
Ví dụ 2.4. Một đồ thị có trọng số

Hình 2.6: Độ dài đường đi giữa các thành phố (Nevada)
Ví dụ 2.5. Một đồ thị có trọng số với một cây bao trùm nhỏ nhất của nó

Hình 2.7: Cây bao trùm nhỏ nhất


3. Một số thuật toán tìm cây bao trùm nhỏ nhất

3

10

Một số thuật toán tìm cây bao trùm nhỏ nhất

Trong phần này, chúng ta sẽ tìm hiểu về hai thuật toán để tìm cây bao trùm nhỏ
nhất của một đồ thị đơn liên thông có trọng số.
Thuật toán thứ nhất chúng ta sẽ đề cập tới trong phần này là thuật toán Kruskal,
được đặt cùng tên với nhà toán học người Mĩ Joseph B. Kruskal Jr., người đã phát
hiện ra thuật toán này vào năm 1956.
Thuật toán thứ hai được phát hiện ra đầu tiên bởi nhà toán học người Cộng hòa

Séc Vojtˇech Jarník năm 1930. Thuật toán này về sau được phát hiện lại bởi Robert C.
Prim vào năm 1957 và Edsger W. Dijkstra vào năm 1959. Thuật toán này thường được
biết đến là thuật toán Prim (hay đôi khi là thuật toán Jarník, thuật toán Prim-Jarník,
thuật toán Prim-Dijkstra hay thuật toán DJP).

3.1

Thuật toán Kruskal

Ta sẽ mô tả thuật toán Kruskal
Đầu vào Đồ thị G = (V, E, l ) với V là tập đỉnh, E là tập cạnh, l : E → R là hàm trọng
số.
Quá trình T := cạnh có trọng số nhỏ nhất. Thực hiện liên tục n − 2 lần quá trình
sau: chọn e là một cạnh có trọng số nhỏ nhất sao cho nó không nằm trong T và
không tạo thành chu trình nếu thêm vào T. T := T thêm vào e
Đầu ra T sẽ là cây bao trùm nhỏ nhất của G

Hình 3.1: Thuật toán Kruskal


3.1

Thuật toán Kruskal

11

Ta sẽ viết chương trình cho thuật toán Kruskal như sau:
> with(networks):
Kruskals_MST := module()
option package;

export Kruskals_Algorithm;
Kruskals_Algorithm := proc (network_def::list, make_graph::truefalse)
local edgelist :: list, edge :: list, cmp_weights, mst :: set,
mst_edges :: posint, i :: posint, vertices :: set, vertex,
vertex_count :: posint, C :: table, rep_target, rep_value, G,
tot_cost :: posint;
# Obtain list of edges sorted by weight
cmp_weights := proc(a,b) return ( is(a[3] < b[3]) ) end proc:
edgelist := sort(network_def, cmp_weights);
# Obtain list of vertices
vertices := {}:
for edge in edgelist do vertices := vertices union { edge[1], edge[2] } end do:
vertex_count := nops(vertices);
mst_edges := vertex_count - 1; # number of edges in MST = vertices - 1
# Initialize cycle-detecting table
C := table;
for vertex in vertices do C[vertex] := vertex end do;
# printf("vertex_count = %d, edges = %d\n", vertex_count, nops(edgelist));
# Generate MST
mst := {};
for i to nops(edgelist) while (nops(mst) < mst_edges) do;
edge := edgelist[i]:
if (C[edge[1]] <> C[edge[2]]) then
mst := mst union { edge };
rep_target := C[edge[2]];
rep_value := C[edge[1]];
for vertex in vertices do;
if (C[vertex]=rep_target) then
C[vertex] := rep_value
end if;

end do;
end if;
end do:


3.1

Thuật toán Kruskal

12

# Sanity check
if (nops(mst) <> mst_edges) then
printf("*** Did not construct MST, %d <> %d ***\n",
nops(mst), mst_edges);
printf("*** Error in input? Not connected graph? ***\n");
return;
end if;
# At this point, shortest paths for graph is determined.
printf("\nMinimum Spanning Tree:\n\n");
tot_cost := 0;
for edge in mst do;
printf ("%A - %A (%d)\n", edge[1], edge[2], edge[3]);
tot_cost := tot_cost + edge[3];
end;
printf("Total cost = %d\n", tot_cost);
printf("\n");
# create graph G if requested
if (make_graph) then
new(G):

addvertex([seq(vertices[i],i=1..nops(vertices))],G);
for edge in mst do connect({edge[1]},{edge[2]},G) end do;
return(draw(G));
end if;
return mst;
end proc: # Kruskals_Algorithm
end module: # Kruskals_MST
with(Kruskals_MST);
Ví dụ áp dụng thuật toán.
Ví dụ 3.1.
>net := [
[1, 2, 1], # arc 1 - from 1 to 2, cost=1
[1, 3, 3],[2, 3, 2],[3, 2, 4],[2, 4, 5],[3, 4, 9]
]:
Kruskals_Algorithm(net, false); # dont display graph
Minimum Spanning Tree:


3.1

Thuật toán Kruskal

13

1 - 2 (1)
2 - 3 (2)
2 - 4 (5)
Total cost = 8
{[1, 2, 1], [2, 3, 2], [2, 4, 5]}
Một ví dụ phức tạp hơn, và cho hình ảnh cây bao trùm

Ví dụ 3.2.
># More complex network, show resulting graph
net := [
[1,2,5], # arc from 1 to 2, cost 5
[1,3,9],[1,4,20],[1,5,4],[1,8,14],[1,9,15],
[2,1,5],[2,3,6],[3,1,9],[3,2,6],[3,4,15],
[3,5,10],[4,1,20],[4,3,15],[4,5,20],[4,6,7],
[4,7,12],[5,1,4],[5,3,10],[5,4,20],[5,6,3],
[5,7,5],[5,8,13],[5,9,6],[6,4,7],[6,5,3],
[7,4,12],[7,5,5],[7,8,7],[8,1,14],[8,5,13],
[8,7,7],[8,9,5],[9,1,15],[9,5,6],[9,8,5]
]:
Kruskals_Algorithm(net, true);

Minimum Spanning Tree:
2 - 1 (5)
3 - 2 (6)
5 - 1 (4)
6 - 4 (7)
6 - 5 (3)
7 - 5 (5)
9 - 5 (6)
9 - 8 (5)
Total cost = 41


3.1

Thuật toán Kruskal


Ví dụ 3.3. ># Network with city name labels
net := [["Omaha","Chicago",5],
["Omaha","St Louis",6],
["St Louis","Chicago",5],
["St Louis","Cincinatti",6],
["Chicago","Boston",11],
["Chicago","New York",9],
["Chicago","Pittsburgh",7],
["Chicago","Cincinatti",5],
["Chicago","Memphis",6],
["Boston","New York",3],
["New York","Pittsburgh",5],
["New York","Washington DC",5],
["Pittsburgh","Washington DC",5],
["Pittsburgh","Atlanta",7],
["Pittsburgh","Cincinatti",4],
["Washington DC","Cincinatti",6],
["Washington DC","Atlanta",4],
["Washington DC","Miami",8],
["Cincinatti","Atlanta",6],
["Cincinatti","Memphis",6],
["Memphis","Atlanta",7],
["Memphis","New Orleans",4],
["New Orleans","Atlanta",6],
["Atlanta","Miami",6]]:
Kruskals_Algorithm(net,true);

14



3.2

Thuật toán Prim

15

Minimum Spanning Tree:
Omaha - Chicago (5)
St Louis - Chicago (5)
Chicago - Cincinatti (5)
Boston - New York (3)
New York - Washington DC (5)
Pittsburgh - Washington DC (5)
Pittsburgh - Cincinatti (4)
Washington DC - Atlanta (4)
Memphis - New Orleans (4)
New Orleans - Atlanta (6)
Atlanta - Miami (6)
Total cost = 52

3.2

Thuật toán Prim

Ta sẽ mô tả thuật toán Prim
Đầu vào Đồ thị G = (V, E, l ) với V là tập đỉnh, E là tập cạnh, l : E → R là hàm trọng
số


3.2


Thuật toán Prim

16

Quá trình T := đỉnh bất kỳ. Thực hiện n − 1 lần quá trình sau: Chọn e là cạnh có
trọng số nhỏ nhất thỏa mãn e có chung đỉnh với một đỉnh của T và thêm e vào
T sẽ không tạo thành chu trình. Khi đó T := T thêm vào e
Đầu ra T sẽ là cây bao trùm nhỏ nhất của G

Hình 3.2: Thuật toán Prim
Ta sẽ viết chương trình cho thuật toán Prim như sau:
>restart:
with(GraphTheory):
PrimMST := module()
option package;


3.2

Thuật toán Prim

export Prim;
Prim := proc (G::Graph, stepByStep::truefalse := false,
draw::truefalse := true, initial := {})
local H :: list, V :: set, E :: set, e :: list, g::Graph ,
a::list, discarded::set, initVert::set,total::int,
uncheckedVerts::int:
#variable initialization
H:={}: #List of edges of the MST

E:=Edges(G,weights): #backup of G’s edge list, used in
destructive operations
uncheckedVerts:=nops(Vertices(G))-1: #number of G’s vertices
not yet reached by the MST
>
if initial <> {} then #determines initial vertex
if initial in Vertices(G) then
V:={initial}: #user-inputted initial vertex
else
printf("ERROR: initial vertex not in graph");
return "ERROR": #invalid initial vertex
end if:
else
V:={E[1][1][1]}: #default initial vertex
end if:
if draw and stepByStep then
printf("key: yellow = vertices, magenta = initial vertex, blue
= original graph edges,\n\tgreen = MST edges, red = discarded
edges.\n");
discarded:={}: #discarded edge set, used only when drawing
the graph
initVert:=V: #initial vertex backup, used only when drawing
the graph
end if:
total:=0: #total weight of the edges in the MST
while nops(E)>0 do; #continue while there are unprocessed
edges
e:={}: #assume no edge is added to the MST
for a in E do: #for each edge
if a[1][1] in V then

if a[1][2] in V then
E:=E minus {a}: #if it would cause a loop in the MST,
discard the edge
if stepByStep then #report discarded edge if the option is
enabled
printf("discarded edge (%a,%a) as it would cause a loop\n",
a[1][1], a[1][2]):
if draw then #draw resulting graph if the option is
enabled

17


3.2

Thuật toán Prim

discarded:=discarded union {a}:
g:=Graph([op(V)], discarded):
HighlightSubgraph(G, g, red, yellow):
HighlightVertex(G,initVert,magenta):
print(DrawGraph(G));
>
end if:
end if:
else
if e={} or a[2]minimum weight edge
e:=a:
end if:

end if:
else
if a[1][2] in V and (e={} or a[2]e:=a:
end if:
end if:
end do:
if e<>{} then #if an edge of the MST was found, add it to the
MST
V:=V union {e[1][1], e[1][2]}:
H:=H union {e}:
E:=E minus {e}:
total:= total+e[2]:
uncheckedVerts:=uncheckedVerts-1:
if stepByStep then #report added edge if the option is
enabled
printf("added edge (%a,%a) with weight %a to the MST\n", e[1]
[1], e[1][2], e[2]):
if draw then #draw resulting graph if the option is enabled
g:=Graph([op(V)], H):
HighlightSubgraph(G, g, green, yellow):
HighlightVertex(G,initVert,magenta):
print(DrawGraph(G));
end if:
end if:
if uncheckedVerts=0 then #algorithm ends when all vertices
are in the MST
if stepByStep then #report end of computation if the option
is enabled
printf("Finished MST construction.\n"):

break:
end if:
end if:
else

18


3.2

Thuật toán Prim

if(E<>{})then #if there are unprocessed edges, but none of
>
>
them belongs to the MST, report an error
printf("ERROR: unable to construct MST, graph may be
disconnected");
return "ERROR":
end if:
end if:
end do:
if (draw) then #print MST if the option is enabled
g:=Graph([op(V)],H):
if stepByStep then
printf("graph for the obtained MST:\n", a[1][1], a[1][2]):
end if:
print(DrawGraph(g));
printf("total weight of the MST: %a\n",total): #report total
MST weight

return g: #return graph for the MST
else
printf("total weight of the MST: %a\n",total): #report total
MST weight
return H; #return list of edges for the MST
end if:
end proc:
end module:
with (PrimMST);
Ví dụ áp dụng thuật toán
Ví dụ 3.4 (In cây bao trùm, không làm từng bước).
>vertices:=["a","b","c","d"]:
edges:={[{"a", "b"}, 1],[{"a", "c"}, 3],[{"b", "c"}, 2],[
{"b", "d"}, 5],[{"c", "d"}, 9]}:
g := Graph(vertices,edges):
Prim(g);

19


3.2

Thuật toán Prim

Ví dụ 3.5 (làm từng bước, nhưng không in cây bao trùm).
vertices:=[1,2,3,4,5,6]:
edges:={[{1,2},6],[{1,3},2],[{1,4},5],[{2,3},6],[{2,4},4],[
{2,5},5],[{3,4},6],[{3,5},3],[{3,6},2],[{4,5},6],[{5,6},2]}:
g := Graph(vertices,edges):
Prim(g,true,false);

added edge (1,3) with weight 2 to the MST
added edge (3,6) with weight 2 to the MST
added edge (5,6) with weight 2 to the MST
discarded edge (3,5) as it would cause a loop
added edge (1,4) with weight 5 to the MST
discarded edge (3,4) as it would cause a loop
discarded edge (4,5) as it would cause a loop
added edge (2,4) with weight 4 to the MST
>
(4.2.1)
>
Finished MST construction.
total weight of the MST: 15
{[{1,3},2],[{1,4},5],[{2,4},4],[{3,6},2],[{5,6},2]}

20


TÀI LIỆU

21

Tài liệu
[1] Nguyễn Hữu Điển, Thực hành tính toán trong Maple, NXBĐHQGHN, 2015.
[2] Nguyễn Hữu Điển và Nguyễn Minh Tuấn, LATEX- Tra cứu và soạn thảo,
NXBĐHQGHN, 2001
[3] Nguyễn Hữu Điển, LATEX- Với gói lệnh và phần mềm công cụ, NXBĐHQGHN, 2004.
[4] Kenneth H. Rosen, Discrete Mathematics and Its Application, 7th ed., McGraw-Hill
Higher Education, 2012.

[5] Thomas H. Cormen, Charles E. Leiserton, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 2nd ed., The MIT Press, 2001.
[6] />[7] />