资源描述：
《管理运筹学 第七章 网络优化模型课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第七章网络优化模型图与网络的基本概念+最小生成树最短路径问题最大流问题哥尼斯堡七桥问题ABDC简捷表示事物之间的本质联系，归纳事物之间的一般规律ACDB在一个人群中，对相互认识这个关系我们可以用图来表示。(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e57.1图与网络的基本概念4当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以
2、用下图来表示，可见图论中的图与几何图、工程图是不一样的。(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e55a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图11-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。7.1图
3、与网络的基本概念7.1.1图与网络的概念及分类1、图：图由点和边组成G=(V,E)点集V={vi}边集E={ei}vjvie每一条边和两个端点关联，一条边可以用两个端点表示（vi，vj）边数：m(G)=
4、E
5、点数：n(G)=
6、V
7、7.1图与网络的基本概念无向边：有向边：无向图：由无向边构成的图有向图：由有向边构成的图2、无向图和有向图7.1图与网络的基本概念3、简单图和多重图环：e9多重边：e6和e7简单图：不含环和多重边多重图：含多重边判断下列哪些图是简单图，哪些图是多重图？7.1图与网络的基本概念7.1图与网
8、络的基本概念4、次：以点v为端点的边数叫做点v的次，d(v)奇点：次为奇数偶点：次为偶数悬挂点：d(v)=1孤立点:d(v)=0定理7.1：任何图，Σd(vi)=2m定理7.2：任何图，奇点有偶数个7.1图与网络的基本概念出次d+(vi)：有向图中，以vi为始点的边数入次d-(vi)：有向图中，以vi为终点的边数Σd+(v)=Σd-(v)=m7.1图与网络的基本概念5、链、圈、路、回路、连通图：链：无向图G=（V,E）前后相继的点边序列称为链初等链：点边序列中没有重复的点和重复边的链称为初等链(v1,e1,v2,
9、e6,v4,e3,v3,e8,v5)7.1图与网络的基本概念圈：无向图G=（V,E）中起点和终点重合的链称为圈初等圈：没有重复点(除起点和终点外)和重复边的圈称为初等圈(v1,e1,v2,e6,v4,e3,v3,e5,v1)7.1图与网络的基本概念对于有向图来说，如果链和圈中边的方向与有向图中所标方向相同，那么链就称为道路，圈就称为回路。连通图：无向图中，任意两个点之间至少有一条链相连的图称为连通图7.1图与网络的基本概念6、子图与生成子图：子图：图G=(V,E)，E’是E的子集，V’是V的子集，且E’的边与V’
10、的顶点想关联，G’=(V’,E’)是图G的一个子图。生成子图：若V’=V，则G’是G的生成子图7.1图与网络的基本概念6、网络：网络（赋权图）：由点、边以及与点边相关联的权数所构成的图称为网络，记作N={V,E,W}v4v2v3v16215846v4v2v3v16215846无向网络有向网络7.1图与网络的基本概念7.1.2树的概念及性质1、树（T）：无圈的连通图称为树树叶分枝点7.1图与网络的基本概念7.1.2树的概念及性质2、树的性质性质7.1树中任意两点之间有且只有一条链。性质7.2如图G中任意两点之间，有
11、且只有一条链，则该图G是一个树。性质7.3一个树，则m=n-1。性质7.4树中任意两个不相邻的点之间增加一条边，则形成唯一的圈。性质7.5一个树如果去掉任何一条边，该图就不再连通。7.1图与网络的基本概念7.1.2树的概念及性质3、图的生成树生成树（支撑树）：图G的生成子图是一棵树，则称该树为G的生成树图G中属于生成树的边称为树枝，不属于生成树的边称为弦定理7.3：图G=（V,E）,有生成树的充分必要条件为G是连通图4、最小生成树：图G=(V，E)的生成树所有树枝上的权数的总和,称为生成树的权。权数最小的生成树称
12、为最小生成树。寻找最小生成树的方法：避圈法、破圈法最小生成树权=115、根树有向树：若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树。根树：有向树T，恰有一个结点入次d-(vi)=0，其余各点入次d-(vi)=1，则称T为根树根树中入次d-(vi)=0的点称为根出次d+(vi)=0称为叶其他点称为分枝点7.1图与网络的基本概念在根树中，若每个顶点的出次d-(
