Bài tốn Steiner và thuật tốn tìm cây Steiner

1/30

MỤC LỤC

GIỚI THIỆU...................................................................................................................................................... 2
1. LÝ DO CHỌN ĐỀ TÀI......................................................................................................................................... 2
2. YÊU CẦU BÀI TOÁN STEINER TRÊN ĐỒ THỊ:......................................................................................................3

2.1. Phần lý thuyết:...........................................................................................................................3
2.2. Cài đặt chương trình thuật tốn tìm cây Steiner bằng ngơn ngữ C...........................................3
2.3. Tập tin dữ liệu vào và dữ liệu ra................................................................................................3
3. NHÓM THỰC HIỆN...........................................................................................................................................4
CHƯƠNG 1: ĐẠI CƯƠNG VỀ ĐỒ THỊ................................................................................................................. 5
1. CÁC KHÁI NIỆM CƠ BẢN..................................................................................................................................5

1.1. Đồ thị, đỉnh, cạnh, cung:............................................................................................................5
1.2. Bậc, nửa bậc vào, nửa bậc ra.....................................................................................................5
1.3. Đường đi, chu trình, tính liên thơng..........................................................................................5
2. BIỂU DIỄN ĐỒ THỊ............................................................................................................................................6

2.1. Ma trận kề.................................................................................................................................6
CHƯƠNG 2: CÂY STEINER................................................................................................................................ 7
1. PHÁT BIỂU BÀI TOÁN CÂY STEINER TRÊN ĐỒ THỊ............................................................................................7
2. THUẬT TOÁN CÂY STEINER.............................................................................................................................9
3. SƠ ĐỒ KHỐI THUẬT TỐN TÌM CÂY STEINER...................................................................................................10
4. CÁC THUẬT TỐN..........................................................................................................................................11

4.1. Thuật tốn Floyd-Warshall......................................................................................................11
4.2. Thuật tốn Prim tìm cây phủ nhỏ nhất....................................................................................12

4.3. Thuật toán sinh tổng quát (dùng để sinh tập con)...................................................................14
4.4. Thuật tốn DFS (kiểm tra thành phần liên thơng)...................................................................14
5. THIẾT KỀ CẤU TRÚC DỮ LIỆU GIẢI THUẬT......................................................................................................15

5.1. Thiết kế cấu trúc dữ liệu:.........................................................................................................15
5.2. Các bước thực hiện giải thuật..................................................................................................16
CHƯƠNG 3: CHƯƠNG TRÌNH......................................................................................................................... 18
1. CHƯƠNG TRÌNH C..........................................................................................................................................18
2. KIỂM THỬ CHƯƠNG TRÌNH............................................................................................................................28
KẾT LUẬN...................................................................................................................................................... 29
TÀI LIỆU THAM KHẢO................................................................................................................................................30

Nhóm thực hiện : Lê An Pha- Lâm Bá Mẫn-Nguyễn Thị Ánh Hồng- Lê Ngọc Khánh


Bài tốn Steiner và thuật tốn tìm cây Steiner

2/30

GIỚI THIỆU

1. LÝ DO CHỌN ĐỀ TÀI
Lý thuyết đồ thị là một vấn đề hết sức phức tạp, hơn nữa nó chiếm một vị trí
quan trọng trong khối kiến thức cơ sở của ngành công nghệ thông tin. Để hiểu được lý
thuyết về đồ thị cũng như hiểu được hoạt động của các thuật tốn trên đồ thị cần phải có
thời gian tìm hiểu lâu dài.
Lý thuyết đồ thị có rất nhiều bài tốn được ứng dụng có hiệu quả trong nhiều
lĩnh vực. Bài toán Steiner trên đồ thị là một trong những bài toán tối ưu được ứng dụng
rộng rãi.
Trong thực tế hiện nay có rất nhiều ứng dụng cần dùng đến bài toán Steiner để

giải quyết. Cụ thể các ứng dụng của cây Steiner là:
 Bố trí mạch điện trong bo mạch điện tử.
 Nối hệ thống mạng với chi phí nhỏ nhất.
 Xây dựng các tuyến đường giao thơng và các nút/ điểm quan trọng (bệnh
viện, trường học, khu cơng cộng…)…
Để hồn thiện đề tài này, nhóm chúng em chân thành cảm ơn Thầy Trần Quốc
Chiến đã cung cấp những kiến thức quí báu và hướng dẫn chúng em hồn thành đề tài
này.

