森林圖概念

第 1 頁 共 7 頁 一、基本概念 1． 網(wǎng)絡(luò)圖 完成一項計劃 （或工程），需進行許多工作 （或施工過程） 。 用一個箭桿表示一項工作，工作的名稱寫在箭桿上方， 工作的持續(xù)時間寫在箭桿下方，箭尾表示工作開始，箭頭表 示工作結(jié)束。箭頭、箭尾銜接處畫圓圈并編號，用箭尾、箭 頭的號碼作為這項工作的代號，這種表示方法稱為雙代號 法。 將所有工作（或施工過程）按順序及相互關(guān)系從左向右 畫成網(wǎng)絡(luò)狀圖形，稱為網(wǎng)絡(luò)圖。 2． 工作 工作（或施工過程）的劃分根據(jù)需要可粗可細。 根據(jù)資源及時間的消耗，工作可分為： 工作——消耗時間，消耗資源。如扎筋、立模、澆混凝 土等； 間歇——只消耗時間，不消耗資源，包括工藝間歇及組 織間歇，如混凝土養(yǎng)護、油漆干燥、測量放樣等。 虛工作——不消耗時間，也不消耗資源，僅為了表示工 作間的邏輯關(guān)系而引入，用虛箭桿表示。 箭桿的長度一般可不按比例繪制（除時間坐標網(wǎng)絡(luò)圖 外），方

1 圖論與網(wǎng)絡(luò)流理論 （Graph Theory and Network Flow Theory ） 高隨祥 中科院研究生院專業(yè)基礎(chǔ)課 學(xué)時 /學(xué)分： 60/3 本課程適合基礎(chǔ)數(shù)學(xué)、應(yīng)用數(shù)學(xué)、計算數(shù)學(xué)、運籌學(xué)與控制論、概率論與數(shù) 理統(tǒng)計各專業(yè)的碩士學(xué)位研究生作為專業(yè)基礎(chǔ)課， 也可供物理學(xué)、化學(xué)、天文學(xué)、 地學(xué)、生物科學(xué)、計算機科學(xué)與技術(shù)、計算機軟件、管理科學(xué)與工程以及通信、 信號等學(xué)科專業(yè)的碩士研究生選修。 主要講授圖論與網(wǎng)絡(luò)流理論的基本概念、 方 法和定理，介紹該領(lǐng)域重要的問題以及典型的算法， 展示圖論與網(wǎng)絡(luò)流模型及方 法的廣泛應(yīng)用。 為學(xué)習者將來從事有關(guān)方面的理論研究打下基礎(chǔ)， 也為進行應(yīng)用 性研究提供一種有力的工具。 2 內(nèi)容提要 第一章 圖的基本概念 圖的基本概念；二部圖及其性質(zhì)；圖的同構(gòu)；關(guān)聯(lián)矩陣與鄰接矩陣。 路、圈與連通圖；最短路問題。 樹及其基本性質(zhì)；生成樹；最小生成樹。