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
ckh
khá
ái
ini
niệ
ệm
mcơ
cơb
bả
ản
n
3.2.
3.2. B
Bà
ài
ito
toá
án
nđư
đườ
ờng
ng ng
ngắ
ắn
nnh
nhấ
ất
t
3.3. B
Bà
ài
ito
toá
án
ncây
cây bao
bao tr
trù
ùm
mt
tố
ối
ithi
thiể
ểu
u
3.4. B
Bà
ài
ito
toá
án
ndòng
dòng c
cự
ự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 i1đến nút itlà bộgồm t nút khác nhau i1,…,
itsao cho (ik, ik+1)∈A.
Chu trình là bộgồmt núti
1,…,itsao cho i1,…, it-1 là mộtđường đi
vớii
t=i1và có ít nhất ba nút khác nhau.
Đồ thịvô hướng đượcgọi là liên thông nếuứng vớimỗicặp
i,j∈Nđềucómộtđường đitừi đếnj.
3.1. Các khái niệmcơbản
119
3.1. Các khái niệmcơbản
Đồ thịG (N,A) là đồ thịcó hướng nếumỗicunglàmộtcặpcóthứtự.
Trong đồ thịcó hướng, (i,j) ≠(j,i).
Trong đồ thịcó hướng có thểchứacảhai cung (i,j) và (j,i), nên để xác
định mộtđường điphảinóirõcảdãy nút i1,…,itvà dãy cung a1,…,at-1.
Đồ 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 Gs
(Ns, As) có Ns=N và As⊂A.
120
3.2. Bài toán đường ngắnnhất
Shortest path problem
3.2.1. Đ
Đặ
ặt
tv
vấ
ấn
nđ
đề
ề
3.2.2. Mô
Mô t
tả
ảd
dạ
ạng
ng to
toá
án
nh
họ
ọc
c
3.2.3. Thu
Thuậ
ật
tto
toá
án
nđ
đặ
ặt
tnhãn
nhãn