Toán ứng dụng Bài toán chọn địa
điểm
MỤC LỤC
Tiểu luận nhóm 2
1
Toán ứng dụng Bài toán chọn địa
điểm
GIỚI THIỆU
Lý thuyết đồ thị là một lĩnh vực đã có từ lâu và có nhiều ứng dụng
hiện đại. 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ỹ
Lenhard Eurle. Chính ông là người đã sử dụng đồ thị để giải bài toán nổi
tiếng về các cái cầu ở thành phố Konigsberg.
Đồ thị được sử dụng để giải các bài toán trong nhiều lĩnh vực khác
nhau. Chẳng hạn, dùng đồ thị của mạng máy tinh có thể sử dụng để xác
định hai máy tính trong mạng có thể trao đổi thông tin được với nhau hay
không. Đồ thị có trọng số trên các cạnh có thể sử dụng để giải các bài toán
như: Tìm đường đi ngắn nhất giữa hai thành phố trong mạng giao thông.
Chúng ta cũng còn sử dụng đồ thị để giải các bài toán về lập lịch, thời khóa
biểu, và phân bố tần số cho các trạm phát thanh và truyền hình… và rất
nhiều lĩnh vực khác.
Trong tiểu luận này nhóm chúng tôi trình bày “Bài toán chọn địa
điểm”.
Tiểu luận nhóm 2
2
Toán ứng dụng Bài toán chọn địa
điểm
ĐỀ TÀI:
Bài toán chọn địa điểm.
NHÓM: 05 người
STT Họ tên

đỉnh v kề đỉnh w.
- Nếu chỉ có duy nhất một cạnh e liên kết với cặp đỉnh v, w, ta viết e =
(v, w). Nếu e là cung thì v gọi là đỉnh đầu và w gọi là đỉnh cuối của cung e.
- Nếu co nhiều cạnh liên kết với cùng một cặp đỉnh thì ta nói đó là các
cạnh song song.
Tiểu luận nhóm 2
4
Toán ứng dụng Bài toán chọn địa
điểm
- Cạnh có hai đỉnh liên kết trung 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ị.
- 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.
Từ định nghĩa trên suy ra đỉnh cô lập trong đồ thị đơn là đỉnh có bậc
bằng 0. Đỉnh treo là đỉnh có bậc bằng 1
- Cho G=(V,E) là đồ thị có hướng, v ∈ V. Nửa bậc ra của đỉnh v, ký
hiệu là d
O
(v), là số cung đi ra từ đỉnh v (v là đỉnh đầu), và nửa bậc vào của
đỉnh v, ký hiệu là d
I
(v), là số cung đi tới đỉnh v (v là đỉnh cuối).
II. Đường đi, chu trình, tính liên thông
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:

i
là đỉnh đầu của cung
e
i+1
, i = 1, ,n-1.
Tiểu luận nhóm 2
5
Toán ứng dụng Bài toán chọn địa
điểm
- Đườ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ị có hướng được 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.
- Đồ thị con:
Cho đồ thị G=(V,E). Đồ thị G'=(V',E') gọi là đồ thị con phủ của G nếu
V' ⊂ V & E' ⊂ E

Từ định nghĩa suy ra rằng ma trận kề của đồ thị vô hướng luôn đối
xứng qua đường chéo chính.
Ví dụ. Xét đồ thị vô hướng
v
1
v
2
v
3
v
4
v
5
có ma trận kề là
v
1
v
2
v
3
v
4
v
5
v
1
0 1 0 0 1
v
2
1 0 1 0 1

v
2
v
6

e
1
e
4
e
6
v
1
e
3
v
4
e
2
e
8
e
5
e
7
v
3
v
5
có ma trận kề là

2. Ma trận liên thuộc
Tiểu luận nhóm 2
7
Toán ứng dụng Bài toán chọn địa
điểm
* Đồ thị vô hướng
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
Þj
)
nxm
thỏa mãn
1, nếu đỉnh v
i
liên thuộc cạnh e
j
a
ij

