ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐÀO TẠO THẠC SĨ CNTT
BÁO CÁO CHUYÊN ĐỀ : LẬP TRÌNH SYMBOLIC
SỬ DỤNG MAPLE GIẢI MỘT SỐ BÀI
TOÁN VỀ LÝ THUYẾT ĐỒ THỊ
• CHU TRÌNH EULER
• TÔ MÀU ĐỒ THỊ (GRAPH COLORING)
• CÂY KHUNG NHỎ NHẤT (PRIM, KRUSKAL)
Konigsberg’s Problem
ĐẠI HỌC QUỐC GIA TPHCM CHƯƠNG TRÌNH THẠC SĨ CNTT
HV : VŨ MINH THÀNH
MS : CH1101134
Lớp : Cao học khóa 6
Email :

GVHD : GS-TS ĐỖ VĂN
NHƠN
2
ĐẠI HỌC QUỐC GIA TPHCM CHƯƠNG TRÌNH THẠC SĨ CNTT
Lời Mở Đầu
Ngày nay, ngành công nghệ thông tin trên thế giới đang trên đà phát triển mạnh mẽ, và
ngày càng ứng dụng vào nhiều lĩnh vực: kinh tế, khoa học kĩ thuật, quân sự, y tế, giáo
dục… và nó đã đáp ứng ngày càng nhiều yêu cầu của các lĩnh vực này, để phục vụ cho
nhu cầu của con người. Ở nước ta, hòa nhập chung với sự phát triển ngành công nghệ
thông tin và ứng dụng vào các lĩnh vực của cuộc sống nhằm phục vụ các nhu cầu như:
nghiên cứu, học tập, lao động và giải trí… của con người. Nhà nước ta đã có những
chính sách cần thiết để đưa ngành công nghệ thông tin vào vị trí then chốt trong chiến
lược phát triển kinh tế của Đất nước.
Ứng dụng CNTT đóng vai trò quan trọng trong giáo dục, môn học Lập trình Symbolic
nói chung và Maple nói riêng là một môn học khá hay và thú vị. Qua môn học sinh động
này do thầy Nhơn phụ trách, ta có thể thấy rõ Maple là một thư viện và công cụ toán


m a

p l

e s

o f

t .c

om ). Maple ra
đời
năm
1991
đến nay đã phát
triển
đến phiên
bản
15. Maple có cách cài
đặt
đơn
giản,
chạy được
trên
nhiều hệ điều
hành, có
cấu
trúc linh
hoạt để sử

cho
nhiều người
trên
thế giới lựa
chọn
sử
dụng Maple cùng
các
phần mềm
toán học
khác áp dụng
trong
dạy
học toán và các công việc tính toán
đòi hỏi của
thực tiễn
và
sự
phát
triển
của giáo dục.
C ó t h ể
nhận thấy rằng
ngoài
các
tính
năng
tính toán và minh
hoạ rất mạnh
mẽ bằng

