企業運籌學--圖與網絡理論講義(ppt 81頁)

企業運籌學--圖與網絡理論講義目錄：
一、圖的概念
二、網絡概念
三、網絡最短樹問題
四、網絡最短路問題
五、網絡最大流問題

 

企業運籌學--圖與網絡理論講義內容提要：
圖的概念
所謂圖，就是頂點和邊的集合，點的集合記為V，邊的集合記為E，則圖可以表示為：G＝（V，E），點代表被研究的事物，邊代表事物之間的聯係，因此，邊不能離開點而獨立存在，每條邊都有兩個端點。
在畫圖時，頂點的位置、邊和長短形狀都是無關緊要的，隻要兩個圖的頂點及邊是對應相同的，則兩個圖相同。
……

在有些圖中，邊是沒有方向的，即[u,v]=[v,u]，這種圖稱為無向圖。
而有些關係是不對稱的，例如父子關係、上下級關係、加工工序的先後順序等都具有單向性，用圖來表示這些關係時，得到的邊是具有方向的，用帶箭頭的線來表示，稱為弧。
從頂點u指向υ的弧a，記作＝a=(u,v),(u,v)≠(v,u)，其中u稱為a的起點，v稱為a的終點，這樣的圖稱為有向圖。仍以V表示點的集合，以A表示弧的集合，則有向圖表示為D＝（V，A）
……

最短樹問題的一般提法是：選取網絡中的部分圖，使得網絡連通，且使總權數最短。
在實際應用中，經常碰到需要求一個賦權連通圖的最短樹的問題。例如，用節點表示城市，用邊表示可以在兩個城市之間架設光纜，邊上的權表示光纜的長度，試求應如何架設光纜，才能使任意兩城市之間均由光纜相通，且使光纜的總長度最短。
求最短樹的方法，依據的是樹的特點，即無圈和連通，加上最短的要求，方法主要有兩種：一種稱為破圈法，一種稱為生長法。

..............................