e
1
e
2
e
3
e
4
e
5
e
6
e
7
v
1
1 1 0 0 0 0 0
v
2
1 0 1 1 0 0 0
v
3
0 0 0 1 1 0 1
v
4
0 0 0 0 0 1 0
v
5
0 1 1 0 1 1 0
* Đồ thị có hướng

không liên thuộc cung e
j
Ví dụ. Xét đồ thị có hướng
v
2
v
6
e
1
e
4
e
6
v
1
v
4
e
3
e
8
e
2

e
5
e
7
v
3

3
0 -1 -1 0 1 0 0 0
v
4
0 0 0 -1 -1 1 1 0
v
5
0 0 0 0 0 0 -1 1
v
6
0 0 0 0 0 -1 0 -1
3. Danh sách cạnh (cung)
Trong trường hợp đồ thị thưa (đồ thị có n đỉnh và m cạnh hoặc cung
thỏa mãn m < 6n) người ta thường dùng cách biểu diễn đồ thị dưới dạng
danh sách cạnh (cung).
Cách biểu diễn đồ thị bằng danh sách cạnh (cung) ta sẽ lưu trữ danh
sách tất cả các cạnh (cung) của đồ thị vô hướng (có hướng). Một cạnh
(cung) e = (x,y) của dồ thị sẽ tương ứng với hai biến dau[e], cuoi[e]. Như
vậy, để lưu trữ đồ thị ta cần sử dụng 2m đơn vị bộ nhớ.
Nhược điểm của cách biểu diễn này là để xác định những đỉnh nào của
đồ thị là kề với một đỉnh cho trước ta phải làm cỡ m phép so sánh (khi
duyệt qua danh sách tất cả các cạnh hoặc cung của đồ thị).
Trong trường hợp đồ thị có trọng số ta cần thêm m đơn vị bộ nhớ để
lưu trữ trọng số của các cạnh.
Ví dụ. Xét đồ thị vô hướng:
v
1
v
2
v

), (v
4
, v
5
)
Được lưu trữ bởi các mảng dau[e], cuoi[e] với e = 1, ,7 như sau
Cạnh 1 2 3 4 5 6 7
Đầu V
1
V
1
V
2
V
2
V
3
V
3
V
4
Cuối V
2
V
5
V
3
V
5
V
e
5
e
7
v
3
v
5
có danh sách cung là
(v
1
, v
2
), (v
1
, v
3
), (v
2
, v
3
), (v
2
, v
4
), (v
3
, v

V
5
Cuối V
2
V
3
V
3
V
4
V
4
V
5
V
6
V
6
4. Danh sách kề
Trong rất nhiều vấn đề ứng dụng của lý thuyết đồ thị, cách biểu diễn
đồ thị dưới dạng danh sách kề là cách biểu diễn thích hợp nhất.
Trong cách biểu diễn này, với mỗi đỉnh v của đồ thị chúng ta lưu trữ
danh sách các đỉnh kề với nó, ta ký hiệu là
Ke(v) = {u ∈ V | (v,u )∈ E}
Khi đó vòng lặp thực hiện với mỗi phần tử trong danh sách này theo
thứ tự các phần tử được sắp xếp trong nó sẽ được viết như sau:
Với mọi u ∈ Ke(v) do <công việc>
Ví dụ: Xét đồ thị vô hướng:
v
1

v
6
e
1
e
4
e
6
v
1
v
4
e
3
e
8
e
2e
5
e
7
v
3
v
5
có danh sách kề là:
Ke[1]

ii
vvw
1
1
),(
Cho hai đỉnh a và z của đồ thị. Bài toán đặt ra là tìm đường đi ngắn
nhất từ a đến z.
2. Thuật toán Dijkstra
Thuật giải tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z trong đồ thị có
trọng số. Trọng số của cạnh (i,j) là w(i,j) > 0 và đỉnh x sẽ mang nhãn L(x).
Khi kết thúc thuật giải L(z) chính là chiều dài ngắn nhất từ a đến z.
Thuật toán:
Đầu vào: Đồ thị G = (V,E,w) có trọng số w(i,j) > 0 với mọi cạnh (i,j),
đỉnh a và z.
Đầu ra: L(z) chiều dài đường đi ngắn nhất từ a đến z, và đường đi
ngắn nhất (nếu có).
Phương pháp:
B1. Khởi tạo: Gán L(a) = 0. Với mọi đỉnh x ≠ a gán L(x) := ∞. Đặt
T := V.
B2. Tính m = min{L(u)| u
∈
T}
Nếu m = +∞, kết thúc, kết luận không có đường đi từ a đến z.
Ngược lại, nếu m < +∞, chọn v
∈
T sao cho L(v) = m.
Đặt T := T – {v}
Tiểu luận nhóm 2
13
Toán ứng dụng Bài toán chọn địa

- Bước quy nạp: Giả thiết L(v
i
) chính là độ dài đường đi ngắn nhất từ a
đến v
i
với mọi i < k. Ta chứng minh rằng L(v
k
) là độ dài đường đi ngắn
nhất từ a đến v
k
.
Gọi P là đường đi ngắn nhất từ a đến v
k
có độ dài l(P). Các đỉnh trên P
trừ v
k
phải thuộc
S = {v
1
, v
2
, , v
k-1
}
Giả sử, ngược lại, gọi u là đỉnh đầu tiên trên P không thuộc S và v
thuộc S là đỉnh trước u. Hiển nhiên
L(u) ≤ L(v) + w(v,u) < L(v
k
)
Nên u phải bị loại khỏi T ở bước 2 trước v

Đầ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).
Phương pháp:
B1. Khởi tạo: Ký hiệu D
0
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,j) = +∞).
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.

