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
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 nhau và phải
được thực hiện theo một thứ tự nào đó cho đến khi hoàn thành toàn bộ các hoạt
động. Hoạt động được hiểu như là một việc đòi hỏi thời gian, và nguyên liệu
(Resource) để hoàn thành. Trước kia để điều hành dự án người ta thường dùng biểu
đồ Gantt (Gantt bar chart), là một đồ thị gồm các đường kẻ ngang, biểu thị điểm
khởi công và kết thúc hoạt động. Nhược điểm của biểu đồ là không xác định được
quan hệ giữa các hoạt động, nên không áp dụng được cho các dự án lớn (largescale project), đòi hỏi đặt kế hoạch (planning), điều hành thực hiện (scheduling) va
kiểm tra (controlling) một cách hệ thống và hiệu quả, thậm chí phải tối ưu hoá hiệu
quả (về thời gian và tiết kiệm nguyên liệu). Vì vậy, gần như đồng thời vào năm
1956-1958, hai phương pháp kế hoạch, điều hành và kiểm tra dự án đã ra đời.
Phương pháp đường găng hoặc phương pháp đường tới hạn (Critical path method,
viết rắt là CPM) được E.I.du Pont de Nemous và công ty xây dựng của ông đưa ra.
Phương pháp thứ hai có tên là Kỹ thuật xem xét và đánh giá dự án (Project
evaluation and review technique, viết tắt là PERT) là kết quả nghiên cứa của một
công ty tư vấn theo đặt hàng của hải quân Mỹ, dùng để điều hành các hoạt động
nghiên cứu và phát triển chương trình tên lửa đối cực. Hai phương pháp được hình

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ý dự án lập được sơ đồ mạng lưới như
H.1.1. Các số bên cạnh cung là thời gian thực hiện hoạt động đó.
Qua sơ đồ mạng lưới H.1.1 ta thấy rõ mối quan hệ giữa các hoạt động về thời
gian. Chẳng hạn hoạt động (6, 8) là trát ngoài-phải sau (4, 6) là lợp mái, nhưng
độc lập với (5, 7) là chỉnh tường trong. Cũng vậy (4, 7) độc lập với (4, 5) và (5, 7).
Ở đây có hai hoạt động giả (dummmy activity) với thời gian để thực hiện bằng 0
được đưa vào để đảm bảo qui tắc sơ đồ.
Cung giả (11, 12), ký hiệu bởi đường đứt đoạn, đưa vào để đảm bảo qui tắc
không có hai hoạt động cùng biến cố bắt đầu và kết thúc, tức là không có 2 cung
có cùng gốc và ngọn (tức là đồ thị đơn). Việc sơn tường trong và làm sàn có cùng
biến cố dầu là nút 9, tức là biến cố lát ván tường xong, và biến cố cuối là nút 12
(làm sàn và sơn tường xong, bắt đầu hoàn thiện trong). Do đó ta phải thêm nút 11
là biến cố giả và cung giả (11, 12).
Cung giả (5, 8) để chỉ rằng hoạt động (4, 5) phải hoàn thành trước khi bắt đầu
hoạt động (8, 10) (nếu bỏ cung giả này thì thời điểm làm hai việc là độc lập).
Cung giả này là phục vụ cho qui tắc sơ đồ mạng lưới phải thể hiện đủ quan hệ
thứ tự cần có.

Trang:2


Nếu quan hệ thời gian có dạng: việc x2 bắt đầu khi xong 1/3 việc x1, việc x3
bắt đầu khi xong một nửa x1, thì ta phải thêm các nút đánh dấu các biến cố xong
1/3x1 và xong 1/2x1 đó như ở H1.2.

Khởi công


Ép ván lát tường

4

5

Sơn tường

0

Hoàn thiện ngoài

2

Hoàn thiện trong
6

