1、1第八 章 图 与网络分析学时安排： 68学时。教学 目的：让学生了解图论的基本知识，掌握用网络表示所研究问题、对象的基本属性及其解决方法。教学内容：基本概念、树、最短路、最大流、最小费用最大流等。教学难点：建立网络图的技巧和各种方法产生的思路。第八章 图与网络分析2l运筹学中的图与几何学中图的区别：运筹学中研究的图是日常生产和生活中经常碰到的各类图的抽象概括，它表明一些研究对象和这些对象之间的相互联系。如交通图是表明一些城镇及这些城镇之间的道路沟通情况。如果 用点表示研究的对象，用边表示这些对象之间的联系， 则图可以 定义为点和边的集合 。由此可知图是区别于几何学中的图。在几何图中，图中点的
2、位置、线的长度和斜率等十分重要。而这里 只关心有多少个点以及那些点之间有线相连。 （ 与线的长度、线是直线还是曲线无关 ）。 第八章 图与网络分析3历史上 解决的比较有名的问题：1、 “哥尼斯堡七桥问题 ”： 18世纪哥尼斯堡城中普雷 格尔河中有两个小岛，它们之间与两岸有七座桥相连。问从岸上某点出发，是否存在经过每座桥一次且仅一次，最后又回到原出发点的走法。（ 1736年欧拉发表了有关图论方面的第一篇文章，在该文章中解决了该问题。）C DAB BADC第八章 图与网络分析4第八章 图与网络分析2、 1847年，物理学家基尔霍夫为解决有关线性方程组而发展了 “树 ”的理论。他将网络中的电感、电容
3、、电阻等抽象为点和线，得到一简单的组合结构。这种结构便于运算，不必指明为何种元素。3、 1857年 ，凯莱研究饱和烃链 CnH2n+2的同分异构体时，又一次引入树状结构，例如， C4H10 。C C C C C CCC5第一节 基本知识第八章 图与网络分析一、图与网络的基本概念l图、网络图图 用点代表事物，用边代表事物之间的联系，则运筹学中研究的图是点与边关系的图。即点集 V=vi和 V中元素（节点）之间的连线所组成。用 m(G)=E（ A）表示图 G中边（弧）的数量；用 n(G)=V表示图 G中点的数量。网络图 若给图中边赋以具体的含义和权数（如距离、费用、容量等），这样的图称网络图。6第八
4、章 图与网络分析1、有向图与无向图：如果节点之间的连线皆是无方向的（称为边，边的集合记为 E），此时图G称为无向图，记为 G=（ V， E）；如果节点之间的连线有方向，即有向边（或称为弧，弧的集合记为 A） ，此时图 G称为有向图，记为 D =（ V， A）。用 m(D)=E（ A）表示图 D 中边（弧）的数量；用 n(D)=V表示图 D中点的数量。一个图是由点集 V=vi和 V中元素（节点）之间的连线所组成。7第八章 图与网络分析ABCDNFGMHG=（ V， E）V=A， B， C， D， N， F， G， H， ME=A,A,A,B,A,C,H,Mn(G)=9； m(G)=12边端点端点8第八章 图与网络分析MNFGD=（ V， A）V=M， N， F， GA=M,G,G,F,M,N,N,F弧始点终点9第八章 图与网络分析ABCDNFGMH2、如果一条边的两端点相同，此边称为环，两点之间多于一条边的，称为多重边。3、简单图：无多重边和环的图； 多重图：有多重边的图。10第八章 图与网络分析4、链：点、边交替的序列（ V1,e1, V2,e2, ,V i,ei) ；简单链： 边不重复， A, C, D, B, G,D,N; 初等链： 点、边不重复， A, B, G, F, N; 。ABCDNFGMH