sẽ tự
động
thực hiện
các
lệnh
có
trong
thủ tục đó một cách
tuần
tự
và sau đó
trả lại kết quả
cuối
cùng.
Mapple có các chức năng cơ bản sau:
• Là một hệ thống tính toán trên các biểu thức đại số.
• Có thể thực hiện được hầu hết các phép toán cơ bản trong chương trình
toán đại học và sau đại học.
• Cung cấp các công cụ minh họa hình học thuận tiện gồm: vẽ đồ thị động
và tĩnh của các đường và mặt được cho bởi các hàm tùy ý và trong các
hệ tọa độ khác nhau.
• Là một ngôn ngữ lập trình đơn giản và mạnh mẽ, có khả năng tương tác
với các ngôn ngữ lập trình khác.
• Cho phép trích xuất ra các định dạng khác nhau như word, HTML…
• Một công 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.
• Một trợ giáo hữu ích cho học sinh sinh viên trong việc tự học.
5
ĐẠI HỌC QUỐC GIA TPHCM CHƯƠNG TRÌNH THẠC SĨ CNTT
2. PHẦN 2 : SỬ DỤNG MAPLE GIẢI MỘT SỐ BÀI TOÁN LÝ THUYẾT

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.
Trong trường hợp giữa hai máy tính nào đó thường xuyên phải truyền tải nhiều thông tin người
ta phải nối hai máy nàu bởi nhiều kênh thoại. Mạng với đa kênh thoại giữa các máy được cho
trong hình 2.
Trong trường hợp giữa hai máy tính nào đó thường xuyên phải truyền tải nhiều thông tin người
ta phải nối hai máy nàu bởi nhiều kênh thoại. Mạng với đa kênh thoại giữa các máy được cho
trong hình 2.
Hình 2. Sơ đồ mạng máy tính với đa kênh thoại.
• Định nghĩa 2 : Đa đồ thị vô hướng G= (V, E) bao gồm V là tập các đỉnh, và E là tậ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. Hai cạnh e1 và
e2 được gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh.
7
ĐẠI HỌC QUỐC GIA TPHCM CHƯƠNG TRÌNH THẠC SĨ CNTT
Hình 3. Sơ đồ mạng máy tính với kênh thoại thông báo.
Rõ ràng mỗi đơn đồ thị đều là đa đồ thị, nhưng không phải đa đồ thị nào cũng là đơn đồ thị, vì
trong đa đồ thị có thể có hai (hoặc nhiều hơn) cạnh nối một cặp đỉnh nào đó.
Trong mạng máy tính có thể có những kênh thoại nối một náy nào đó với chính nó (chẳng hạn
vời mục đính thông báo). Mạng như vậy được cho trong hình 3. Khi đó đa đồ thị không thể mô
tả được mạng như vậy, bởi vì có những khuyên (cạnh nối một đỉnh với chính nó). Trong 3
trường hợp nàychúng ta cần sử dụng đến khái niệm giả đồ thị vô hướng, được định nghĩa như
sau:
• Định nghĩa 3 : Giả đồ thị vô hướng G = (V, E) bao gồm V là tập các đỉnh và E là tập các
cặp không có thứ tự gồm hai phần tử (không nhất thiết phải khác nhau) của V gọi là
cạnh. Cạnh e được gọi là khuyên nếu nó có dạng e = (u, u).
Hình 4. Mạng máy tính với kênh thoại một chiều
8
ĐẠI HỌC QUỐC GIA TPHCM CHƯƠNG TRÌNH THẠC SĨ CNTT
Các kênh thoại trong mạng máy tính có thể chỉ cho phép truyền tin theo một chiều. Chẳng hạn,
trong hình 4 máy chủ ở Hà Nội chỉ có thể nhận tin từ các máy ở địa phương, có một số máy chỉ
có thể gửi tin đi, còn các kênh thoại cho phép truyền tin theo cả hai chiều được thay thế bởi hai

Konigsberg và đây là định lý đầu tiên của lý thuyết đồ thị.
Định lý 1 (Euler). Đồ thị vô hướng liên thông G là đồ thị Euler khi và chỉ khi mọi đỉnh
của G đều có bậc chẵn.
1.2.2 Giải tìm chu trình Euler bằng Maple
11
ĐẠI HỌC QUỐC GIA TPHCM CHƯƠNG TRÌNH THẠC SĨ CNTT
Mặc dù Maple đã trang bị sẵn hàm IsEulerian để kiểm tra xem một đồ thị có chu trình
Euler hay không, nhưng hàm này chỉ áp dụng cho các đồ thị đơn giản (không vòng hay
đa cạnh). Ta sẽ đi xây dựng hàm kiểm tra chu trình Euler cho đa đồ thị (multigraphs).
Sourcecode trong đường dẫn ở đĩa CD :
\Sourcecode\Euler.mw
Ta đi xây dựng 1 số hàm con phụ trợ
Giả đồ thị (Pseudograph) : là đồ thị vô hướng, có vòng và đa cạnh.
12
ĐẠI HỌC QUỐC GIA TPHCM CHƯƠNG TRÌNH THẠC SĨ CNTT
• Hàm tính bậc của 1 đỉnh cho đồ thị bất kỳ (vô hướng, có vòng và đa cạnh)
Để tính bậc của 1 đỉnh, đầu tiên ta kiểm tra xem đồ thị có trọng số hay không sử dụng lệnh
IsWeighted. Nếu không có trọng số, dùng hàm Degree. Nếu có trọng số, ta sử dụng lệnh
IncidentEdgesđể xác định các cạnh kề với đỉnh cho trước. Lệnh add thêm trọng số, sau đó ta chỉ
việc kiểm tra xem có loop hay không, nếu có thì cộng 2 vào bậc của đỉnh. Hàm này được sử
dụng để tính chu trình Euler bên dưới.
> PseudoDegree := proc(G::Graph, v)
local E, e, d;
uses GraphTheory;
if IsWeighted(G) then
d := add(GetEdgeWeight(G,e),e in IncidentEdges(G,v));
else
d := Degree(G,v);
end if;
if GetVertexAttribute(G,v,"loop") then