Nhóm thực hiện : Lê An Pha- Lâm Bá Mẫn-Nguyễn Thị Ánh Hồng- Lê Ngọc Khánh


Bài tốn Steiner và thuật tốn tìm cây Steiner

3/30

2. U CẦU BÀI TOÁN STEINER TRÊN ĐỒ THỊ:
2.1. Phần lý thuyết:
- Trình bày bài tốn Steiner trên đồ thị
- Trình bày thuật tốn tìm cây Steiner
- Thiết kế cấu trúc dữ liệu và giải thuật tìm cây Steiner
2.2. Cài đặt chương trình thuật tốn tìm cây Steiner bằng ngơn ngữ C.
2.3. Tập tin dữ liệu vào và dữ liệu ra
- File dữ liệu đầu vào: GRAPH.INP có cấu trúc:
n
(số đỉnh)
a11 a12 ... a1n
(ma trận trọng số)
a21 a22 ... a2n
....................

an1 an2 ... ann
u1 u2
...uh
(các đỉnh phủ)
- File dữ liệu đầu ra STEINER.OUT có cấu trúc
+ Trường hợp các đỉnh phủ liên thơng:
W
(trọng số cây phủ Steiner)
v1 v2
...
vk
(các đỉnh Steiner)
y1 z1
(cạnh thứ 1 của cây phủ)
y2 z2
(cạnh thứ 2 của cây phủ)
...
ym
zm
(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ụ: STEINER.INP
STEINER.OUT
7
8

4
8
4
1

2

1
2
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
4

NO STEINER TREE

1


1
1




1
1


1

1
4
Nhóm thực hiện : Lê An Pha- Lâm Bá Mẫn-Nguyễn Thị Ánh Hồng- Lê Ngọc Khánh

5


Bài tốn Steiner và thuật tốn tìm cây Steiner

4/30

3. NHĨM THỰC HIỆN
STT


Họ tên

1

Lê An Pha

2

Lâm Bá Mẫn

3

Lê Ngọc
Khánh

4

Nguyễn Thị
Ánh Hồng

Công việc
(theo mục lục)
Chương 2: Cây Steiner
4.4. Thuật toán DFS
5. Thiết kế cấu trúc dữ liệu
Chương 3: Chương trình
1. Cài đạt chương trình
Viết báo cáo và trình bày
Chương 2: Cây Steiner

2. Thuật toán Steiner
4.3. Thuật toán sinh tổng
quát
5.Các bước thực hiện giải
thuật
Phản biện 1
Chương 1
Chương 2: Cây Steiner
4.1. Thuật toán FloydWarshall
Phản biện 2
Chương 2: Cây Steiner
3. Sơ đồ khối
4.2. Thuật toán Prim tìm cây
phủ nhỏ nhất
Chương 3: Chương trình
2. Kiểm thử chương trình
Phản biện 3

Chữ ký

Nhận xét của
giáo viên

Nhóm thực hiện : Lê An Pha- Lâm Bá Mẫn-Nguyễn Thị Ánh Hồng- Lê Ngọc Khánh


Bài tốn Steiner và thuật tốn tìm cây Steiner

5/30


CHƯƠNG 1: ĐẠI CƯƠNG VỀ ĐỒ THỊ
1. CÁC KHÁI NIỆM CƠ BẢN
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ết với một cặp đỉnh (v, w) có thứ tự.
Cạnh có hai đỉnh liên kết trùng nhau gọi là khuyên.
Đỉnh không kề với đỉnh khác gọi là đỉnh cô lập.
Số đỉnh của đồ thị gọi là bậc của đồ thị, số cạnh hoặc số cung của đồ thị gọi là
cỡ của đồ thị.
Đồ thị hữu hạn là đồ thị có bậc và cỡ hữu hạn.
Đồ thị đơn là đồ thị khơng có khun và khơng có cạnh song song.
Đồ thị vơ hướng đủ là đồ thị mà mọi cặp đỉnh đều kề nhau.
Đồ thị có hướng đủ là đồ thị có đồ thị lót đủ.
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ó khun thì mỗi khun đượ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 ra của đỉnh v, ký hiệu là dO(v),
là số cung đi ra từ đỉnh v (v là đỉnh đầu), và nửa bậc vào của đỉnh vV, ký hiệu là
dI(v), là số cung đi tới đỉnh v (v là đỉnh cuối).
1.3. Đường đi, chu trình, tính liên thơng
Định nghĩa. Cho đồ thị G=(V,E).

Dãy  từ đỉnh v đến đỉnh w là dãy các đỉnh và cạnh nối tiếp nhau bắt đầu từ
đỉnh v và kết thúc tại đỉnh w. Số cạnh trên dãy  gọi là độ dài của dãy .
Dãy  từ đỉnh v đến đỉnh w độ dài n được biểu diễn như sau
 = (v, e1, v1, e2, v2, ... , vn-1, en, w)
trong đó vi (i=1,...,n-1) là các đỉnh trên dãy và e i (i=1,...,n) là các cạnh trên dãy liên
thuộc đỉnh kề trước và sau nó. Các đỉnh và cạnh trên dãy có thể lặp lại.
Đường đi từ đỉnh v đến đỉnh w là dãy từ đỉnh v đến đỉnh w, trong đó các cạnh
khơng lặp lại.
Đường đi sơ cấp là đường đi không đi qua một đỉnh quá 1 lần.
Nhóm thực hiện : Lê An Pha- Lâm Bá Mẫn-Nguyễn Thị Ánh Hồng- Lê Ngọc Khánh


Bài tốn Steiner và thuật tốn tìm cây Steiner

6/30

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,
e2, ... , en) thoả mãn đỉnh cuối của cung ei là đỉnh đầu của cung ei+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 q 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 đồ thị lót (vơ hướng) 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.
Trọng đồ (có hướng) là đồ thị (có hướng) mà mỗi cạnh (cung) của nó được gán
một số.
Trọng đồ được biểu diễn bởi G=(V, E, w), trong đó V là tập các đỉnh, E là tập
các cạnh (cung) và w:ER là hàm số trên E, w(e) là trọng số của cạnh (cung) e với
mọi eE.
Trong trọng đồ độ dài trọng số của đường đi  là tổng các trọng số trên đường
đi đó.
2. BIỂU DIỄN ĐỒ THỊ
2.1. Ma trận kề
2.1.1 Đồ thị vô hướng
Định nghĩa. Cho đồ thị vơ hướng G=(V,E) có n đỉnh theo thứ tự v1, v2, ..., vn .
Ma trận kề của đồ thị G là ma trận vuông A=(aịj)nxn , trong đó aij là số cạnh nối vi với
vj. Lưu ý rằng mỗi khuyên được tính là hai cạnh.
Từ định nghĩa suy ra rằng ma trận kề của đồ thị vơ hướng ln đối xứng qua
đường chéo chính.
2.1.2 Đồ thị có hướng
Định nghĩa. Cho đồ thị có hướng G=(V,E) có n đỉnh theo thứ tự v 1, v2, ..., vn .
Ma trận kề của đồ thị G là ma trận vng A=(a ịj)nxn , trong đó aij là số cung đi từ vi
tới vj.
Nhóm thực hiện : Lê An Pha- Lâm Bá Mẫn-Nguyễn Thị Ánh Hồng- Lê Ngọc Khánh


