Trang:1
Chương mở đầu

GIỚI THIỆU CHUNG VỀ NHIỆM VỤ

Đề tài “Điều hành dự án bằng phương pháp PERT-PCM và ứng
dụng giải bài toán lập lịch thi công công trình”, bao gồm

- Tìm hiểu phương pháp PERT-PCM (phương pháp sơ đồ mạng
lưới).
- Ứng dụng giải bài toán lập lịch thi công công trình.
+ Lưu trữ lịch thi công các dự án
+ Cho biết thới gian bắt đầu một dự án và thời gian kết thúc dự án
+ Thêm một số hạng mục khi dự án đang được thi công
+ Bỏ một số hạng mục khi dự án đang thi công
+ Đưa ra lịch thi công các hạng mục tối ưu nhất
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
Trang:2

Chương I

ĐIỀU HÀNH DỰ ÁN BẰNG PHƯƠNG PHÁP
PERT-CMP
(Phương pháp sơ đồ mạng lưới) Dự án (Project) là một tập hợp các hoạt động (Activity) liên quan với

khâu): kế hoạch, điều hành và kiểm tra điều chỉnh. Pha kế hoạch có nội
dung là lập một sơ đồ mạng lưới (arrow network diagram hoặc arrow
diagram), tương tự một đồ thị có hướng. Pha này mở đầu bằng việc tách
dự án thành nhiều hoạt động riêng và định thời gian hoàn thành chúng.
Trong mạng, mỗi cung có hướng biểu diễn hoạt động và cả sơ đồ mạng
biểu thị mối quan hệ giữa các hoạt động. Mỗi nút biểu thị một biến cố hoặc
sự kiện (event), đánh dấu hoàn thành một số hoạt động (activity) là các
cung đi vào nút, và bắt đầu các hoạt động ứng với các cung ra khỏi nút.

Pha điều hành (scheduling phase) có nhiệm vụ xây dựng biểu đồ thời
gian, chỉ rõ thời điểm bắt đầu và kết thúc của mỗi hoạt động và mối quan
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
Trang:3
hệ giữa các hoạt động. Nói riêng, điều quan trọng là phải tính chính xác
các hoạt động tới hạn, tức là găng (critical), cần chú ý đặc biệt khi thực
hiện, để toàn bộ dự án được hoàn thành đúng hạn.

Pha kiểm tra bao gồm việc sử dụng sơ đồ mạng lưới, và biểu đồ thời
gian để theo dõi và báo cáo định kì tiến triển của dự án. Nếu cần thì phải
phân tích lại và xác định sơ đồ mới cho phần dự án còn lại.

I.
Lập sơ đồ mạng lưới

Như trên đã nói, pha đầu của phương pháp PERT-CPM là lập kế
hoạch thể hiện ở một sơ đồ mạng lưới, biểu diễn như một đồ thị có hướng.
Hãy xét một dự án xây dựng một toà nhà. Việc tách dự án thành các hoạt
động như đào đất, xây móng, xây tường thô, lợp mái, đặt đường dây điện
… là do kiến trúc sư hoặc kỹ sư xây dựng làm. Dựa vào đó, người quản lý

và xong 1/2x
1
đó như ở H1.2.

Khởi công

2 Đào móng 4 Xây móng
1
2
3
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
Trang:4
10 Xây thô
6 Lợp mái

4 Chỉnh thẳng tường ngoài
Đặt dây điện 7
2
1
x
1
3
1
x
1

2
1
x
1Hình 1.2

II.
Phân tích các chỉ tiêu thời gian. Xác định đường căng.

Pha điều hành có nhiệm phân tích các chỉ tiêu thời gian và đưa ra các
bảng và số liệu cần thiết trên sơ đồ mạng lưới. Nếu trong dự án phải điều
hành cả nguyên liệu (hoặc nhân lực) thì phải xét cả các chỉ tiêu đó, ta sẽ
nói đến ở mục sau.

II.1.
Tính các thời điểm.


tính E
3
, E
4
, E
5
, E
6
, E
9
, E
10
và E
11
cũng tương tự vì các nút tương ứng chỉ
có một cung vào, khi đó:
E
i
= E
j
+ t
ji

