ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA
KHOA CÔNG NGHỆ THÔNG TIN

TIỂU LUẬN
Môn:
TOÁN ỨNG DỤNG
Đề tài:
CÂY STEINER
GVHD: PGS. TS. Trần Quốc Chiến
HVTH: Nguyễn Thanh Trung
Trương Thị Minh Hậu
Lê Quang Vũ
Nguyễn Thị Quỳnh Trang
LỚP : Khoa học máy tính-K24
(T9/2011)
Tiểu luận môn: Toán ứng dụng
MỤC LỤC
LỜI NÓI ĐẦU 2
GIỚI THIỆU 3
1.BÀI TOÁN STEINER TRÊN ĐỒ THỊ 3
2.NHÓM THỰC HIỆN 4
CHƯƠNG I: ĐẠI CƯƠNG VỀ ĐỒ THỊ 5
I.1 Các khái niệm cơ bản 5
I.1.1 Đồ thị, đỉnh, cạnh, cung 5
I.1.2 Bậc, nửa bậc vào, nửa bậc ra 5
I.1.3 Đường đi, chu trình, tính liên thông 6
I.2 Biểu diễn đồ thị 7
I.2.1 Ma trận kề 7
I.2.2 Ma trận liên thuộc 7
CHƯƠNG II: BÀI TOÁN CÂY STEINER 8

Để hoàn thành đề tài này nhóm chúng tôi xin gởi lời cám ơn chân thành đến Thầy giáo
PGS.TS Trần Quốc Chiến đã tận tình hướng dẫn, cung cấp những kiến thức quý báu. Cám ơn
các anh chị học viên lớp Khoa học máy tính K24 đã cung cấp tài liệu, đóng góp ý kiến cho
nhóm. Tuy nhiên trong quá trình làm đề tài nhóm chúng tôi không tránh khỏi những sai sót,
những hạn chế, rất mong nhận được ý kiến, chia sẻ kiến thức của Thầy và các anh chị học viên
để đề tài hoàn thành tốt hơn.
Đà Nẵng, Tháng 04 năm 2012
Các thành viên nhóm
Nguyễn Thanh Trung
Trương Thị Minh Hậu
Lê Quang Vũ
Nguyễn Thị Quỳnh Trang
Nhóm 6 – lớp Khoa học máy tính K24 Trang 2
Tiểu luận môn: Toán ứng dụng
GIỚI THIỆU
1.BÀI TOÁN STEINER TRÊN ĐỒ THỊ
Yêu cầu đề tài như sau:
1. Trình bày bài toán Steiner trên đồ thị.
2. Trình bày thuật toán tìm cây Steiner.
3. Thiết kế cấu trúc dữ liệu và giải thuật tìm cây Steiner.
4. Viết chương trình cài đặt thuật toán tìm cây Steiner bằng ngôn ngữ C.
◊ File dữ liệu đầu vào: GRAPH.INP có cấu trúc
n (số đỉnh)
a
11
a
12
a
1n
(ma trận trọng số)

y
1
z
1
(cạnh thứ 1 của cây phủ)
y
2
z
2
(cạnh thứ 2 của cây phủ)

y
m
z
m
(cạnh thứ m của cây phủ)
+ Trường hợp các đỉnh phủ không liên thông:
NO STEINER TREE
◊ Ví dụ 1:
STEINER.INP STEINER.OUT
7 8
∞ 4 8 4 1 2 ∞ 1 2 5
4 ∞ 2 ∞ 2 ∞ 3 1 5
8 2 ∞ 3 ∞ ∞ 6 1 6
4 ∞ 3 ∞ ∞ 7 ∞ 2 3
1 2 ∞ ∞ ∞ 5 1 2 5
2 ∞ ∞ 7 5 ∞ 5 5 7
∞ 3 6 ∞ 1 5 ∞
3 6 7
◊ Ví dụ 2:

- Cài đặt chương trình
Nhóm 6 – lớp Khoa học máy tính K24 Trang 4
Tiểu luận môn: Toán ứng dụng
CHƯƠNG I: ĐẠI CƯƠNG VỀ ĐỒ THỊ
I.1 Các khái niệm cơ bản
I.1.1 Đồ thị, đỉnh, cạnh, cung
Đồ thị vô hướng G=(V,E) gồm một tập V các đỉnh và tập E các cạnh. Mỗi cạnh e ∈ E
được liên kết với một cặp đỉnh v, w (không kể thứ tự).
Đồ thị có hướng G=(V,E) gồm một tập V các đỉnh và tập E các cạnh có hướng gọi là cung.
Mỗi cung e∈E được liên kế với một cặp đỉnh (v,w) có thứ tự.
Cho đồ thị có hướng G=(V,E). Nếu ta thay mỗi cung của G bằng một cạnh, thì đồ thị vô hướng
nhận được gọi là đồ thị lót của G.
Cho đồ thị ( có hướng hoặc vô hướng) G=(V,E).
Nếu cạnh e liên kết đỉnh v,w thì ta nói cạnh e liên thuộc đỉnh v,w; các đỉnh v,w liên thuộc cạnh
e; các đỉnh v,w gọi là các đỉnh biên của cạnh e và đỉnh v kề đỉnh w.
Đồ thị hữu hạn là đồ thị có bậc và cỡ hữu hạn
Đồ thị đơn là đồ thị không có khuyên và không có cạnh song song.
Đồ thị vô hướng đủ là đồ thị mà mọi cặp đỉnh kề đều nhau.
Đồ thị có hướng đủ là đồ thị có đồ thị lót đủ.
I.1.2 Bậc, nửa bậc vào, nửa bậc ra
Cho đồ thị G=(V,E).
Bậc của đỉnh v∈ V là tổng số cạnh liên thuộc với nó và ký hiệu là d(v). Nếu đỉnh có khuyên
thì mỗi khuyên được tính là 2 khi tính bậc, như vậy:
d(v) = Số cạnh liên thuộc v + 2*Số khuyên
Từ định nghĩa suy ra đỉnh cô lập trong đồ thị đơn là đỉnh có bậc bằng 0.
Số bậc lớn nhất của G ký hiệu là ∆(G), số bậc nhỏ nhất của G ký hiệu là δ(G).
Đỉnh treo là đỉnh có bậc bằng 1.
Nửa bậc: cho G=(V,E) là đồ thị có hướng, v∈V. Nửa bậc của đỉnh v, ký hiệu là d
o
(v), là số

Đường đi sơ cấp là đường đi không đi qua một đỉnh quá 1 lần.
Vòng là dãy có đỉnh đầu và đỉnh cuối trùng nhau.
Chu trình là đường đi có đỉnh đầu và đỉnh cuối trùng nhau.
Chu trình sơ cấp là chu trình không đi qua một đỉnh quá 1 lần.
Dãy có hướng trong đồ thị có hướng là dãy các đỉnh và cung nối tiếp nhau (e
1
, e
2
, , e
n
) thoả
mãn đỉnh cuối của cung e
i
là đỉnh đầu của cung e
i+1
, i=1, n-1.
Đường đi có hướng trong đồ thị có hướng là dãy có hướng, trong đó các cung không lặp lại.
Đường đi có hướng sơ cấp là đường đi có hướng không đi qua một đỉnh quá 1 lần.
Vòng có hướng là dãy có hướng có đỉnh đầu và đỉnh cuối trùng nhau.
Chu trình có hướng là đường đi có hướng có đỉnh đầu và đỉnh cuối trùng nhau.
Chu trình có hướng sơ cấp là chu trình có hướng không đi qua một đỉnh quá 1 lần.
Đồ thị vô hướng gọi là liên thông , nếu mọi cặp đỉnh của nó đều có đường đi nối chúng với
nhau.
Đồ thị có hướng gọi là liên thông mạnh , nếu mọi cặp đỉnh của nó đều có đường đi có hướng
nối chúng với nhau.
Đồ thị có hướng gọi là liên thông yếu, nếu nó không liên thông mạnh nhưng đồ thị lót của nó
liên thông.
Đồ thị có hướng gọi là bán liên thông, nếu với mọi cặp đỉnh (u,v) bao giờ cũng tồn tại đường
đi có hướng từ u đến v hoặc từ v đến u.
Nhóm 6 – lớp Khoa học máy tính K24 Trang 6

