MỤC LỤC
1
DÙNG MAPLE GIẢI
MỘT SỐ BÀI TOÁN CƠ BẢN VỀ ĐỐ THỊ
MỞ ĐẦU:
Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu và có nhiều ứng
dụng trong ngành công nghệ thông tin. Những tư tưởng cơ bản của lý thuyết đồ
thị được đề xuất vào những năm đầu của thế kỷ 18 bởi nhà toán học lỗi lạc người
Thụy Sỹ: Leonhard Euler. Chính ông là người đã sử dụng đồ thị để giải bài toán
nổi tiếng về 7 cái cầu ở thành phố Konigberg.
Những ứng dụng cơ bản của đồ thị như:
- Xác định tính liên thông trong một mạng máy tính: hai máy tính nào đó có
thể truyền dữ liệu cho nhau được không.
- Tìm đường đi ngắn nhất trên mạng giao thông
- Giải các bài toán tối ưu: lập lịch, phân bố tần số cho các trạm phát thanh,
truyền hình.
- Giải bài toán tô màu trên bản đồ: tìm số màu ít nhất để tô các quốc gia sao
cho hai quốc gia kề nhau phải được tô khác màu.
- …
1. Giới thiệu mapple – công cụ lập trình symbolic
Maple là một hệ thống tính toán trên các biểu thức đại số và minh hoạ toán
học mạnh mẽ của công ty Warterloo Maple Inc. ().
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ử dụng
tối ưu cấu hình máy và có trình trợ giúp (help) rất dễ sử dụng. Từ phiên bản 7,
Maple cung cấp ngày 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 học phổ thông và đại học. Ưu điểm đó làm 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ó thể 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

| for <name> | | in < bieu_thuc > | | while < bieu_thuc > |
do < cac_cau_lenh > end do;
• Thủ tục:
3
proc (danh_sach_tham_so)
local ds_bien_cuc_bo;
global ds_bientoancuc; #neu co
options ds_cac_bien_tuy_chon;
description Chuoi_mo_ta_thu_tuc;
end proc:
2. Chương trình:
> DOTHI:=module()
local ModuleLoad,index,dangchuyendoi;
export taodothi, ladothivohuong, ladothicohuong, loaidothi, dinh, sodinh,
canh, socanh, themcanh, xoacanh, themdinh, xoadinh, timdinhke, timduongdi,
lienthong, tplienthong, caybaotrum, timchutrinh, baccuadinh, lacau,
timchutrinhEuler, vedothi;
global `type/Dinh`, `type/Canh`, `type/Dothi`;
options package;
=============================
ModuleLoad:=proc()
global `type/Dinh`,`type/Canh`,`type/Dothi`;
`type/Dinh`:={integer,name};
`type/Canh`:=proc(c)
if type(c,{list(Dinh),set(Dinh)})= false then return false;
end if;
if nops(c)<>2 or op(1,c) = op(2,c) then
return false;
end if;
return true;

==============================
# Thủ tục tạo đồ thị:
taodothi:=proc(G)
local i,huong,H,tapdinh,tapcanh;
if type(G,Dothi)=false then
return "DoThi_KhongDung";
5
end if;
if type(G[1],Dinh) then
tapdinh:={G[1]};
else
tapdinh:=G[1];
end if;
if type(G[2],Canh) then
tapcanh:={G[2]};
else
tapcanh:=G[2];
end if;
huong:=false;
H:=[tapdinh,tapcanh];
for i in tapcanh do
if type(i,list) then huong:=true;break; end if;
end do;
if huong=true then
for i in tapcanh do
if type(i,set) then
H:=[tapdinh,{op(tapcanh minus{i}), [op(1,i),
op(2,i)],[op(2,i), op(1,i)]}];
end if;
end do;

new:=[op(new),i];
end if;
break;
end if;
end do;
for i from 1 to n do
if index[i]=op(2,c) then
if ladothivohuong(G) then new:={op(new),i}; else
new:=[op(new),i];
end if;
break;
end if;
7
end do;
tapcanh:={op(tapcanh),new};
end do;
return taodothi([{seq(k,k=1 n)},tapcanh]);
return D;
end proc;
# Thủ tục xác định có là đô thị có hướng không
ladothicohuong:=proc(G::Dothi)
local i;
for i in canh(G) do
if type(i,list) then
return true;
end if;
end do;
return false;
end proc;
# Thủ tục xác định có là đô thị vô hướng không

tapdinh:=dinh(G);
if type(tapcanh,Canh) then
for i in tapcanh do
if member(i,tapdinh)=false then
tapdinh:={op(tapdinh),i};
end if;
end do;
return taodothi([tapdinh,{op(canh(G)),tapcanh}]);
9
end if;
for c in tapcanh do
for i in c do
if member(i,tapdinh)=false then
tapdinh:={op(tapdinh),i}; end if;
end do;
end do;
return taodothi([tapdinh,{op(canh(G)),op(tapcanh)}]);
end proc;
# Thủ tục xóa cạnh trong đồ thị
xoacanh:=proc(G::Dothi,tapcanh)
local tc,i,j,tapcanhbandau;
if type(tapcanh,Canh)=false and
type(tapcanh,set(Canh))=false then
print("Canh can xoa khong hop le."); return G; end if;
if type(tapcanh,Canh) then
tc:={tapcanh};
else
tc:=tapcanh;
end if;
if ladothicohuong(G) then