Kết thúc
Hình 1.1
Tóm lại: Sơ đồ mạng lưới phải là một đồ thị có hướng, đơn, liên thông, không có
khuyên (tức là cung có gốc và ngọn cùng là một nút), không có chu trình có hướng
(directed cycle), có nút khởi công và nút kết thúc.

Trang:3


x1

x1

đ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à Lj. Đối lại với Ej, các Lj đượ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ì En =
Ln, ở thí dụ H.1.1 là E13 = L13 = 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à :
Lj =Li - tji,

Trang:4


Tức là thời điểm muộn của nút ngay sau nó trừ đi thời gian thực hiện hoạt động nối
hai nút. Các biến cố 12, 11, 10, 8, 7, 6, 3, 2 và 1 ở H.1.1 là trường hợp này. Nếu có
nhiều cung ra khỏi biến cố, thì theo định nghĩa ta có :
Lj =
Ở đây min theo các nút i ngay sau j và tji là thời gian thực hiện hoạt động nối (j, i).
Các nút 9, 5, 4 là ở trường hợp này, chẳng hạn :
L9 = min {L11 – t9 11, L12 – t9 12} = min (38 – 4, 38 - 5) = 33
Hãy chú ý sự ‘’đối xứng ‘‘ của quá trình tính Ei và Lj. Các Lj đượ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ữ.
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ó : di = Li – Ei. Thời gian dự trữ (slack hoặc float) của hoạt
động được chia làm hai loại. Thời gian dự trữ chung (total slack hoặc total float)
của hoạt động (i, j) là :
TFij = Lj – Ei – tij.
TFij chỉ là thời gian có thể trì hoãn của hoạt động (i,j) mà không ảnh hưởng đến
thời điểm kết thúc cả dự án. Vì nó bằng thời gian tối đa dành cho hoạt động (i, j) là
Lj - Ei trừ đi thời gian để
thực hiện là tij. Thời gian dự trữ độc lập (free float hoặc free slack), ký hiệu là
FFij, cũng là ký hiệu thời gian dành cho (i, j) và thời gian thực hiện là tij, nhưng

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 đường găng được tô đậm.
Một thí dụ dự án có nhiều đường găng là sơ đồ ở H.1.3 nhưng với t46 thay từ 6
thành 10. Khi đó thời gian dự trữ của các hoạt động (6, 8), (8, 10) và (10, 13) và
thời gian dự trữ của các biến cố 6, 8 và 10 đều thay từ 4 thành 0. Lúc này đường 1
–> 2 –> 3 –> 4 –> 6 –> 8 –> 10 –> 13 là đường găng thứ hai.
Các chỉ tiêu thời gian của dự án ở H.1.3 được ghi vào bảng 1.1
Biến cố Thời điểm sớm
gian dự trữ chung
1 0 0 0 (1, 2)
2 2 2 0 (2, 3)
3 6 6 0 (3, 4)
4 16 16 0 (4, 5)
5 20 20 0 (4, 6)
6 22 26 4 (4, 7)
7 25 25 0 (5, 7)
8 29 33 4 (6, 8)
9 33 33 0 (7, 9)
10 38 42 4 (8, 10)
11 37 38 1 (9, 11)
12 38 38 0 (9, 12)
13 44 44 0 (10, 13)
(12, 13)

Thời điểm muộn Thời gian dự trữ Hoạt động

Thời




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 TFp, 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 = ,
ở đây là độ dài đường găng và là độ dài đường P, là tổng thời gian thực hiện hoạt
động trên đường P.
Hệ số găng (critital coefficient) biểu thị mức độ căng thẳng về thời gian của một
đường P nối nút khởi công và kết thúc, không phải đường găng G, được định nghĩa
là
,
ở đây TPG là độ dài quãng đường (tức là một phần của đường) mà P trùng với G.
Rõ ràng O < KP < 1 và KP càng gần 1 thì thời hạn thực hiện các hoạt động không
găng trong P càng chặt chẽ.
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 EC68 = E6 + t68 = 22 + 7 = 29 = E8, EC10, 13 = 40 < E13 = 44. Thời
điểm khởi công muộn LS46 = L6 – t46 = 26 – 6 = 20 > L4 = 16. Bây giờ giả sử P
là đường đi 1 –> 2 –> 3 –> 4 –> 5 –> 6 –> 8 –> 10 –> 13 thì TP = =40
Nên thời gian dự trữ của P là TG – TP = 44 – 40 = 40. Hệ số găng là
KP = (không có quãng chung với đường găng). Gọi Q là đường 1 –> 2 –> 3 –> 4
–> 7 –> 9 –> 12 –> 13 thì TQ = 42, KQ = . Ta thấy mặc dù TQ > TP 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ó

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
1
0
4
11
0
8