Bài tốn Steiner và thuật tốn tìm cây Steiner


7/30

CHƯƠNG 2: CÂY STEINER
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 tốn Steiner gọi là bài tố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 thẳng là nhỏ nhất.
Sau đây là lời giải cho trường hợp P có 3 và 4 điểm:

 Trường hợp nối 3 điểm a,b,c ta tìm điểm v sao cho các góc avb = avc =
bvc = 1200.
 Trường hợp nối 4 điểm a,b,c,d ta tìm điểm u,v sao cho các góc auv = cuv =
bvu = dvu = 1200.
Ghi chú. Nếu W là tập con thực sự của V, thì cây phủ nhỏ nhất của đồ thị <W>
sinh bởi W có thể khơng phải là cây Steiner của W.
Ví dụ 1 Xét đồ thị

Nhóm thực hiện : Lê An Pha- Lâm Bá Mẫn-Nguyễn Thị Ánh Hồng- Lê Ngọc Khánh


Bài tốn Steiner và thuật tốn tìm cây Steiner

8/30


Cho tập W = {1, 2, 3, 4}. Đồ thị <W> sinh bởi W có tập đỉnh {1, 2, 3, 4} và tập
cạnh là {(1,2),(2,3),(3,4),(4,1),(1,3)}. Dễ thấy rằng cây phủ nhỏ nhất của <W> có các
cạnh {(2,3),(3,4),(4,1)} với tổng trọng số là 9. Tuy nhiên cây với tập đỉnh {1, 2, 3, 4, 5}
và tập cạnh {(1,5),(5,2),(2,3),(3,4)} phủ W và có trọng số là 8 < 9.
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
tốn Floyd-Warshall tìm khoảng cách và đường đi ngắn nhất và thuật tốn tìm cây phủ
nhỏ nhất.
 Định lý. Cho trọng đồ đơn đủ G với các đỉnh {1, 2, ..., n} và trọng số w(i,j) thoả