(i,k) + d
k-1
(k,j)
và p
k
(i,j) = p
k-1
(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)
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

k
(i,j)
Sẽ xảy ra một trong hai trường hợp sau:
a) Trong các đường nối đỉnh I với j qua các đỉnh trung gian {1, 2,
…,k-1, k} có chiều dài ngắn nhất, tồn tại một đường p không qua đỉnh k.
Khi đó p cũng là đường ngắn nhất nối đỉnh I với j qua các đỉnh trung gian
{1, 2, …, k-1}, nên theo giả thiết quy nạp
d
k-1
(i,j) = d(p) <= d
k-1
(i,k) + d
k-1
(k,j)
Do đó theo cách tính dk ta có d
k
(i,j) = d
k-1
(i,j) = d(p) là độ dài đường đi
ngắn nhất từ I đến j qua các đỉnh trung gian {1, 2, …,k-1, k}.
b) Mọi đường nối đỉnh I với j qua các đỉnh trung gian {1, 2, …,k-1, k}
có chiều dài ngắn nhất đều qua đỉnh k. Gọi p = (i,…,k,…,j) là một đường
ngắn nhất nối đỉnh i với đỉnh j qua các đỉnh trung gian {1,2,…,k-1,k}. Khi
đó đoạn (i,…k) và (k,…j) cũng phải là các đường đi ngắn nhất qua các đỉnh
trung gian {1,2,…,k-1}. Ta có:
d
k-1
(i,k) + d
k-1
(k,j) = d(p) < d

m
, j)
là đường đi từ đỉnh i đến j được xây dựng trên cơ sở ma trận P
k
như
sau:
i
1
= pk(i,j), i
2
= p
k
(i
1
,j), …, i
h+1
= p
k
(i
h
,j), …, p
k
(i
m
,j) = j
Tiểu luận nhóm 2
16
Toán ứng dụng Bài toán chọn địa
điểm
Tiểu luận nhóm 2