Ở đây j là nút ngay trước i. Chẳng hạn E
6
+ t
46
= 16 + 6 = 22. Nếu có
nhiều cung vào nút, tức là nhiều hoạt động kết thúc tại biến cố, thì từ định
nghĩa E

= maxmax {E
j
+ t
ji
},
j
ở đây j là các nút ngay trước i, tức là có cung nối tới i. Các E
i
được ghi ở
H.1.3 là số đầu trong ngoặc ở mỗi nút.
Thời điểm muộn (latest time) của biến cố j là thời điểm muộn nhất mọi
cung đi vào biến cố j đều hoàn thành mà không làm thay đổi thời điểm kết
thúc dự án sớm nhất có thể, ký hiệu là L
j
. Đối lại với E
j
, các L
j
được tính
theo hướng lùi (backward pass), tức là đi từ nút kết thúc. Theo định nghĩa,
ở nút kết thúc thì E
n
= L
n
, ở thí dụ H.1.1 là E
13
= L
13
= 44. nếu ở biến cố chỉ
có một cung ra, tức là một hoạt động được bắt đầu thì, thời điểm muộn là :

– t
9 12
} = min (38 – 4, 38 - 5) = 33
Hãy chú ý sự ‘’đối xứng ‘‘ của quá trình tính E
i
và L
j
. Các L
j
được ghi ở số
thứ 2 trong ngoặc ở mỗi nút trong H.1.3.

II.2.
Tính thời gian dự trữ.

Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
Trang:6
Trong thời gian dự trữ (slack hoặc float) của một biến có là hiệu thời điểm
muộn và thời
điểm sớm của
nó : d
i
= L
i
– E
i
.
Thời gian dự trữ
(slack hoặc float)

- E
i
trừ đi thời
gian để
thực hiện là t
ij
.
Thời gian dự trữ
độc lập (free float
hoặc free slack),
ký hiệu là FF
ij
,
cũng là ký hiệu
thời gian dành
cho (i, j) và thời
gian thực hiện là
t
ij
, nhưng với giả
thiết là mọi hoạt động đều bắt đầu sớm có thể, vậy :
FF
ij
= E
j
– E
i
– t
ij
.

2

6
8
1
0

1
3

1
2

4
4
4
4
4

4

4
(44, 44)
6

0
2

(38, 42)
(29, 33)

