Page 141 - Bí Mật Toán Học
P. 141
Hình 2
1. Chọn một cạnh có chi phí nhỏ nhất trong hình vẽ. Bỏi vì phí của
DC là 3 trăm đồng, nhỏ nhất trong tất cả các chi phí, cho nên chọn cạnh
DC, xem hình 2.
2. Trong hình 1 bỏ đi cạnh còn lại của cạnh đã chon, chọn một cạnh
đáp ứng hai điều kiện dưới đây, cho vào trong h'mh 2:
(1) Là cạnh sau khi thêm vào hình 2 không sinh ra đường quay lại;
(2) Cạnh này là cạnh có chi phí nhỏ nhất trong những cạnh còn lại.
Do hình 2 lúc này chỉ có một cạnh, thêm vào bất kỳ cạnh nào cũng
không sinh ra đường quay lại, chúng ta chọn cạnh có chi phí nhỏ nhất
trong những cạnh còn lại, tức là chọn AB thêm vào hình 2. Cạnh thêm
vào tiếp theo là AC, chi phí của nó là 7, lại cũng không khiến cho hình 2
nảy sinh đường quay lui. Do cạnh BD không đáp ứng được 2 yêu cầu
trên nên ta loại, xét Ctạiih CE, chi phí của nó nhỏ nhất, lại không làm nảy
sinh đưòng quay lui, thêm CE vào trong hình 2. Kỳ thực chi phí của cạnh
AE cũng là 10, cho nên cũng có thể thêm cạnh AE, vậy trong AE và EC
chỉ có thể chọn một cạnh thêm vào, nếu đồng thòi thêm vào thì không
được, sẽ khiến cho hình 2 nảy sinlì đường quay lui.
N ế u th ê m các c ạ n h c ò n lại AE, BC, AD, BE đ ề u sẽ k h iế n h ìn h 2
n ả y s in h đ ư ờ n g q u a y lui, x e m ra k h ô n g cò n Ccạnh n à o có th ể th ê m v à o
h ìn h 2 n ữ a
3. Nếu kliông tìm thấy cạnh thoả mãn yêu cầu, thì chúng ta tìm tất cả
các cạnli, cộng chi phí trên các cạnh vào, chmh là giá sửa đường thấp nhất
Thế thì tổng chi phí trong hình 2 là 4+7+3+10=24 triệu đồng.
Mạng đường sắt này không những nối liền 5 thành phố, mà chi phí
còn thấp nhất.
- 141 -