bất đẳng thức tam giác
w(i,j)  w(i,k) + w(k,j) i, j, k
Cho W là tập m đỉnh trong G. Khi đó tồn tại cây Steiner của W trong G với số
điểm Steiner không vượt quá m-2.
 Chứng minh
Giả sử số đỉnh Steiner của W ứng với cây T là p. Khi đó T có (m+p) đỉnh và
(m+p-1) cạnh. Ký hiệu x là bậc trung bình (trong T) của các điểm Steiner và y là bậc
trung bình (trong T) của các điểm khơng Steiner. Theo bổ đề bắt tay ta có :
p.x + m,y = 2.(m+p-1)
Mặt khác x  3 (theo bất đẳng thức tam giác) và y  1. Suy ra p  m-2.

Nhóm thực hiện : Lê An Pha- Lâm Bá Mẫn-Nguyễn Thị Ánh Hồng- Lê Ngọc Khánh


Bài tốn Steiner và thuật tốn tìm cây Steiner

9/30

2. THUẬT TỐN CÂY STEINER
+ Đầu vào. Trọng đồ liên thơng G=(V,E,w) n đỉnh, và tập W  V m đỉnh, m < n.
+ Đầu ra. Cây Steiner của W trong G.
+ Các bước.

- Bước 1. Xây dựng trọng đồ đơn đủ G’=(V,F,w’) (bằng thuật tốn FloydWarshall), trong đó w’(u,v) là khoảng cách ngắn nhất từ u đến v với mọi cặp (u,v).
- Bước 2. Với mỗi S  V-W , card(S)  m-2, tìm cây phủ nhỏ nhất của đồ thị
<WS> sinh bởi WS trong G’. Trong các cây phủ đó tìm cây T’ có trọng số nhỏ
nhất.
- Bước 3. Xây dựng cây Steiner T từ T’ bằng cách thay mỗi cạnh nối hai đỉnh
trong G’ bằng đường đi nối chúng với nhau trong G. Các đỉnh thuộc T mà không thuộc
W là những đỉnh Steiner.
+ Ví dụ. Tìm cây Steiner của W = {3,6,7} trong đồ thị cho ở ví dụ trên.
Ma trận khoảng cách của đồ thị trên là

D=

0
3

5

4
1

2
2


3
0
2
5
2
5

3

5
2
0
3
4
7
5

4
5
3
0
5
6
6

1
2
4
5
0
3
1

2
5
7
6

3
0
4

2
3
5

6
1

4
0

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à W1= {3,6,7}, W2 = {3,6,7,1}, W3 = {3,6,7,2}, W4 =
{3,6,7,4}, W5 = {3,6,7,5}, Các cây phủ trọng số nhỏ nhất của các đồ thị sinh bởi
W1, ..., W5 trong G’ có trọng số tương ứng là 9, 9, 9, 12 và 8. Vậy ta sẽ chọn đồ thị
sinh bởi W5 có cây phủ nhỏ nhất như sau:
Cạnh (3,5) trong cây T’ thay bằng đường đi
ngắn nhất 5-2-4. Tương tự, Cạnh (5,6)
trong cây T’ thay bằng đường đi ngắn nhất
5-1-6.