lùi lại khoảng 1 đến 3 chẳng hạn, thì ảnh hưởng đến hoạt động (2, 4). Mặc dù có
FF24 = TF24 nhưng lúc này có chỉ còn được xê dịch thực hiện trong khoảng từ 3
đến 6.

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 FFij =
TFij. 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,

Trang:9


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
(1, 2) 0
(1, 3) 5
(2, 4) 0
(3, 4) 7
(3, 5) 3

Số nhân công
(4, 6) 2
(4, 7) 1
(5, 6) 2
(5, 7) 5
(6, 7) 6

Hoạt động



(5, 6)

H .I.6 (a)
(4, 7)
(3, 5)
(3, 4)

(5, 7)

(1, 3)

(4, 6)
(5, 6)

H .I.6 (b)

Trang:11

(6, 7)


Hình 1.7
IV. Hoàn thành sớm dự án.
Trên đây đã xét thời điểm hoàn thành dự án là cố định và xác định các đường
găng, phải thực hiện chặt chẽ để dự án hoàn thành đúng thời gian qui định. Nếu
muốn giảm thời gian hoàn thành dự án thì làm thế nào ? Ta cũng sử dụng đường
găng, nhưng phải dựa vào kỹ thuật và công nghệ, chứ không phải quản lý bằng
toán học được nữa. Cụ thể là phải dùng công nghệ mới, tăng vật tư, công nhân ..

độ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 te 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 te 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
.
(1.1)
Điều này đúng cho nhiều biến ngẫu nhiên hay gặp.
Giả thiết 2. Phân bố xác suất của mỗi thời gian hoạt động đêøu là phân bố beta
(beta distribution).
Ta hãy nhắc lại vài kiến thức xác suất. Mỗi đại lương ngẫu nhiên x có hai hàm
quan trọng nhất. Hàm mật độ xác suất (probability density fuction) f(x), a  x  b,
và hàm phân bố tích luỹ (cumulative distribution function) F(X), gọi là hàm phân
bố. Ở đây giả thiết là x chỉ lấy giá trị trong [a, b] . Ta có các quan hệ sau
ở đây xe 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,
,
(1.2)
ở đây ,  là tham số, (.) là hàm đặc biệt gamma và B(., .) là hàm đặc biệt beta,
được định nghĩa bằng tích phân phụ thuộc tham số
f(x)

thuộc vào phân bố của từng biến ngẫu nhiên).
Trở lại mô hình ngẫu nhiên điều hành dự án. Để tính kỳ vọng te của thời gian
hoạt động, người ta giả thiết là điểm giữa chiếm tỷ trọng bằng nửa điểm hợp lý
nhất m. Khi đó
(II.3)
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 te Phương sai 2
(1, 2)
(2, 3)
(3, 4)
(4, 5)
(4, 6)
(4, 7)
(5, 7)
(6, 8)
(7, 9)
(8, 10)
(9, 11)
(9, 12)

Trang:14


(10, 13)
(12, 13) 1

5
10
9
10
11
9
17
4
7
3
9

2

4
10
4
6
7
5
7
8
9
4
5
2
6
1

Trang:16

