MÔ HÌNH MẠNG
Kếtthúcchương này, sinh viên có thể:
1. Nắm đượcnhững khái niệmcơ bảncủamôhìnhmạng
2. Hiểu được bài toán đường đingắnnhấtvàvậndụng vào kinh tế
3. Hiểu được bài toán cây bao trùm tốithiểuvàvậndụng vào kinh tế
4. Hiểu được bài toán đường dòng cực đạivàvậndụng vào kinh tế
Chương 3
117
3.1.
3.1.
C
C
á
á
c
c
kh
kh
á
á
i
i
ni
ni
ệ
ệ
m
m
cơ
cơ
b

n
nh
nh
ấ
ấ
t
t
3.3.
B
B
à
à
i
i
to
to
á
á
n
n
cây
cây
bao
bao
tr
tr
ù
ù
m
m

ự
c
c
đ
đ
ạ
ạ
i
i
Mục lục
118
 Đồ thị vô hướng G là mộtcặpgồmhaitập N và A, ký hiệu
G(N,A), vớiN làtập các nút và A là tập các cung vô hướng.
Cung vô hướng là mộtcặp không kểđếnthứ tự hai nút khác
nhau i và j (i,j∈N) ký hiệu là (i,j).
Trong đồ thị vô hướng, cung (i,j) = cung (j,i).
 Một đường đitừ nút i
1
đến nút i
t
là bộ gồm t nút khác nhau i
1
,…,
i
t
sao cho (i
k
, i
k+1
)∈A.

.
 Đồ thị có hướng là liên thông nếu đồ thị vô hướng tương ứng là liên
thông.
 Cây là một đồ thị vô hướng, liên thông và không có chu trình.
 Cây bao trùm của đồ thị G (N,A) là một cây trong G có chứatấtcả các
nút củaG cònsố cung có thể ít hơn. Do vậy, cây bao trùm là cây G
s
(N
s
, A
s
) có N
s
=N và A
s
⊂ A.
120
3.2. Bài toán đường ngắnnhất
Shortest path problem
3.2.1.
Đ
Đ
ặ
ặ
t
t
v
v
ấ
ấ

c
3.2.3.
Thu
Thu
ậ
ậ
t
t
to
to
á
á
n
n
đ
đ
ặ
ặ
t
t
nhãn
nhãn
121
3.2.1. Đặtvấn đề
Công ty ABC có mộtvàidự án xây dựng nằmkhắpnơi trong địa
bàn tỉnh. Hàng ngày công ty có nhiều chuyếnxeđưa công nhân,
chuyên chở thiếtbị và vậttưđilạigiữatrụ sở công ty và các công
trường xây dựng.
Công ty muốnxácđịnh các tuyến đường ngắnnhấtnhằmtốithiểu
khoảng cách di chuyểntừ văn phòng công ty đếncáccông

chính là tìm đường ngắnnhấttừ nhiềuhoặcthậmchímọi nút
khác nút i đến nút k.
Vậy, bài toán đường ngắnnhất là bài toán tìm đường
ngắnnhấttừ mọinúti∈N đếnmộtnútk∈Nchotrước
trên đồ thị G(N,A).
124
3.2.3. Thuậttoánđặt nhãn
 Thuật toán đặtnhãnlàthuậttoándựavàoviệc đặt nhãn cho các
nút để tìm đường ngắnnhất.
 Nhãn của nút i gồm 2 con số nằm trong dấu ngoặc vuông và
đượckýhiệulà[c
1i
, T], trong đóc
1i
là giá trị khoảng cách từ nút
1 đến nút i, và T là ký hiệusố thứ tự của nút đứng ngay trước
nút i theo đường đitừ nút 1 đếnnúti.
 Nút chưa đặtnhãnlànútchưaxácđịnh được đường đitừ nút 1
đếnnútđó.
 Nút đã được đặt nhãn tạmthời là nút đãxácđịnh đượcmột
đường đitừ nút 1 đến nút đó.
 Nút có nhãn cốđịnh khi thuậttoánđãxácđịnh được đường đi
ngắnnhấttừ nút 1 đến nút đó.
125
3.2.3. Các bướccủathuậttoánđặt nhãn
Bước1: Đầu tiên, giả sử nút 1 có nhãn cốđịnh [0,S].
Bước2: Đặt nhãn tạmthời cho các nút liên thông trựctiếptừ nút 1.
GọiN
1
là tập các nút có nhãn tạmthờivới nút 1.