Cuối cùng ta nhận được cây Steiner, có
các điểm Steiner là 1, 2 và 5.

Nhóm thực hiện : Lê An Pha- Lâm Bá Mẫn-Nguyễn Thị Ánh Hồng- Lê Ngọc Khánh



Bài tốn Steiner và thuật tốn tìm cây Steiner

10/30

3. SƠ ĐỒ KHỐI THUẬT TỐN TÌM CÂY STEINER
STAR
T

FILE INPUT
FILE OUTPUT

Doc_File_MTK

KiemTraMaTranKe

false

true
false

DFS
true
Floy_Warshall

Init_S

Ghi_File NO STEINER TREE

SinhToHopW


Trong_So_Min (PRIM)

Tree_Steiner

Trọng số cây Steiner = 0

Trọng số cây Steiner != 0
Ghi_File Cây Steiner

END

Nhóm thực hiện : Lê An Pha- Lâm Bá Mẫn-Nguyễn Thị Ánh Hồng- Lê Ngọc Khánh


Bài tốn Steiner và thuật tốn tìm cây Steiner

11/30

4. CÁC THUẬT TỐN
4.1. Thuật tốn Floyd-Warshall
Thuật giải tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị (có hướng) liên
thơng (mạnh) có trọng số.
+ Đầu vào. Đồ thị liên thơng G=(V,E), V= {1, 2, ... , n}, có trọng số với mọi cung
(i,j).
+ Đầu ra. Ma trận D=[d(i,j)], trong đó d(i,j) là chiều dài đường đi ngắn nhất từ i đến j
với mọi cặp (i,j).
Ma trận P=[p(i,j)] dùng để xác định đường đi ngắn nhất.
+ Phương pháp.
(1) Bước khởi tạo: Ký hiệu D0 là ma trận xuất phát
D0 = [d0(i,j)]

