管理決策之網絡分析與應用培訓課件(ppt 38頁)

內容摘要
圖論(GraphTheory)
是運籌學的一個分支，已廣泛應用在物理學、化學、控製論、信息論、科學管理、計算機等各個領域中。
網絡分析（NetworkAnalysis）
作為圖論的一個重要內容，已成為對各種係統進行分析、研究和管理的重要工具。本章主要介紹運輸問題、最短路問題、最小支撐樹問題、最大流問題，以及網絡計劃評審與優化問題。
圖與網絡的基本概念
圖論中的圖，是反映現實世界中具體事物及其相互關係的一種抽象工具,它比地圖、分子結構圖、電路圖等更抽象。
圖的定義：簡單的說，一個圖是由一些點(Vertices)及點間的連線(Edges)所組成的。點可以作為現實世界中事物的抽象，而點間的連線表示事物間的關係。
無向圖：如果一個圖由點及邊所構成，則稱之為無向圖，記為G=(V，E)。其中，V是一個有限非空的點集合，稱為G的點集，一般表示為V={v1，v2，…，vn}；E是一個邊集合，稱為G的邊集，一條連接vi和vj的邊一般表示為一個無序對e=（vi，vj）。
有向圖：如果一個圖由點及弧所構成，則稱之為有向圖，記為D＝(V，A)。其中，V是點的集合；A是弧的集合，一條從vi連接到vj的弧一般表示為一個有序對a＝(vi，vj)。

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