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   -
   136   137   138   139   140   141   142   143   144   145   146