đường đi hai chiều nối với nhau.
Tiểu luận nhóm 2
18
Toán ứng dụng Bài toán chọn địa
điểm
Yêu cầu: Tìm địa điểm để xây xựng Trung tâm phòng cháy chữa cháy
trong N địa điểm sao cho khoảng cách xa nhất từ Trung tâm phòng cháy
chữa cháy đến một khu chung cư bất kỳ là nhỏ nhất.
3. Dữ liệu vào ra cho cả hai bài toán cực tiểu tổng và cực tiểu trị
lớn nhất trên đồ thị
Dữ liệu vào: Cho trong file văn bản GRAPH.INP có cấu trúc như sau:
Dòng 1: Ghi 2 số nguyên dương N, M, trong đó N là số đỉnh, M là số
cạnh.
M dòng tiếp theo: Mỗi dòng ghi 3 số i, j, t, trong đó i là đỉnh đầu, j là
đỉnh cuối và t là độ dài đường đi trực tiếp từ đỉnh i đến đỉnh j (trọng số).
Dữ liệu ra: Ghi ra file văn bản MINSUM.OUT theo cấu trúc:
Dòng 1: Ghi giá trị S là tổng giá trị đường đi đường đi ngắn nhất giữa
N - 1 khu dân cư đến vị trí xây dựng trường học.
Dòng 2: Ghi v
1
,v
2
, ,v
k
, Các vị trí có thể xây dựng trường học (các
đỉnh cực tiểu tổng).
Dòng 3: Ghi giá trị M là khoảng cách xa nhất từ Trung tâm phòng
cháy chữa cháy đến một khu chung cư bất kỳ là ngắn nhất (Cực tiểu trị lớn
nhất).
Dòng 4: Ghi v

If Min > Tong then
Begin
Min := Tong;
PosSave := i;
End;
End;
Writeln(f,Min);
For i:=1 to N do
Begin
Tong :=0;
For j:= 1 to N do
If i <> j then
Tong:= Tong + A[i, j];
If Min = Tong then Write(f,i, ' ');
End;
2. Thuật toán tìm cực tiểu trị lớn nhất trên đồ thị
Gọi ma trận A[N, N] là ma trân trọng số lưu khoảng cách từ địa điểm
xây dựng i đến địa điểm xây dựng j (1<= i, j <= N; 1 < N <= 100).
Ta dùng thuật toán Floyd-Warshall để tìm cực tiểu tổng trên đồ thị:
{Xây dựng ma trận đường đi ngắn nhất}
For k:=1 to N do
For i:=1 to N do
For j:=1 to N do
if (A[i,j] > A[i,k] + A[k,j]) then
A[i,j]:=A[i,k] + A[k,j];
{Tìm cực tiểu trị lớn nhất}
Min:=+∞;
For i:=1 to N do
Begin
Tiểu luận nhóm 2

Sử dụng ma trận A kích thước N x N để lưu trữ dữ liệu vào (Độ dài
đường đi giữa các địa điểm xây dựng).
Sử dụng luôn ma trận A kích thước N x N để lưu trữ kết quả đường đi
ngắn nhất khi chạy thuật toán Floyd - Warshall.
Sử dụng ma trận L kích thước N x N để lưu trữ các đỉnh trung gian
trong đường đi ngắn nhất của thuật toán Floyd - Warshall.
II Cài đặt chương trình
Program Floyd_Warshall;
Const fi='GRAPH.INP';
fo='MINSUM.OUT';
MaxN=101;
VC=2147483647;
Type mmc=Array[0 MaxN] of Longint;
mhc=Array[0 MaxN] of mmc;
Var A:mhc;L:^mhc;
N,M,Top:Byte;
Procedure Read_Data;
Var f:Text; k,i,j:Byte; t:Longint;
Begin
Assign(f,fi);
Reset(f);
Fillchar(A,Sizeof(A),0);
Readln(f,N,M);
For k:=1 to M do
Begin
Tiểu luận nhóm 2
22
Toán ứng dụng Bài toán chọn địa
điểm
Readln(f,i,j,t);

Tiểu luận nhóm 2
23
Toán ứng dụng Bài toán chọn địa
điểm
{Tim cuc tieu Tong}
Min:=VC;
For i:=1 to N do
Begin
Tong :=0;
For j:= 1 to N do
If i <> j then
Tong:= Tong + A[i, j];
If Min > Tong then
Begin
Min := Tong;
PosSave := i;
End;
End;
Writeln(f,Min);
For i:=1 to N do
Begin
Tong :=0;
For j:= 1 to N do
If i <> j then
Tong:= Tong + A[i, j];
If Min = Tong then Write(f,i, ' ');
End;
Writeln(f);
{Tim cuc tieu tri lon nhat}
Min:=VC;

Write_Data;
END.
Tiểu luận nhóm 2
25