> Konigsberg := Graph({[{"A","B"},2], [{"A","C"},2],
{"A","D"}, {"B","D"}, {"C","D"}});
> SetVertexPositions(Konigsberg,[[0,1],[0,0],[0,2],[1,1]]);
14
ĐẠI HỌC QUỐC GIA TPHCM CHƯƠNG TRÌNH THẠC SĨ CNTT
> DrawPseudograph(Konigsberg);
> IsPseudoEulerian(Konigsberg);
Kiểm tra lại bằng hàm của Maple có sẵn IsEulerian
>
Hàm chính tìm chu trình Euler của 1 đa đồ thị
> FindMultiEuler := proc(G::Graph)
local H, circuit, subC, i, v, insertPoint, e, w,
buildingSub, oldC;
uses GraphTheory;
if not IsPseudoEulerian(G) then
return false;
end if;
H := CopyGraph(G);
15
ĐẠI HỌC QUỐC GIA TPHCM CHƯƠNG TRÌNH THẠC SĨ CNTT
circuit := [];
while Edges(H) <> {} do
# find a starting point
if circuit = [] then
subC := [Vertices(H)[1]];
else
for i from 1 to nops(circuit) do
if Neighbors(H,circuit[i]) <> [] then
subC := [circuit[i]];
insertPoint := i;

oldC := circuit;
circuit := [];
if insertPoint >= 2 then
circuit := oldC[1 (insertPoint-1)];
end if;
circuit := [op(circuit),op(subC)];
if insertPoint < nops(oldC) then
circuit:=[op(circuit),op(oldC[(insertPoint+1) 1])];
end if;
end if;
end do;
return circuit;
end proc:
Giải thích thuật toán
17
ĐẠI HỌC QUỐC GIA TPHCM CHƯƠNG TRÌNH THẠC SĨ CNTT
Chương trình bắt đầu với việc dùng hàm IsPseudoEulerianđể tránh tìm kiếm chu trình
mà không tồn tại trong đồ thị. Sau đó ta gán đồ thị cho 1 biến H. Ta dùng biến H này để
lưu giữ đồ thị cần xử lý sau này.
Có 2 ý chính trong giải thuật này. Một là, đối với 1 đồ thị mà đỉnh đều có bậc chẵn, nếu
ta lấy bất kỳ đỉnh nào để bắt đầu và đi theo cạnh ngẫu nhiên nhưng không lặp lại, ta sẽ
quay về đỉnh ban đầu và tạo nên 1 chu trình. Ý thứ 2 là đối với đồ thị liên thông, nếu
chu trình của ta không bao gồm tất cả các cạnh của đồ thị, thì vài đỉnh được sử dụng
trong chu trình có sẵn có thể được dùng làm điểm khởi đầu cho 1 chu trình con mới.
Chu trình con mới này sau đó có thể được ghép vào trong chu trình chính. Việc này
cuối cùng sẽ dẫn đến việc sử dụng tất cả các cạnh và kết quả ta được chu trình Euler.
Biến circuit lưu giữ kết quả chu trình Euler và trả về kết quả cần tìm, nó chứa list các
đỉnh mà chu trình đi qua nó và ban đầu khởi tạo là rỗng. Vòng While chính gồm 3
phần : (1) xác định điểm bắt đầu của chu trình con (gọi là subC); (2) xây dựng chu trình
con; (3) ghép chu trình con vào chu trình chính.