động (i, j có TF
ij
= 0 được gọi là hoạt động găng (critital activity). Biến cố i
có d
i
=0 được gọi là biến cố găng (critical event).
Một số tính chất quan trọng của đường găng là như sau.
1. Mỗi dự án đều có ít nhất một đường găng.
2. Tất cả các hoạt động (i, j) có TF
ij
= 0, tức là mọi hoạt động găng
đều phải nằm trên đường găng.
3. Mọi biến cố găng, tức là biến cố i có d
i
= 0, đều phải nằm trên
đường găng. Biến có không găng không thể nằm trên đường
găng.
4. Đường nối nút khởi công đến nút kết thúc mà mọi biến cố trên đó
đều găng có thể không phải đường găng vì có thể có hoạt động
không găng. Chẳng hạn đường 1 –> 2 –> 3 –> 4 –> 7 –> 9 –> 12
–> 13 không găng vì TF
47
= 2.
5. Đường găng là đường dài nhất trong các đường nối nút khởi
công đến nút kết thúc.
Điều 5 này là rõ từ định nghĩa vì ở nút khởi công và kết thúc hai thời
điểm sớm và muộn trùng nhau và thời gian hoàn thành dự án chính là hiệu
thời gian ở hai nút (ở H.1.3 là 44 - 0). Đường găng là đường gồm các hoạt
động không có dự trữ nên tổng chiều dài, tức là thời gian thực hiện, là toàn
bộ thời gian thực hiện dự án (ở H.1.3 là 44), nên phải dài nhất. Trên H.1.3

10 38 42 4 (8, 10) 4
11 37 38 1 (9, 11) 1
12 38 38 0 (9, 12) 0
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
Trang:8
13 44 44 0 (10, 13) 4
(12, 13) 0

Bảng1.1. Chỉ tiêu thời gian xây nhà
Ngoài các chỉ tiêu chính nói trên, khi cần các thông tin chi tiết hơn để
điều hành dự án, người ta cũng đưa ra một số khái niệm về thời gian khác
nữa như sau.
Thời điểm khởi công sớm (earliest start) của hoạt động (i, j) là thời
sớm của nút gốc: ES
ij
= E
i
.
Thời điểm hoàn thành sớm (earliest completion) của hoạt động (i, j) là
EC
ij
= E
i
+ t
ij
.
Thời điểm khởi công muộn (latest start) của hoạt động (i, j) là LS
ij
= L

i
+t
ij
= EC
ij
,
Vì i cũng là một trong các nút k ngay trước j. Bất đẳng thức thứ hai
tương tự.
Thời gian dự trữ của một đường đi (total float of a path) P từ nút khởi
công đến nút kết thúc, ký hiệu TF
p
, là thời gian có thể kéo dài thêm các
hoạt động trên đường này mà không ảnh hưởng đến thời điểm hoàn thành
công trình, tức là
TP =



PGP
ij
G
ij
TTtt
,
ở đây
G
G
ij
Tt 


Hai định nghĩa trên đây của đường đi có thể mở rộng cho đường P có
nút đầu và cuối trùng với nút trong đường găng, không cần là nút khởi
công và kết thúc của cả dự án.
Thí dụ II.1. Ở dự án trên H.1.3, đường găng dược tô đậm. Thời điểm
hoàn thành sớm EC
68
= E
6
+ t
68
= 22 + 7 = 29 = E
8
, EC
10, 13
= 40 < E
13
=
44. Thời điểm khởi công muộn LS
46
= L
6
– t
46
= 26 – 6 = 20 > L
4
= 16. Bây
giờ giả sử P là đường đi 1 –> 2 –> 3 –> 4 –> 5 –> 6 –> 8 –> 10 –> 13 thì
T
P
=

7
35
44
3542



. Ta
thấy mặc dù T
Q
> T
P
nhưng thời hạn thực hiện các hoạt động không găng
trong P lại chặt chẽ hơn hoạt động không găng (4, 7) duy nhất của Q.
Nguyên nhân là (4, 7) là không găng duy nhất, nên mọi sự nới lỏng của Q
đều dồn cho hoạt động này.
Chú ý rằng các dữ liệu thời gian quan trọng nhất là các chỉ tiêu có
trong bảng 1.1. Ở bảng này cũng cho thấy đường găng (đường gồm các
hoạt động găng, tức là có thời gian dự trữ chung bằng 0).

II.4.
Biểu đồ thời gian
Một cách truyền thống, bên cạnh sơ dồ lưới bảng, để theo dõi điều
hành thời gian cho dự án là dùng biểu đồ thời gian (time chart). Ta hãy xét
cách vẽ và sử dụng biểu đồ thời gian qua một thí dụ.
Thí dụ II.2. Xét dự án ở H.1.4, và bảng 1.2 tương ứng. (chú ý là hoạt
động giả (4, 5) lại là hoạt động găng.)

19
0
4
3
6
6
13
19
0
2
0
0
0
0
0
(1, 2)
(1, 3)
(2, 4)
(3, 4)
(3, 5)
(4, 5)
(4, 6)
(4, 7)
(5, 6)
(5, 7)
(6, 7)
2
0
2
0

2

2 3
2
5

Hình: 1.5
Biểu đồ được vẽ từ các E
i
và L
i
ở Bảng1.2 (hoạt động găng hay không
găng thì theo TF
ij
bằng 0 hay khác 0). Các số không có vòng chỉ thời gian
thực hiện của hoạt động. Chẳng hạn hoạt động (1, 2) thực hiện trong 2
đơn vị thời gian, được phép xê dịch trong khoảng thời gian 4 đơn vị (từ 0
đến 4). Xét sâu hơn thì sự xê dịch có tự do trong khoảng thời gian này
không là phụ thuộc vào FF
ij
= TF


III.
Điều khiển nhân lực.

Các hoạt động không găng được phép xê dịch nhất định, nhất là khi
FF
ij
= TF
ij
. Có thể sắp đặt chúng đáp ứng các yêu cầu khác nữa. Ngoài
thời gian ra, chẳng hạn nhân lực, nguyên liệu, chi phí …Về mặt toán học
xử lý yêu cầu loại nào cũng vậy. Ở đây ta nói theo ngôn ngữ nhân lực
chẳng hạn.
Thí Dụ III.1. Giả sử nhân lực cho các hoạt động của dự án ở Thí Dụ
II.2 đòi hỏi như sau:

Hoạt động

Số nhân Hoạt động số nhân công

1

1

3

5

4


For evaluation only.
Trang:11
công
(1, 2) 0 (4, 6) 2
(1, 3) 5 (4, 7) 1
(2, 4) 0 (5, 6) 2
(3, 4) 7 (5, 7) 5
(3, 5) 3 (6, 7) 6

Chú ý rằng tại thời điểm hai hoạt động cùng tiến hành thì số nhân lực
cần là tổng hai số công nhân. Vì vậy cần phải sắp xếp khéo các hoạt động
không găng để đòi hỏi tổng nhân công của cả dự án ít (tạm coi là mỗi
người biết làm mọi việc). Việc sắp xếp tối ưu là phức tạp, đến nay ta sử
dụng biểu đồ thời gian biểu diễn thêm nhân lực để sắp xếp theo trực quan.
H.1.6 (a) biểu diễn tổng công nhân cần ở mỗi thời điểm nếu tất cả các hoạt
động không găng xếp vào lúc sớm nhất có thể, còn H.1.6 (b) là tương ứng
khi xếp vào lúc muộn nhất có thể. Hai biểu đồ này nên vẽ thẳng dưới H.1.5
nữa. Sắp đặt sớm nhất ở hình (a) cho thấy ở mỗi thời điểm dự án cần
nhiều nhất là 10 công nhân còn ở sắp đặt muộn nhất (b) là 12 công nhân.
Ở hai phương án này, số công nhân cần ở các thời điểm không đều. Theo
trực quan ta chỉnh lại từ (a) như sau: chuyển hoạt động (4, 6) đến thời
điểm muộn nhất có thể, chuyển (4, 7) đến ngay sau khi (5, 7) kết thúc. Kết
quả được vẽ lại ở biểu đồ H.1.7. (chú ý là hoạt động (1, 2) và (2, 4) không
cần công nhân nên không cần vẽ.).


3 4 6
10 11 13 14 17
19

Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
Trang:12 H .I.6 (a)
(4, 7)

(3, 5) (3, 4) (5, 7) (1, 3) (4, 6) (6, 7) (5, 6)
H .I.6 (b)


4

5

6

7

4

6

7
7

5

5

3
4
2

2

4

Thời gian
ố công nhân

vào các hoạt động găng. Cụ thể là nếu ta quan tâm đến hạn chế chi phí
thì với (i, j)  G, tìm số gia chi phí C
ij
khi đạt được rút ngắn thời gian thực
hiện hoạt động là t
ij
(tìm bằng thực tế công nghệ, không phải thuần tuý
toán học). Khi đó sẽ chọn cách tăng chí phí để giảm thời gian sao cho đạt
ij
ij
t
C


min
. Giả sử cực tiểu là
0
0
ij
ij
t
C


. Khi đó độ dài đường găng mới, tức là
thời gian hoàn thành dự án mới, là

 ,
0
~

cần để làm xong khi hoạt động được thực hiện thuận lợi nhất. Thời gian
này rất khó đạt được. Theo lý thuyết thống kê, thì đây thực chất là cận
dưới (lower bound) của phân bố xác suất. Thời gian bi quan (pressimistic
time), ký hiệu là b, là thời gian cần để xong hoạt động khi tiên hành gặp
trục trặc nhất, tức là cận trên (upper bound) của phân bố xác suất. Thời
gian hợp lý nhất (most likely time), ký hiệu là m, là thời gian hiện thực nhất,
tức là có xác suất lớn nhất (đỉnh cao nhất của hàm mật độ). Ba lượng trên
chưa đủ để xác định phân bố xác suất của thời gian hoạt động. Do đó
chưa đủ để xác định kỳ vọng t
e
tức là giá trị trung bình theo xác suất, và
phương sai 
2
đặc trưng cho độ lệch khỏi t
e
của thời gian hoạt động. Mô
hình cần hai gải thiết phù hợp thực tế sau đây.
Giả thiết 1. b - a, tức là độ dài khoảng mà thời gian hoạt động có thể
lấy, bằng 6 lần độ lệch chuẩn (standard deviasion), tức là ta có phương sai
2
2
)(
6
1







e
b
a
e
dxxfxx
dxxxfX
,)()(
,)(
22


ở đây x
e
là kỳ vọng và 
2
là phương sai của biến ngẫu nhiên x, P {…} là
xác suất của biến cố {…}. Mỗi một trong hàm mật độ hoặc hàm phân phối
đặc trưng hoàn toàn cho biến ngẫu nhiên. Kỳ vọng và phương sai là các
đại lượng quan trọng. Ta cũng nói là hàm mật độ (hoặc hàm phân bố), xác
định hoàn toàn phân bố xác suất. Phân bố beta (beta distribution) là một
trong các phân bố xác suất phổ biến nhất, xác định bởi hàm mật độ sau,
nếu 0  x  1,
1111
)1(
),(
1
)1(
)()(
)(
)(

11
0
1
)1(:),(
:)(
dtttB
et
t





=1, =2  =  =2, =2 ==1

m 1 x

Hình 1.8

Nếu y lấy giá trị trên [a, b] và có phân bố theo beta thì hàm mật độ
nhân được từ (4.2) bằng đổi biến y = a + (b - a)x. Chẳng hạn, hàm mật độ
của phân bố beta có dạng như H.1.8 với   1,   1 và a = 0, b = 1.
Phân bố chuẩn (normal distribution) là phân bố xác suất phổ biến
nhất, định nghĩa bởi hàm mật độ sau.


có phân bó là phân bô chuẩn
với kỳ vọng 0, phương sai là 1.
Hàm mật độ của phân bố chuẩn
có dạng ở H.1.9 Các biến ngẫu nhiên x
1
, …, x
n
được gọi là độc lập (independent) nếu.
P{x
1
 X
1
, …, x
n
 X
n
} = P
{x
1

 X
n
},
Định nghĩa giới hạn trung tâm (centrer – limit thoerem) nói rằng với các
điều kiện khá nhẹ, tổng các biến ngẫu nhiên độc lập luôn có phân bố
chuẩn (không phụ thuộc vào phân bố của từng biến ngẫu nhiên).

For evaluation only.
Trang:16
Thí dụ V.1. Giả sử dự án xây nhà ở H.1.1 bây giờ có các thời gian hoạt
động là ngẫu nhiên có phân bố beta thoả hai giả thiết trên và xác định
được ba mốc thời gian lạc quan, bi quan và hợp lý nhất theo bảng1.3. Khi
đó phương sai và kỳ vọng của các thời gian hoạt động, tình theo công thức
(4, 1) và (4, 3) được ghi ở hai cột cuối.

Hoạt
động
Thời gian
lạc quan a

Thời gian
hợp lý
nhất m
Thời gian
bi quan b
Kỳ vọng t
e

Phương
sai 
2
(1, 2)

(2, 3)

(3, 4)


4

5
3
5
4

1

1

5
2

2
1
3

9

2
1
4

2
1
5

2
1


9

10

11
9
17
4

7 3

9
2

4

10

4

6

7

5



4

9
1

9
4Bảng 1.3
Nhận xét rằng cột kỳ vọng ở Bảng1.3, do thí dụ được xây dựng đặc
biệt, trùng hoàn toàn với các thời gian hoạt động trong mô hình tất định đã
xét ở H.1. Do đó đường găng xây dựng trên các thời gian hoạt động kỳ
vọng trùng với đường găng của mô hình tất định ở H.1.2 và thời gian của
đường găng này là 44.
Tuy nhiên để xác định kỳ vọng và phương sai của thời gian dự án, ta
cần thêm hai giả thiết sau.
Giả thiết 3. Các thời gian hoạt động là các biến ngẫu nhiên độc lập.
Giả thiết 4. Đường găng xây dựng trên các thời gian hoạt động kỳ
vọng, luôn đòi hỏi thời gian (hoàn thành mọi hoạt động trên nó) lớn hơn
các đường khác.
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
Trang:17
Tính thật chi ly trong các thí dụ cụ thể thì hai giả thiết 3 và 4 có thể
không đúng. Chẳng hạn, ở Thí dụ V.1, nếu sảy ra thời gian bi quan ở mọi
hoạt động thì đường găng đã tính là 69 (ngày). Còn đường 1 –> 2 –> 3 –>
4 –> 5 –> 7 –> 9 –> 12 –> 13 có thời gian bi quan là 70. Tuy vậy người ta
vẫn chấp nhận các giả thuyết xấp xỉ này. Khi đó, vì kỳ vọng và phương sai

47} = 0,1584. Do đó xác suất cần tìm là  1 – 0,1584  0,84.
Phương pháp điều hành dự án có tính ngẫu nhiên trên đây thường
được gọi là phương pháp ba ước lượng PERT (PERT three estimate
method).
Nếu cần tính các yếu tố thời gian ở các biến cố trung gian (không chỉ
thời gian hoàn thành dự án, tức là biến cố cuối) thì ta lý luận như sau.
Trước hết tính kỳ vọng và phương sai của thời điểm sớm 
i
của biến cố i.
Nếu chỉ có một đường từ khởi công đến i thì, do các hoạt động là độc lập
kỳ vọng của 
i
ký hiệu là E(
i
), bằng tổng các kỳ vọng t
e
của thời gian các
hoạt động dẫn đến i. Khi có nhiều đường dẫn đến i thì người ta coi xấp xỉ
(để đơn giản) E(
i
) và Var(
i
) là tổng các t
e
và 
2
của các hoạt động theo
đường đến i có tổng E(
i
) dài nhất. Nếu có nhiều đường với cùng E(

ii
ii
KzP
Var
ET
Var
E
PTP 



















,
ở đây
)(

động khi nó được tiến hành trong điều kiện bình thường, tức là chuẩn,
không có cước phí bổ xung tăng cường (như làm ngoài giờ, tăng thiết bị
nhân lực …). Cực điểm (crash point) là điểm ứng với thời gian và cước phí
khi đầu tư hết mức để thời gian thực hiện hoạt động ngắn nhất có thể. Mọi
điểm trung gian giữa điểm chuẩn và cực điểm, tức là mọi cách thoả hiệp
thời gian cước phí (time – cost trade - off) đều coi là chấp nhận được,
xem H.1.10.

Hình 1.10
Đường cong thời gian – cước phí của hoạt động (i, j).

Các ký hiệu trên H.1.10 rõ ràng như sau. D
ij
là d
ij
là thời gian chuẩn và
thời gian cực điểm. C
Dij
và C
dij
là cước phí chuẩn (normal cost) và cước phí

T cho trước và làm cực tiểu cước phí dự án C.
Nhận xét rằng các yếu tố của bài toán đều là tuyến tính, ta cố gắng
đưa về quy hoạch tuyến tính như sau:
Cước phí trực tiếp
K
ij
C
dij

Cực điểm
Điểm chuẩn

Th
ời
gian

C
xij
C
Dij
d
ij

x
ij
D
ij
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
Trang:19

là nút kết thúc dự án thì
y
1
= 0, y
n
T.
Ở mục tiêu thì K
ij
là hằng. Tóm lại ta được quy hoạch tuyến tính
.,0
0
,
,min
1
),(
Tyy
yxy
Dxd
xS
n
ijiji
ijijij
ji
ijij




.
Trường hợp không có thời hạn bắt buộc T cho trước, tức là cần tìm
thoả hiệp tốt nhất giữa tổng cước phí và tổng thời gian dự án, người ta coi
T là tham số và giải quy hoạch tuyến tính tham số để được nghiệm tối ưu
như hàm của T.

VII.
Kiểm tra hiệu chỉnh dự án.

Sau khi dùng phương pháp điều hành dự án PERT – CPM xác định
được sơ đồ mạng lưới, các biểu đồ và bảng tính các chỉ tiêu và dự án
đang được tiến hành, người quản lý luôn phải theo dõi, kiểm tra. Điều kiện
lao động thực tế có thể nhiều bất ngờ. Khi cần thiết có thể phải dùng
phương pháp PERT – CPM lại, dựa trên các dữ liệu mới, để tính toán cho
phần còn lai của dự án. Sau đó điều hành dự án theo các biểu đồ và bảng
tính mới.
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
Trang:20

CHƯƠNG 2

CƠ SỞ VỀ LÝ THUYẾT ĐỒ THỊ

I.
Một số khái niệm cơ bản.

Lý thuyết độ thị là một lĩnh vực nghiên cứu đã 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

và E là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi
là các cạnh. Hai cạnh e
1
và e
2
được gọi là cạnh lặp nếu chúng cùng tương
ứng với một cặp đỉnh.
Rõ ràng mỗi đơn đồ thị đều là đa đồ thị, nhưng không phải đa đồ thị
nào cũng là đơn đồ thị, vì đa đồ thị có thể có 2 (hoặc nhiều hơn) cạnh nối
một cặp đỉnh nào đó.
Trong mạng máy tính có thể có những kênh thoại nối một máy nào đó
với chính nó (chẳng hạn với mục đích thông báo). Mạng như vậy được cho
trong hình 3. Khi đó đa đồ thị không thể mô tả được mạng như vậy, bởi vì
có những khuyên (cạnh nối một đỉnh với chính nó ). Trong trường hợp này
chúng ta cần sử dụng đến các khái niệm giả đồ thị vô hướng, được định
nghĩa như sau:
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
Trang:21

Định nghĩa 3: Giả đồ thị vô hướng G = (V,E) bao gồm V là tập các
đỉnh, và E là họ các cặp không có thứ tự gồm hai phần tử (không nhất thiết
phải khác nhau) của V gọi là các cạnh. Cạnh e được gọi là khuyên nếu có
dạng e = (u,u).

Định nghĩa 4: Đơn đồ thị có hướng G =(V,E) bao gồm V là tập các
đỉnh, và E là tập các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là
các cung.
Nếu trong mạng có thể có đa kênh thoại một chiều, ta phải sử dụng đến
khái niệm đa đồ thị có hướng:

a f e g

Hình 1: Đồ thị vô hướng G.

Thí dụ 1: Xét đồ thị trong hình 1, ta có:

deg(a)= 1, deg(b)=4, deg(c)=4, deg(f)=3, deg(d)=1, deg(e)=3,
deg(g)=0.
Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 gọi là đỉnh treo. Trong thí dụ trên
đỉnh g là đỉnh cô lập, a và d là các đỉnh treo. Bậc của đỉnh có tính chất sau:




Vv
vm )deg(2

Định lý 1: Giả sử G = (V,E) là đồ thị vô hướng với m cạnh. Khi đó.
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
Trang:22
Chứng minh. Rõ ràng mỗi cạnh e = (u,v) được tính một lần trong
deg(u) và một lần trong deg(v). Từ đó suy ra tổng tất cả các bậc của các
đỉnh bằng hai lần số cạnh.
Thí dụ 2: Đồ thị với n đỉnh và mỗi đỉnh có bậc là 6 có bao nhiêu
cạnh?.
Giải: Theo định lý 1, ta có 2m = 6n. Từ đó suy ra số cạnh của đồ thị là

Định nghĩa 4: Ta gọi bán bậc ra (bán bậc vào) của các đỉnh v trong đồ
thị có hướng là số cung của đồ thị đi ra khỏi nó (đi vào nó) và ký hiệu là
deg
+
(v) (deg(v)).
Định lý 2: Giả sử G = (V,E) là đồ thị có hướng. Khi đó

Evv
VvVv







)(deg)(deg

Rất nhiều tính chất của đồ thị có hướng không phụ thuộc vào hướng
trên các cung của nó. Vì vậy, trong nhiều trường hợp sẽ thuận tiện hơn
nếu ta bỏ qua hướng trên các cung của đồ thị. Đồ thị vô hướng thu được
bằng cách bỏ qua hướng trên các cung được gọi là đồ thị vô hướng tương
ứng với dồ thị có hướng đã cho.

1.3. Đường đi, chu trình, đồ thị liên thông.

Định nghĩa 1: Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số
nguyên dương, trên đồ thị vô hướng G =(V,E) là dãy x
0
, x

Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp
lại.

Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
Trang:23
Định nghĩa 2: Đường đi độ dài n từ đỉnh u đến đỉnh v trong đó n là số
nguyên dương, trên đồ thị vô hướng G =(V, A) là dãy x
0
, x
1
, … ,x
n-1
,x
n

trong đó u =x
0
, v=x
n
, (x
i
, x
i+1
) A, i= 0, 1, 2… , n-1. Đường đi nói trên còn
có thể biểu diễn dưới dạng dãy các cung: (x
0
, x
1
), (x

nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.

Định nghĩa 7: Đồ thị có hướng G =(V,A) được gọi là liên thông yếu nếu
đồ thị vô hướng tương ứng với nó là đồ thị vô hướng liên thông.
Rõ ràng nếu đồ thị là liên thông mạnh thì nó cũng là liên thông yếu,
nhưng điều ngược lại là không luôn đúng.
Định lý1: Đồ thị vô hướng liên thông là định hướng được khi và chỉ khi
mỗi cạnh của nó nằm trên ít nhất một chu trình.
Chứng minh: Điều kiện cần, giả sử (u, v) là một cạnh của đồ thị. Sự
tồn tại đường đi có hướng từ u đến v và ngược lại suy ra (u, v) phải nằm
trên ít nhất một chu trình.
Điều kiện đủ, thủ tục sau đây cho phép định hướng các cạnh của đồ
thi để thu được đồ thị có hướng liên thông mạnh. Giả sử C là chu trình
nào đó trong đồ thị. Định hướng các cạnh trên chu trình này theo một
hướng đi vòng theo nó. Nếu tất cả các cạnh của đồ thị đã được định
hướng thì kết thúc thủ tục. Ngược lại chọn e là cạnh chưa định hướng có
chung đỉnh với ít nhất một trong số các cạnh đã định hướng. Theo giả thiết
tìm đựơc chu trình C’ chứa cạnh e định nghĩa các cạnh chưa định hướng
của C
’
theo một hướng dọc theo chu trình này (không định hướng lại các
cạnh đã có hướng). Thủ tục trên sẽ lặp lại cho đến khi tất cả các cạnh của
đồ thị được định hướng. Khi đó ta thu được đồ thị có hướng liên thông
mạnh.

II.
Biểu diễn đồ thị trên máy tính.

Generated by Foxit PDF Creator © Foxit Software
For evaluation only.


1 2 3 4 5 6
1
2
3
4
5
6

3 4 2 5 1 6 1 4

2 5 3 6
G G
1Hình 1: Đồ thị vô hướng G và Đồ thị có hướng G
1Các tính chất của ma trận kề:

1. Rõ ràng ma trận kề của đồ thị vô hướng là ma trận đối xứng, tức là
a[i, j]= a[j, i], i, j = 1, 2,…,n. Ngược lại, mỗi (0, 1) – ma trận đối xứng cấp n
sẽ tương ứng chính xác đến cách đánh số đỉnh (còn nói là: chính xác đến
đẳng cấu), với một đơn đồ thị vô hướng n đỉnh.


sau.

1 2 3 4 5 6
1
2
3
4
5
6 Lưu ý rằng ma trận kề của đồ thị có hướng không phải là ma trận đối
xứng.
Chú ý: Trên đây chúng ta chỉ xét đơn đồ thị. Ma trận kề của đa đồ thị
có thể xây dựng hoàn toàn tương tự, chỉ khác, là thay vì ghi 1 vào vị trí a[i,
j] nếu (i, j) là cạnh của đồ thị, chúng ta sẽ ghi k là số cạnh nối hai đỉnh i và
j.

Trong rất nhều vấn đề ứng dụng của lý thuyết đồ thị, mỗi cạnh e= (u, v)
của đồ thị được gán với một con số c(e) (còn viết là c (u, v)) gọi là trọng số
của cạnh e. Đồ thị trong trường hợp như vậy được gọi là đồ thị trọng số.
Trong đồ thị có trọng số, thay vì ma trận kề, để biểu diễn đồ thị ta dùng ma
trận trọng số.
C = c[i,j], i,j=1,2,…,n.
Với c(i, j)= c[i, j], nếu (i, j)  E và c[i, j] = nếu (i, j)  E
Trong đó số , tùy từng trường hợp cụ thể, có thể được đặt bằng một
trong các giá trị sau: 0, +, -.
Ưu điểm lớn nhất của phương pháp biểu diễn đồ thị bằng ma trận kề
(hoặc bằng ma trận trọng số) là để trả lời câu hỏi: hai đỉnh u, v có kề nhau
trên đồ thị hay không, chúng ta chỉ phải thực hiện một phép so sánh.

For evaluation only.