, , v
n
. Ma trận kề của đồ thị
G là ma trận vuông A=(a
ịj
)
nxn
, trong đó a
ij
là số cung đi từ v
i
tới v
j
.
I.2.2 Ma trận liên thuộc
a, Đồ thị vô hướng
Định nghĩa: Cho đồ thị G=(V,E) có n đỉnh, V={v
1
, v
2
, , v
n
} và m cạnh E={e
1
, e
2
, , e
m
}. Ma
trận liên thuộc của đồ thị G là ma trận A=(a

A=(a
ij
)
nxm
thoả mãn
1, nếu đỉnh v
i
là đỉnh đầu của cung e
j
a
ịj
= -1, nếu đỉnh v
i
là đỉnh cuối của cung e
j
0, nếu đỉnh v
i
không kề cung e
j
Nhóm 6 – lớp Khoa học máy tính K24 Trang 7
Tiểu luận môn: Toán ứng dụng
CHƯƠNG II: BÀI TOÁN CÂY STEINER
II.1 Phát biểu bài toán cây Steiner trên đồ thị
Cho đồ thị G=(V,E) có trọng số (V : tập các đỉnh; E tập các cạnh của đồ thị) và tập W ⊂
V. Tìm cây T =(W’, F) trong G nhỏ nhất bao trùm tất cả các đỉnh của W. Cây T gọi là Cây
Steiner của W, và W’-W gọi là các điểm Steiner của W ứng với cây T.
+ Ghi chú. Nếu V là tập tất cả các điểm trên mặt phẳng và trọng số của cạnh nối 2 đỉnh là
khoảng cách giữa 2 điểm đó (đồ thị vô hạn), thì bài toán Steiner gọi là bài toán Steiner với độ
dài Euclide:
Trên mặt phẳng cho tập các điểm P, nối chúng bằng các đoạn thẳng sao cho tổng các đoạn

là ma trận xuất phát D
0
= [d
0
(i,j)] trong đó d
0
(i,j) = w(i,j) nếu tồn tại cung
(i,j) và d
0
(i,j) = +∞ nếu không tồn tại cung (i,j) (đặc biệt nếu không có khuyên tại i thì
d
0
(i,i) = +∞).
P
0
= [p
0
(i,j)] trong đó p
0
(i,j) = j nếu có cung từ i đến j và p
0
(i,j) không xác định nếu
không có cung từ i đến j.
Gán k:=0.
(2) Kiểm tra kết thúc:
Nếu k = n, kết thúc. D = D
n
là ma trận độ dài đường đi ngắn nhất, P = P
n
.

(i,k)
ngược lại đặt
d
k
(i,j) := d
k-1
(i,j)
và
p
k
(i,j) := p
k-1
(i,j)
Nhóm 6 – lớp Khoa học máy tính K24 Trang 9
Tiểu luận môn: Toán ứng dụng
Quay lại bước (2).
• Phương pháp xác định đường đi ngắn nhất từ đỉnh i đến đỉnh j : Đường đi ngắn nhất từ i
đến j gồm dãy các đỉnh
i , i
1
, i
2
, i
3
, , i
k
, i
k+1
, , i
m

4
, ta có thể tìm đường đi ngắn nhất giữa các đỉnh. Chẳng hạn, để
tìm đường đi từ đỉnh d đến đỉnh c ta làm như sau:
Đặt i
1
:= P(d,c) = b; i
2
:= P(b,c) = c
Từ đó ta nhận được đường đi ngắn nhất từ d đến c: d→b→c với độ dài là 8.
II.2.2 Thuật toán Prim tìm cây phủ nhỏ nhất
+ Đầu vào:
Đồ thị G=(V,E) với trọng số.
Các đỉnh ký hiệu là: 1, 2, , n
Trọng số của cạnh (i,j), (i,j)∈E, ký hiệu là c
ij
+ Đầu ra: Cây phủ nhỏ nhất T, hoặc kết luận đồ thị không liên thông.
+ Các bước:
(1) Khởi tạo:
T là đồ thị gồm một đỉnh 1 và không có cạnh.
(2) Kiểm tra điều kiện kết thúc:
Nếu T có n-1 cạnh, Kết thúc. Kết luận: T là cây phủ nhỏ nhất. Ngược lại sang bước (3)
(3) Thêm cạnh:
Ký hiệu M là tập
M = { (i,j)∈E  i∈T & j ∉T }
Tìm cạnh (k,h)∈M sao cho
Nhóm 6 – lớp Khoa học máy tính K24 Trang 11
Tiểu luận môn: Toán ứng dụng
c
kh
= min{c

là
cạnh đầu tiên trong dãy các cạnh của T xây dựng theo thuật toán không thuộc S. Cạnh e
m
và
các cạnh của S tạo thành chu trình duy nhất C.
Chu trình C chứa đỉnh v
m
∈T
m
, trong đó T
m
= {v
1
, ,v
m
} là số đỉnh có được ở bước thêm
cạnh e
m
. Chu trình C bắt buộc phải chứa cạnh e nối đỉnh của T
m
với đỉnh không thuộc T
m
(nếu
không C⊂T). Theo thuật toán thì cạnh e có trọng số không nhỏ hơn trọng số của e
m
. Vì vậy
thay cạnh e bằng cạnh e
m
, ta thu được cây phủ S’ có d(S’) ≤ d(S). Lặp lại quá trình trên ta biến
đổi cây S thành cây phủ T và suy ra

cf
= 3 = min{c
ij
 (i,j)∈M}
Thêm đỉnh e và cạnh (a,e) vào T.
(2) Kiểm tra: Số cạnh của T là 3, sang bước (3)
(3) Thêm cạnh: Tập M là
M = {(a,b),(c,f),(d,b),(d,f),(e,f)}
Ta có: c
ef
= 2 = min{c
ij
 (i,j)∈M}
Thêm đỉnh f và cạnh (e,f) vào T.
(2) Kiểm tra: Số cạnh của T là 4, sang bước (3)
(3) Thêm cạnh: Tập M là
M = {(a,b),(d,b)}
Ta có: c
ab
= 4 = min{c
ij
 (i,j)∈M}
Thêm đỉnh b và cạnh (a,b) vào T.
(2) Kiểm tra: Số cạnh của T là 5, Kết thúc.
Kết luận: Ta có cây phủ nhỏ nhất gồm các cạnh (a,c),(c,d),(a,e),(e,f),(a,b)
với tổng trọng số là 2+1+3+2+4 = 12.
Nhóm 6 – lớp Khoa học máy tính K24 Trang 13
Tiểu luận môn: Toán ứng dụng
II.2.3 Thuật toán tìm cây Steiner
Bây giờ ta sẽ xây dựng phương pháp giải bài toán Steiner bằng cách sử dụng thuật toán






















0416532
4036752
1305421
6650354
5743025
3525203
2214530
Vì m = card(W) = 3, nên các tập S sẽ là các tập con của {1,2,4,5} với nhiều nhất là 1
phần tử. Các tập S∪W sẽ là W

- G=a
ij
với i=1 n, j=1 n (n số đỉnh của đồ thị G);
trong đó:
a
ij
= trọng số cạnh nối trực tiếp từ i đến j , a
ij
là số nguyên (int)
a
ij =
∞ nếu giữa i và j không nối trực tiếp với nhau
a
1
a
2
… … a
n
a
1
∞ a
12
a
1n
a
2
a
21
∞ ∞
…

thứ nhất của cây phủ, cạnh thứ 2, …
int n, m, SoCanh, SoCap, min Đồ thị đầu vào n đỉnh
m số đỉnh của W ⊂ V
SoCanh= số cạnh đồ thị con <W U S> <
m-1>
char filein[30], fileout[30] Lưu trữ tên file dữ liệu vào và file dữ
liệu ra.
Các biến còn lại Ngoài các cấu trúc dữ liệu chính được
khai báo ở trên, trong chương trình còn
sử dụng một số biến tạm, biến trung
gian để tính toán trong từng hàm.
Nhóm 6 – lớp Khoa học máy tính K24 Trang 17
Tiểu luận môn: Toán ứng dụng
III.1.2 Xây dựng thuật toán
III.1.2.1 Chương trình chính
Thuật toán của chương trình chính được biểu diễn theo sơ đồ khối như hình bên dưới:
Hình I.2.1. Sơ đồ khối của hàm main()
Nhóm 6 – lớp Khoa học máy tính K24 Trang 18
Sai
Đúng
tieptuc=c
hoặc C
tieptuc=c
hoặc C
Bắt đầu
Nhập tên file vào và lưu tên file
vào biến filein
Nhập tên file vào và lưu tên file
vào biến filein
Nhập tên file kết quả và lưu tên

Hình I.2.2. Sơ đồ khối của hàm DocFile()
Nhóm 6 – lớp Khoa học máy tính K24 Trang 19
Đúng
Bắt đầu
Mở file với tham số filein
Mở file với tham số filein
Kết thúc
Mở
thành công
Mở
thành công
Sai
Đọc số đỉnh từ file vào biến n
Đọc số đỉnh từ file vào biến n
Đọc các giá trị trọng số của đồ thị,
nếu bằng 0 thì đổi thành VoCung
và gán cho G[i][j], D[i][j], P[i][j]
với i, j = 1 n
Đọc các giá trị trọng số của đồ thị,
nếu bằng 0 thì đổi thành VoCung
và gán cho G[i][j], D[i][j], P[i][j]
với i, j = 1 n
Gán Card[i]=1, i=1 n
Gán Card[i]=1, i=1 n
Đọc các đỉnh phủ trong file và gán
cho Card[m] (m=1 k, m<n)
Đọc các đỉnh phủ trong file và gán
cho Card[m] (m=1 k, m<n)
Đóng file
Đóng file

tiên của Card:
T[Card[1]]=2
Khởi tạo tại vị trí đỉnh đầu
tiên của Card:
T[Card[1]]=2
Khởi tạo count = 0
Khởi tạo count = 0
count
=0
count
=0
Lặp việc thêm cạnh
(i=1 n) và tăng count++
nếu thỏa mãn điều kiện
D[i][j]!=0&&D[i][j]!=
VoCung &&T[j]==1
Lặp việc thêm cạnh
(i=1 n) và tăng count++
nếu thỏa mãn điều kiện
D[i][j]!=0&&D[i][j]!=
VoCung &&T[j]==1
Xuất ra file
output
“No Steiner
Tree”
Xuất ra file
output
“No Steiner
Tree”
Tìm giá trị nhỏ nhất

Bổ sung các đỉnh chưa kiểm tra vào để kiểm tra
Bổ sung các đỉnh chưa kiểm tra vào để kiểm tra
Nếu cây phủ đang kiểm tra có tổng trọng số nhỏ hơn cây
phủ đã kiểm tra trước đó thì hoán chuyển các CapDinh
của cây phủ đã kiểm tra bởi các cặp đỉnh của cây phủ
đang kiểm tra.
Nếu cây phủ đang kiểm tra có tổng trọng số nhỏ hơn cây
phủ đã kiểm tra trước đó thì hoán chuyển các CapDinh
của cây phủ đã kiểm tra bởi các cặp đỉnh của cây phủ
đang kiểm tra.
Quay lui để xét tất cả các cây phủ còn lại bằng việc
gọi lại hàm Try(i)
Quay lui để xét tất cả các cây phủ còn lại bằng việc
gọi lại hàm Try(i)
Kết thúc
Tiểu luận môn: Toán ứng dụng
III.1.2.5 Hàm CayPhu()
Hình I.2.5. Sơ đồ khối của hàm CayPhu()
Nhóm 6 – lớp Khoa học máy tính K24 Trang 22
Bắt đầu
Đặt k bằng số cạnh m
Đặt k bằng số cạnh m
Lấy giá trị nhỏ nhất bằng gọi hàm Prim()
Lấy giá trị nhỏ nhất bằng gọi hàm Prim()
Tìm cây phủ nhỏ nhất bằng việc tính toán giá trị của đỉnh
đầu, đỉnh cuối và trọng số của cung ab
Tìm cây phủ nhỏ nhất bằng việc tính toán giá trị của đỉnh
đầu, đỉnh cuối và trọng số của cung ab
Quay lui để xét tất cả các cây phủ còn lại bằng việc
gọi lại hàm Try()

trường Windows.
III.2.2 Giao diện chương trình
III.2.3 Dữ liệu để kiểm tra
a, Bộ dữ liệu 1
b, Bộ dữ liệu 2
Nhóm 6 – lớp Khoa học máy tính K24 Trang 24
Steiner1.OUTSteiner1.INP
7
0 4 8 4 1 2 0
4 0 2 0 2 0 3
8 2 0 3 0 0 6
4 0 3 0 0 7 0
1 2 0 0 0 5 1
2 0 0 7 5 0 5
0 3 6 0 1 5 0
3 6 7
8
1 2 5
2 5
3 2
5 7
1 6
5 1
Steiner2.OUTSteiner2.INP
4
0 1 0 0
1 1 0 0
0 0 1 1
0 0 1 0
1 4