> Test := Graph({{"a","b"},[{"a","e"},3],{"b","c"},{"b","d"},
{"b","e"},[{"c","d"},2],{"c","e"},{"d","e"}});
> SetVertexPositions(Test,[[0,2],[1,2],[2,.5],[1,1],[0,1]]);
> DrawPseudograph(Test);
19
ĐẠI HỌC QUỐC GIA TPHCM CHƯƠNG TRÌNH THẠC SĨ CNTT
> TestPath := FindMultiEuler(Test);
20
ĐẠI HỌC QUỐC GIA TPHCM CHƯƠNG TRÌNH THẠC SĨ CNTT
1.3 BÀI TOÁN TÔ MÀU ĐỒ THỊ (GRAPH COLORING)
1.3.1 Giới thiệu bài toán tô màu đồ thị
Vấn đề liên quan đến tô màu các miền trên bản đồ, ví dụ bản đồ các vùng trên thế giới
đã dẫn đến nhiều kết quả trong lí thuyết đồ thị. Khi tô màu bản đồ, ta thường tô 2 miền
có chung đường biên giới bằng 2 màu khác nhau. Để đảm bảo điều này, ta có thể sử
dụng màu sắc riêng cho mỗi miền. Tuy nhiên, cách làm này là không hiệu quả, và nếu
bản đồ có quá nhiều miền, sẽ rất khó để phân biệt giữa các miền có màu sắc gần giống
nhau. Do đó, ta nên sử dụng số màu ít nhất có thể được. Nó dẫn đến bài toán xác định
số màu tối thiểu cần sử dụng để tô màu các miền bản đồ sao cho các miền lân cận luôn
khác màu nhau.
VD: Bản đồ H1a có thể tô được bằng 4 màu, nhưng không thể tô bằng 3 màu -> Số màu tối
thiểu phải là 4.
Bản đồ H1b có thể tô bằng 3 màu,nhưng 2 màu là không thể ->Số màu tối thiểu là 3.
Mỗi bản đồ trên mặt phẳng có thể biểu diễn bằng đồ thị: Mỗi miền biểu diễn bằng 1 đỉnh; 2 đỉnh
sẽ được nối với nhau khi 2 miền tương ứng có chung đường biên giới. Hai miền chỉ tiếp xúc
nhau tại 1 điểm coi như không kề nhau. Đồ thị này được gọi là đồ thị kép của bản đồ. Từ
phương pháp xây dựng đồ thị kép của 1 bản đồ, dễ thấy mỗi bản đồ phẳng sẽ tương ứng với 1
đồ thị kép phẳng .
H2 thể hiện đồ thị phẳng tương ứng của các bản đồ trong H1.
21
ĐẠI HỌC QUỐC GIA TPHCM CHƯƠNG TRÌNH THẠC SĨ CNTT

sử dụng máy tính để thực hiện các thao tác chính. Ví dụ, chương trình máy tính có thể
mắc lỗi dẫn đến kết quả sai. Liệu lí lẽ của họ có thật sự là 1 chứng minh khi phụ thuộc
vào những kết quả không đáng tin cậy của máy tính?
Định lí 4 màu chỉ ứng dụng trên đồ thị phẳng. Đồ thị không phẳng có thể có số màu lớn hơn 4.
2 điều kiện được yêu cầu để xác định số màu của 1 đồ thị là n: Đầu tiên,phải chứng
minh đồ thị có thể tô bằng n màu.Việc này có thể thực hiện bằng cách xây dựng, như tô
màu. Thứ 2, chúng ta phải chỉ ra rằng đồ thị không thể tô bằng số màu ít hơn n. Các ví
dụ sau điển hình cho cách tìm số màu đồ thị.
23
ĐẠI HỌC QUỐC GIA TPHCM CHƯƠNG TRÌNH THẠC SĨ CNTT
Một số ví dụ
24
ĐẠI HỌC QUỐC GIA TPHCM CHƯƠNG TRÌNH THẠC SĨ CNTT
Tô màu các đồ thị đầy đủ K
n
Ta có thể tô màu n đỉnh của K
n
bằng n màu riêng biệt. Liệu có cách tô nào tiết kiệm màu
hơn không? Câu trả lời là không.
Thật vậy, không có 2 đỉnh nào có thể tô cùng màu vì mọi đỉnh đều kề nhau. Vậy, ta có c(Kn) = n
(Chú ý: Kn không phải đồ thị phẳng khi n ≥ 5, do đó kết quả này không vi phạm định lí 4 màu).
H5 cho ta ví dụ về việc tô màu K5.
Tô màu các đồ thị vòng C
n
Ví dụ tô màu với n = 6 và n =5
25