kj
}.
GọiN
tt
là tập các nút có nhãn tạmthời.
Xét các c
1j
với ∀j ∈ N
tt
giả sử c
1m
= min {c
1j
}.
Như vậy, đặt nhãn cố định cho nút m.
Tiếp tục qui trình này cho đến khi tất cả các nút có nhãn cố định
thì kết thúc thuật toán.
127
3.2.3. Các bước…
Bước 4: Xác định khoảng cách ngắnnhấttừ nút 1 đến nút bất
kỳ.
Đường ngắn nhất đến một nút nhất định k có thể tìm
bằng cách xuất phát từ nút k và di chuyển ngược về
nút ngay trước.
Tiếp tục di chuyển ngược chiều qua mạng sẽ tìm thấy
đường ngắn nhất từ nút 1 đến nút đang đề cập.
128
Ứng dụng thuậttoánchomạng công ty ABC
 Bước1: Nút 1 có nhãn cốđịnh [0,S]
3

15
1
17
6
10
3
4
5
2
6
4
[0,S]
[15,1]
130
Ứng dụng…
Bước 3: Các nút liên thông với nút 3 là 2 và 5. Đặtnhãntạmthời
cho nút 5 [14,3]; Điềuchỉnh nhãn tạmthời cho nút 2 thành
[13,3]. Đặt nhãn cố định cho nút 2.
3
6
2
5
7
15
1
4
17
6
10
3

4
[0,S]
[10,1]
[13,3]
[14,3]
[19,2]
[30,2]
132
Ứng dụng…
 Xét các nút liên thông với nút 5. Đặtnhãntạmthời cho nút 6
[16,5], Điều chỉnh nhãn tạm thời cho nút 4 [18,5]. Xét 3 nút
tạmthời 4,6,7. Nút 6 sẽđược đặtnhãncốđịnh
3
6
2
5
7
15
1
4
17
6
10
3
4
5
2
6
4
[0,S]

[14,3]
[18,5]
[16,5]
[22,6]
134
Ứng dụng…
Cuối cùng, chỉ có nút 7 liên thông với nút 4. Vì
c
14
+5=18+5=23>22 nên không điềuchỉnh nhãn củanút7.Nút
7 là nút cuối cùng được đặt nhãn cố định.
3
6
2
5
7
15
1
4
17
6
10
3
4
5
2
6
4
[0,S]
[10,1]

ạ
ng
ng
to
to
á
á
n
n
h
h
ọ
ọ
c
c
c
c
ủ
ủ
a
a
b
b
à
à
i
i
to
to
á

i
i
thi
thi
ể
ể
u
u
137
3.3.1. Đặtvấn đề
Trung tâm máy tính khu vựcphảilắp đặt đường cáp truyền
thông để liên kết5 ngườisử dụng máy tính vớimộtmáychủ
trung tâm. Việclắp đặtlàmột công việctốnkém. Nhằmgiảm
chi phí, nhóm quảntrị mạng trung tâm muốntổng chiềudài
đường cáp truyền thông càng ngắncàngtốt.
Trong mạng, máy tính trung tâm có thểđượckếtnốitrựctiếp
vớitừng ngườisử dụng và cho phép những ngườisử dụng khác
tham gia vào hệ thống bằngcáchliênkếtvớinhững ngườisử
dụng đãkếtnốivớihệ thống.
Mạng truyền thông của Trung tâm máy tính khu vực
như sau:
138
Mạng truyền thông của Trung tâm máy
tính khu vực(Khoảng cách tính bằng
km)
5
4
1
2
6

s
) thỏa mãn min ∑ c
ij
, ∀(i,j) ∈A
s
, A
s
⊂ A.
Vậy, bài toán cây bao trùm tổithiểu là bài toán tìm tập
các cung liên thông tấtcả các nút vớitổng khoảng cách
trên cung nhỏ nhất.
140
3.3.3. Thuật toán cây bao trùm tốithiểu
Tư tưởng củathuật toán là xem xét các nút và đưatừng nút vào
tập các nút N
s
.
Thuậttoáncâybaotrùmtốithiểugồm các bướcsau:
GọiN
C
là tập các nút đã đượcchọn để đưavàoN
S
và N
U
là tập
các nút còn lại
Bước1: Bắt đầutạimột nút i bấtkỳ. Nút i ∈ N
C
. Xét các cung
(i,k) vớik∈N