print("Dinh can xoa khong hop le"); return G;
end if;
if type(d,Dinh) then tapdinh:={d}; else tapdinh:=d; end if;
D:=G;
for i in tapdinh do
for j in canh(D) do
if op(1,j)=i or op(2,j)=i then D:=xoacanh(D,j); end if;
end do;
D:=[dinh(D) minus {i},canh(D)];
end do;
return D;
11
end proc;
# Thủ tục xác định đỉnh kề
timdinhke:=proc(G::Dothi,dinh)
local i,ketqua;
ketqua:={};
for i in canh(G) do
if i[1]=dinh then ketqua:={op(ketqua),i[2]};end if;
if type(i,set) then if i[2]=dinh then
ketqua:={op(ketqua),i[1]}; end if; end if;
end do;
return ketqua;
end proc;
# Thủ tục từ đỉnh d tới đỉnh c
timduongdi:=proc(G::Dothi,d,c)
local chuanbi, daduyet, tapdinh,i,j, duongdi, dinh, dinhke, timduoc,
ketqua, kq, t, n, D, index, dau, cuoi;
D:=dangchuyendoi(G);
n:=sodinh(D);

for i in dinhke do duongdi[i]:=dinh;end do;
chuanbi:=chuanbi union dinhke;
end do;
if type(ketqua,list) then
kq:=[];
for i in ketqua do kq:=[op(kq),index[i]]; end do;
return kq;
end if;
return [];
end proc;
# Thủ tục xác định liên thông trong đồ thị
lienthong:=proc(G::Dothi)
local i,j;
for i in dinh(G) do
for j in dinh(G) do
13
if timduongdi(G,i,j)=[] then
return false;
end if;
end do;
end do;
return true;
end proc;
# Thủ tục xác định thành phần liên thông trong đồ thị
tplienthong:=proc(G::Dothi)
local i,j,H,tapdinh,tapcanh,taplienthong;
if lienthong(G) then printf("Do Thi Lien Thong");
return G;
end if;
H:=dinh(G);

for i in taplienthong do
j:=j+1;
printf("Tp Lien Thong %a",j);
print(i);
end do;
end proc;
# Thủ tục xác định cây bao trùm
caybaotrum:=proc(D::Dothi)
local A,B,T,S,x,Dinhke,i,G,kq;
if lienthong(D)=false then
print("Do Thi ko lien thong, ko ton tai Cay bao trum!");
return {};
end if;
if ladothicohuong(D) then return "Chi tim Cay Bao Trum cho Do Thi Vo
Huong"; end if;
G:=dangchuyendoi(D);
A:={op(1,dinh(G))}; B:=dinh(G) minus A; T:={};
while B<>{} do
S:={};
while A<>{} do
x:=min(op(A));
15
Dinhke:={op(timdinhke(G,x))} intersect B;
if Dinhke <> {} then
for i in Dinhke do
T:={op(T),{x,i}};
B:=B minus Dinhke;
S:=S union Dinhke;
end do;
end if;

if nops(duongdi)>2 and member({i,d},canh(G)) then
return [op(duongdi),d];
end if;
elif member([i,d],canh(G)) then
return [op(duongdi),d];
end if;
end if;
end do;
return [];
end proc;
# Thủ tục xác định bậc của đỉnh
baccuadinh:=proc(G::Dothi,d)
local i,bac;
if member(d,dinh(G))=false then print("Dinh khong thuoc Do Thi"); return
0; end if;
bac:=0;
for i in canh(G) do if op(1,i)=d or op(2,i)=d then bac:=bac+1; end if; end
do;
return bac;
end proc;
# Thủ tục xác định cạnh c có là cầu của đồ thị không
lacau:=proc(G::Dothi,c)
local D;
if type(c,Canh)=false then print("Canh khong hop le");
return false; end if;
if member(c,canh(G))=false then
17
print("Canh khong thuoc Do Thi");
return false;
end if;

if lacau(H,c)=false or baccuadinh(H,d)=1 then
kq:=[op(kq),[d,dnext]];
H:=xoacanh(H,c);
if baccuadinh(H,d)=0 then
H:=xoadinh(H,d);
end if;
d:=dnext;
end if;
end if;
if canh(H)={} then break; end if;
end do;
end do;
return kq;
end proc;
# Thủ tục vẽ đồ thị:
vedothi:=proc(G::Dothi)
if G<>[{},{}] then GraphTheory:-DrawGraph(GraphTheory:-
Graph([op(dinh(G))],canh(G)));
end if;
end proc;
end module:
3. Dữ liệu thử:
Ví dụ 1:
G1:=[{1,2,5,4,3},{{3,2},{4,2},{1,4},{1,5},{4,5},{4,3}}];
> G:=taodothi(G1);
vedothi(G);
loaidothi(G);
19
> lienthong(G);
> timduongdi(G,1,3);

> caybaotrum(G);
Ví dụ 3
G3:=[{a,b,c,d,1},{{b,c},[a,b],[c,a],{1,b}}];
> G:=taodothi(G3); vedothi(G); loaidothi(G);
> G:=xoadinh(G,a): G:=themcanh(G,{[b,d],{c,d}}): vedothi(G);
25