trong đó d0(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ó khun tại i thì d0(i,i) = +).
P0 = [p0(i,j)]
trong đó p0(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 = Dn là ma trận độ dài đường đi ngắn nhất, P = Pn.
Ngược lại tăng k lên 1 đơn vị (k:=k+1) và sang (3).
(3) Tính ma trận Dk và Pk theo Dk-1 và Pk-1:
Với mọi cặp (i,j), i=1..n, j=1..n thực hiện:
Nếu dk-1(i,j) > dk-1(i,k) + dk-1(k,j) thì đặt
dk(i,j) := dk-1(i,k) + dk-1(k,j)
và
pk(i,j) := pk-1(i,k)
ngược lại đặt
dk(i,j) := dk-1(i,j)
và
pk(i,j) := pk-1(i,j)
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 , i2 , i3 , ... , ik ,
ik+1 , ... , im , j thỏa mãn i1 = p(i,j) , i2 = p(i1,j) , ... , ik+1 = p(ik,j) , ... , p(im,j) = j
+ Ví dụ.

Xét đồ thị

Nhóm thực hiện : Lê An Pha- Lâm Bá Mẫn-Nguyễn Thị Ánh Hồng- Lê Ngọc Khánh



Bài tốn Steiner và thuật tốn tìm cây Steiner

12/30

Áp dụng giải thuật Floyd-Warshall ta nhận được các ma trận sau:
Ta có ma trận xuất phát D0 và P0 như sau :

Sau khi áp dụng giải thuật ta có kết quả ma trận khoảng cách D4 và P4 như sau:

Cuối cùng, ta có ma trận khoảng cách ngắn nhất giữa các đỉnh D = D4. Ta thấy
đồ thị liên thông và chứa chu trình.
Sử dụng ma trận P = P4 , 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 i1 := P(d,c) = b; i2 := 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à 7.
4.2. Thuật tố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à cij
Nhóm thực hiện : Lê An Pha- Lâm Bá Mẫn-Nguyễn Thị Ánh Hồng- Lê Ngọc Khánh


Bài tốn Steiner và thuật tốn tìm cây Steiner

13/30

+ Đầ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
ckh = min{cij  (i,j)M}
Nếu ckh < , thêm cạnh (k,h) và đỉnh h vào T, sang bước (2).
Ngược lại, kết thúc. Kết luận đồ thị G không liên thơng.
Chứng minh thuật tốn
Cho cây phủ S bất kỳ của đồ thị G, ta phải chứng minh
d(S)  d(T)
Ký hiệu các đỉnh và các cạnh lần lượt được thêm vào T là
v1, v2,...,vn và e1, e2,...,en-1
trong đó ek =(vk,vk+1), k=1,2,...,n-1.
Nếu các cạnh của T cũng là cạnh của S thì hiển nhiên d(S) = d(T).
Ngược lại gọi em là cạnh đầu tiên trong dãy các cạnh của T xây dựng theo thuật
tốn khơng thuộc S. Cạnh em 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 vmTm , trong đó Tm = {v1,...,vm} là số đỉnh có được ở
bước thêm cạnh em. 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 Tm (nếu không CT). Theo thuật tốn thì cạnh e có trọng số khơng nhỏ
hơn trọng số của em. 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 q trình trên ta biến đổi cây S thành cây phủ T và suy ra
d(S)  d(S’)  ...  d(T)
+ Ví dụ. Tìm cây phủ nhỏ nhất của đồ thị

Áp dụng thuật toán PRIM ta có cây phủ nhỏ nhất gồm các cạnh: (a,c),(c,d),(a,e),(e,f),(a,b)
Nhóm thực hiện : Lê An Pha- Lâm Bá Mẫn-Nguyễn Thị Ánh Hồng- Lê Ngọc Khánh



Bài tốn Steiner và thuật tốn tìm cây Steiner

14/30

Tổng trọng số T là 2+1+3+2+4 = 12.
4.3. Thuật toán sinh tổng quát (dùng để sinh tập con)
Áp dụng thuật toán sinh tổng quát (sinh chuỗi nhị phân) để tìm tập hợp các phần tử.
Procedure Generate
Begin
c = InitialConfigure; //cấu hình ban đầu
Process (c);
// xử lý cấu hình đang có
if c=LastConfigure then Stop:=true
else stop := false;
while (not stop) do
Begin
//Sinh cấu hình kế tiếp từ cấu hình đang có
c=getNextConfigure(c);
Process (c); // xử lý cấu hình này
if c= LastConfigure then stop = true;
End;
End;
4.4. Thuật tốn DFS (kiểm tra thành phần liên thông).
void DFS1(int v)
{
process(v);
chuaxet[v]=0
for (int i=1; i<=n; i++)
if (G(v,i) && chuaxet[v]==1) DFS1(i);

}
void DFS()
{ for(v=1;v<=n;v++) chuaxet[v]=1;
for (int v=1; v<=n; v++)
if (chuaxet[v]) DFS1(v)
}

Nhóm thực hiện : Lê An Pha- Lâm Bá Mẫn-Nguyễn Thị Ánh Hồng- Lê Ngọc Khánh


Bài tốn Steiner và thuật tốn tìm cây Steiner

15/30

5. THIẾT KỀ CẤU TRÚC DỮ LIỆU GIẢI THUẬT
5.1. Thiết kế cấu trúc dữ liệu:
Đồ thị G = (V, E,w) , n số đỉnh của đồ thị G. Ta sử dụng ma trận kề để lưu dữ
liệu đầu vào đồ thị, ma trận kề MTK[n][n]
Trong đó: aij = trọng số cạnh nối trực tiếp từ i đến j , aij là số nguyên (int). i,j : 1->n
aij = ∞ nếu giữa i và j không nối trực tiếp với nhau . i,j : 1->n
Khai báo C:
+ Ma trận MTK lưu trữ ma trận kề của đồ thị G
int mtk[max][max];
+ Ma trận MTK_D, MTK_P lưu trữ đồ thị đường đi ngắn nhất và đồ thị đỉnh qua
giải thuật FloydWarshall
int mtk_D[max][max];
int mtk_P[max][max];
+ Mãng cấu trúclưu trữ Các tập SW của cây phủ W qua giải thuật PRIM
struct tap_phu
{

int card; // số đỉnh phủ của tập
int min; // giá trị trọng số nhỏ nhất cây phủ
int dsd[max]; // danh sách đỉnh của tập phủ
};
tap_phu W[max]; //W[0] lưu tập đỉnh W. W[1::max] Mãng lưu trữ các tập SW
tap_phu S; // tập đỉnh S
+ Mãng cấu trúc lưu trữ danh sách tập cạnh đồ thị
struct tap_canh
{
int m;
int dsc[max][3];
};
tap_canh ck_W[max],dsc_W[max],dsc_steiner;
Nhóm thực hiện : Lê An Pha- Lâm Bá Mẫn-Nguyễn Thị Ánh Hồng- Lê Ngọc Khánh


Bài tốn Steiner và thuật tốn tìm cây Steiner

16/30

+ Mãng cấu trúc lưu tập đỉnh Steiner
struct diem_steiner
{
int m; //số lượng đỉnh
int dsd[max];// danh sách đỉnh Steiner
};
diem_steiner P_S;
5.2. Các bước thực hiện giải thuật
 Bước 1
Đọc file dữ liệu đầu vào của đồ thị G đã cho (file có cấu trúc ma trận kề) bằng thủ

tục Doc_File_MTK(). Đối với file dữ liệu đầu vào aij = 0 khi khơng có đường đi từ i->j,
thủ tục đọc file sẽ chuyển các giá trị 0 này thành 1000 (vô cực dương)
Kết quả :
-

Ma trận kề MTK[n][n]

-

Tập đỉnh W : W[0]

 Bước 2
Kiểm tra ma trận kề có đối xứng khơng. Nếu khơng đối xứng,kết luận đồ thị khơng
có cây Steiner. Nếu đối xứng tiếp tục bước 3.
Hàm kiểm tra đối xứng : KiemTraMaTranKe() ; Nếu trả về 1 thì đối xứng.
 Bước 3
Kiểm tra đồ thi liên thông. Nếu không liên thông,kết luận đồ thị khơng có cây
Steiner. Nếu liên thơng thực hiện bước 4.
Thủ tục kiểm tra liên thông theo chiều rộng : DFS(). Nếu stplt=1 đồ thị liên thông.
 Bước 4
Gọi thủ tục tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị bằng thuật toán
Floyd-Warshall.
Thủ tục : Floyd_Warshall() ;
Kết quả :
-

Ma trận kề trọng số nhỏ nhất MTK_D[n][n]

Nhóm thực hiện : Lê An Pha- Lâm Bá Mẫn-Nguyễn Thị Ánh Hồng- Lê Ngọc Khánh



Bài tốn Steiner và thuật tốn tìm cây Steiner

-

17/30

Ma trận đỉnh tương ứng MTK_P[n][n]

 Bước 5
Gọi thủ tục tìm cây phủ nhỏ nhất cho từng đồ thị con của G’ tìm được ở bước 4,
G’=(V,E,w’) (đồ thị con <WS> sinh bởi WS trong G’ với S  V-W,card(S)  m-2).

Thủ tục :
-

Khởi tạo giá trị ban đầu cho thủ tục tìm tập con của phần tử <WS> : init_S();

-

Thủ tục tìm tập con của phần tử <WS> : enumerate();

-

Thủ tục tìm trọng số nhỏ nhất các cây phủ tập W bằng giải thuật PRIM :
Trong_So_Min();

Kết quả :
- Tìm ra các tập WS : W[0 ::nW] , với nW : số tập W tìm được. Chứa tập đỉnh và
giá trị nhỏ nhất của cây phủ.

- Trong các cây phủ W đó tìm cây T’ có tổng trọng số nhỏ nhất : min_steiner, là số
thứ tự của tập W[0 ::nW].
 Bước 6
Xây dựng cây Steiner cho cây phủ T’ tìm được ở bước 5.
Thủ tục :
-

Tree_Steiner()

Kết quả :
-

Tìm ra tập cạnh cây Steiner : dsc_steiner, chứa tập cạnh, trọng số cạnh

-

Tìm ra tập đỉnh Steiner : P_S, chứa các đỉnh steiner.

 Bước 7
Kết xuất giá trị sang file lưu trữ, dựa vào ma trận MTK_D[n][n], MTK_P[n][n] để
tìm đường đi ngắn nhất giữa các đỉnh tìm được trong bước 6
-

Thủ tục ghi file : Ghi_file().

-

Kết quả : Kết quả của đồ thị

 Bước 8

Kết thúc.

Nhóm thực hiện : Lê An Pha- Lâm Bá Mẫn-Nguyễn Thị Ánh Hồng- Lê Ngọc Khánh


Bài tốn Steiner và thuật tốn tìm cây Steiner

18/30

CHƯƠNG 3: CHƯƠNG TRÌNH
1. CHƯƠNG TRÌNH C
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
const max=20;
const vc=1000;
struct tap_phu
{
int card, min;
int dsd[max];
};
struct diem_steiner
{
int m;
int dsd[max];
};
struct tap_canh
{
int m;
int dsc[max][3];

};
tap_phu W[max], S;
tap_canh ck_W[max],dsc_W[max],dsc_steiner[max];
diem_steiner P_S[max];//
int min_prim,min_phu,nS,count,stop,nW,nWm,stn;
int mtk[max][max], mtk_D[max][max], mtk_P[max][max],dsc[max][3], ck[max][3];
char filemo[30], fileluu[30];
int int n,m,stplt,sc,sc_prim, min_steiner,kt_mtk, tham[max], b[max];
Nhóm thực hiện : Lê An Pha- Lâm Bá Mẫn-Nguyễn Thị Ánh Hồng- Lê Ngọc Khánh


Bài tốn Steiner và thuật tốn tìm cây Steiner

int void Doc_File_MTK()
{

int tam,gt;
FILE *f=fopen(filemo,"r");
if (f==NULL)
{
printf("\n File %s khong co \n",filemo); exit(0); }
fscanf(f,"%d",&n);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{ fscanf(f,"%d",&mtk[i][j]); }
tam=0;
while (!feof(f))
{ fscanf(f,"%d",>);
if (gt!=0) { tam++ ; W[0].dsd[tam]=gt;}
}

W[0].card=tam; W[0].min=vc;

fclose(f);
}
void Ghi_file()
{

int i,j;
FILE *f=fopen(fileluu,"w");
if ((kt_mtk==1)&&(stplt==1)&&(min_steiner!=0))
{
//in danh sach dinh tap các Cay Steiner
fprintf(f,"%d",min_steiner);
for (int x=1;x<=stn;x++)
{

fprintf(f,"\n");
for (i=1;i<=P_S[x].m;i++)
{

Nhóm thực hiện : Lê An Pha- Lâm Bá Mẫn-Nguyễn Thị Ánh Hồng- Lê Ngọc Khánh

19/30


Bài tốn Steiner và thuật tốn tìm cây Steiner

20/30

fprintf(f,"%d",P_S[x].dsd[i]); fprintf(f,"\t");

}
fprintf(f,"\n");
for (i=1;i<=dsc_steiner[x].m;i++)
{
fprintf(f,"%d\t%d",dsc_steiner[x].dsc[i][0],dsc_steiner[x].dsc[i][1]);
fprintf(f,"\n");
}}
}
else
{ fprintf(f,"NO STEINER TREE"); }
}
void Chuyen_MTK_DSC_W()
{

int i,ii,j,jj,k,kk,nn;
k=0; nn=W[nWm].card;
for (ii=1;ii<=nn;ii++)
{
for (jj=ii+1;jj<=nn;jj++)
{

i=W[nWm].dsd[ii];
j=W[nWm].dsd[jj];
if(mtk_D[i][j]!=vc)
{ k++;
dsc_W[nWm].dsc[k][0]=i; dsc_W[nWm].dsc[k][1]=j;
dsc_W[nWm].dsc[k][2]=mtk_D[i][j];
}}

}

dsc_W[nWm].m=k; m=k;
}

Nhóm thực hiện : Lê An Pha- Lâm Bá Mẫn-Nguyễn Thị Ánh Hồng- Lê Ngọc Khánh