第 1 页 共 7 页 一、基本概念 1． 网络图 完成一项计划 （或工程），需进行许多工作 （或施工过程） 。 用一个箭杆表示一项工作，工作的名称写在箭杆上方， 工作的持续时间写在箭杆下方，箭尾表示工作开始，箭头表 示工作结束。箭头、箭尾衔接处画圆圈并编号，用箭尾、箭 头的号码作为这项工作的代号，这种表示方法称为双代号 法。 将所有工作（或施工过程）按顺序及相互关系从左向右 画成网络状图形，称为网络图。 2． 工作 工作（或施工过程）的划分根据需要可粗可细。 根据资源及时间的消耗，工作可分为： 工作——消耗时间，消耗资源。如扎筋、立模、浇混凝 土等； 间歇——只消耗时间，不消耗资源，包括工艺间歇及组 织间歇，如混凝土养护、油漆干燥、测量放样等。 虚工作——不消耗时间，也不消耗资源，仅为了表示工 作间的逻辑关系而引入，用虚箭杆表示。 箭杆的长度一般可不按比例绘制（除时间坐标网络图 外），方

1 图论与网络流理论 （Graph Theory and Network Flow Theory ） 高随祥 中科院研究生院专业基础课 学时 /学分： 60/3 本课程适合基础数学、应用数学、计算数学、运筹学与控制论、概率论与数 理统计各专业的硕士学位研究生作为专业基础课， 也可供物理学、化学、天文学、 地学、生物科学、计算机科学与技术、计算机软件、管理科学与工程以及通信、 信号等学科专业的硕士研究生选修。 主要讲授图论与网络流理论的基本概念、 方 法和定理，介绍该领域重要的问题以及典型的算法， 展示图论与网络流模型及方 法的广泛应用。 为学习者将来从事有关方面的理论研究打下基础， 也为进行应用 性研究提供一种有力的工具。 2 内容提要 第一章 图的基本概念 图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵。 路、圈与连通图；最短路问题。 树及其基本性质；生成树；最小生成树。