森林圖概念

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

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