cách áp dụng thực tế là dùng các kỳ vọng của các biến, rồi áp dụng mọi tính toán
và lý luận ở các mục trước vào các kỳ vọng, thay cho các biến tất định.
Ở Thí dụ V.1 kỳ vọng và phương sai của thời gian dự án là 44 và 9, vì đường
găng là 1 –> 2 –> 3 –> 4 –> 5 –> 7 –> 9 –> 12 –> 13 .
Bây giờ ta xét vấn đề quan trọng là tính xác suất để dự án hoàn thành trước
một thời hạn bắt buộc (deadline). Theo định lý giới hạn trung tâm, thời gian dự án
là biến ngẫu nhiên có phân bố chuẩn. Do đó ta tính được xác suất P(x  X),
thường được tính sẵn để tra theo bảng. Chẳng hạn Bảng A1 ở cuối sách cho biết P
{x  xe + K}, ở đây  là độ lệch chuẩn. Do đó K là đơn vị lệch chuẩn.

Trang:17


Thí dụ, hãy tính xác suất để thời gian xây nhà ở Thí dụ V.1 không quá 47 ngày.
Ta thấy 47 = 44 + 3.1 = xe + K nên K = 1. Theo bảng thì P {x  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 te 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
te 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(i) thì Var(i) quy ước lấy lượng của đường có tổng các 2
dái nhất.
Bây giờ hãy tính xác suất để biến cố i xong trước thời gian bắt buộc Ti cho
trước. Theo định lý giới hạn trung tâm i tuân theo phân bố chuẩn, ta chỉ việc tra
bảng các xác suất ứng với phân bố chuẩn để tính P{i  Ti}. Cụ thể, để tra bảng,

biến quyết định (decision variable) của bài toán mà ta cần tính. Gọi Sij là độ xiên,
tức là hệ số góc đường thẳng biểu thị đường cong thời gian – cước phí , tức là:
.
Gọi Kij là tung độ điểm đường thẳng cắt trục tung. Khi đó cước phí của hoạt
động (i, j) tương ứng với thời gian hoạt động (i, j) ứng với thời gian hoạt động xij
rõ ràng là:
Bài toán: Chọn các xij để thời gian dự án không quá thời hạn bắt buộc 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:
Đưa vào các biến bổ xung yk là thời điểm sớm Ek của biến cố k. Khi đó quan
hệ giữa các biến theo Mục 4.2 là
,
(1, 4)
ở đây max lấy theo các biến cố j ngay trước k, tức là có hoạt động nối (j, k). Ký
hiệu yk = Ek, tjk = xjk và viết lại (4, 4) ta được
yi + xjk – yk  0
(số ràng buộc là số các biến cố ngay trước k). Gọi 1 là nút xuất phát và n là nút kết
thúc dự án thì
y1 = 0, yn T.
Ở mục tiêu thì Kij là hằng. Tóm lại ta được quy hoạch tuyến tính
Để đưa về quy hoạch tuyến tính dạng chuẩn ta làm như sau. Đổi biến xij = dij
+ x’ij thì ràng buộc xij  dij trở thành ràng buộc dấu x’ij  0. Thêm ràng buộc
hình thức yi  0, i. Ràng buộc này tự nhiên thoả do y1 = 0 và yj  yi + dij +
X’ij.
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ơ đồ

Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này.
Chúng ta phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nối hai
đỉnh nào đó của đồ thị. Để có thể hình dung được tại sao lại cần đến các loại đồ thị
khác nhau, chúng ta sẽ nêu ví dụ sử dụng chúng để mô tả một mạng máy tính. Giả
sử ta có một mạng gồm các máy tính và các kênh điện thoại (gọi tắt là kênh thoại)
nối các máy tính này.
Định nghĩa 1: Đơn đồ thị vô hướng G = (V,E) bao gồm V là tập hợp các đỉnh và E
là tập hợp 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.
Trong trường hợp giữa hai máy tính nào đó thường xuyên phải truyền tải
nhiều thông tin người ta phải nối hai máy tính này bởi nhiều kênh thoại.
Định nghĩa 2: Đa đồ thị vô hướng G = (V,E) bao gồm 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ác nhau của V gọi là các cạnh. Hai
cạnh e1 và e2 đượ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

Trang:20


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:
Đị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à

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:
Định lý 1: Giả sử G = (V,E) là đồ thị vô hướng với m cạnh. Khi đó.

Trang:21


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à 3n.
Hệ quả: Trong đồ thị vô hướng, số đỉnh bậc lẻ (nghĩa là có bậc là số lẻ) là một số
chẵn.
Chứng minh: Thực vậy gọi O và U tương ứng là tập đỉnh bậc lẻ và tập
đỉnh bậc chẵn của đồ thị. Ta có:
Do deg(v) là chẵn với v là đỉnh trong U nên tổng thứ hai trong vế phải ở trên
là số chẵn. Từ đó suy ra tổng thứ nhất (chính là tổng bậc của các đỉnh bậc lẻ) cũng
phải là số chẵn, do tất cả các số hạng của nó là số lẻ, nên tổng này phải gồm một số
chẵn các số hạng. Vì vậy, số đỉnh bậc lẻ phải là số chẵn. Ta xét các thuật ngữ tương
tự cho đồ thị có hướng.
Định nghiã 3: Nếu e = (u, v) là cung của đồ thị có hướng G thì ta nối hai đỉnh u và
v là kề nhau, và nói cung (u,v) nối đỉnh u với đỉnh v hoặc cũng nói cung này là đi
ra khỏi đỉnh u và đi vào đỉnh v. Đỉnh u(v) sẽ được gọi là đỉnh đầu (cuối) của cung
(u, v).
Tương tự như khái niệm bậc, đối với đồ thị có hướng ta có khái niệm bán bậc
ra (vào) của một đỉnh.

Định nghĩa 4: Ta gọi đồ thị con của đồ thị G= (V,E) là đồ thị H = (W,F) trong đó W
 V và FE.
Trong trường hợp đồ thị là liên thông, nó sẽ rã ra thành một số đồ thị con liên
thông đôi một không có đỉnh chung. Những đồ thị con liên thông như vậy ta sẽ gọi
là các thành phần liên thông của đồ thị.
Định nghĩa 5: Đỉnh v được gọi là đỉnh rẽ nhánh nếu việc loại bỏ v cùng với các
cạnh liên thuộc với nó khỏi đồ thị làm tăng số thành phần liên thông của đồ thị.
Cạnh e được gọi là cầu nếu việc loại bỏ nó khỏi đồ thị làm tăng số thành phần liên
thông của đồ thị.
Định nghĩa 6: Đồ thị có hướng G= (V,A) được gọi là liên thông mạnh 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.

6

5

2
1

5

4
3

6
G1

Hình 1: Đồ thị vô hướng G và Đồ thị có hướng G1
Cá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.
2. Tổng các phần tử trên dòng i (cột j) của ma trận kề chính bằng bậc của đỉnh i
(đỉnh j).
3. Nếu ký hiệu aijp, i,j = 1, 2,…, n. Là các phần tử của ma trận Ap = A.A….A. p là
thừa số, khi đó aijp, i,j = 1, 2,…, n. cho ta số đường đi khác nhau từ đỉnh i đến
đỉnh j qua p –1 đỉnh trung gian.
Ma trận kề của đồ thị có hướng được định nghĩa một cách hoàn toàn tương tự.
Thí dụ 2: Đồ thị có hướng G1 cho trong hình 1 có ma trận kề là ma trận sau.


Trong cách biểu diễn đồ thị bởi danh sách cạnh (cung) chúng 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ỗi cạnh (cung)
e = (x, y) của đồ 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 chúng 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ạch của đồ thị).
Chú ý: 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ạch.
2.3. 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 được sử dụng.
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ó, mà ta sẽ ký hiệu là Ke(v), tức là Ke(v)={uV: (v, u)  E}

Trang:25