资源描述：
《网络优化模型ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第七章网络优化模型图与网络的基本概念最短路径问题最大流问题最小费用最大流问题哥尼斯堡七桥问题ABDC简捷表示事物之间的本质联系，归纳事物之间的一般规律ACDB在一个人群中，对相互认识这个关系我们可以用图来表示。(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e57.1图与网络的基本概念7.1图与网络的基本概念7.1.1图与网络的概念及分类1、图：图由点和边组成G=(V,E)点集V={vi}边集E={ei}vjvie每一条边和两个端点关联，一条边可以用两个端点表示（vi
2、，vj）边数：m(G)=
3、E
4、点数：n(G)=
5、V
6、7.1图与网络的基本概念无向边：有向边：无向图：由无向边构成的图有向图：由有向边构成的图2、无向图和有向图7.1图与网络的基本概念3、简单图和多重图环：e9多重边：e6和e7简单图：不含环和多重边多重图：含多重边判断下列哪些图是简单图，哪些图是多重图？7.1图与网络的基本概念7.1图与网络的基本概念4、次：以点v为端点的边数叫做点v的次，d(v)奇点：次为奇数偶点：次为偶数悬挂点：d(v)=1孤立点：d(v)=0定理7.1：任何图，Σd(vi)=2m定理
7、7.2：任何图，奇点有偶数个7.1图与网络的基本概念出次d+(vi)：有向图中，以vi为始点的边数入次d-(vi)：有向图中，以vi为终点的边数Σd+(v)=Σd-(v)=m7.1图与网络的基本概念5、连通图：链：无向图G=（V,E）前后相继的点边序列称为链初等链：点边序列中没有重复的点和重复边的链称为初等链(v1,e1,v2,e6,v4,e3,v3,e8,v5)7.1图与网络的基本概念5、连通图：圈：无向图G=（V,E）中起点和终点重合的链称为圈初等圈：没有重复点和重复边的链圈称为初等圈(v1,e1,v
8、2,e6,v4,e3,v3,e5,v1)7.1图与网络的基本概念5、连通图：对于有向图来说，如果链和圈中边的方向与有向图中所标方向相同，那么链就称为道路，圈就称为回路。连通图：任意两个点之间至少有一条链相连的图称为连通图7.1图与网络的基本概念6、子图与生成子图：子图：图G=(V,E)，E’是E的子集，V’是V的子集，且E’的边与V’的顶点想关联，G’=(V’,E’)是图G的一个子图。生成子图：若V’=V，则G’是G的生成子图7.1图与网络的基本概念6、网络：网络（赋权图）：由点、边以及与点边相关联的权数
9、所构成的图称为网络，记作N={V,E,W}v4v2v3v16215846v4v2v3v16215846无向网络有向网络7.1图与网络的基本概念7.1.2树的概念及性质1、树（T）：无圈的连通图称为树树叶分枝点7.1图与网络的基本概念7.1.2树的概念及性质2、树的性质性质7.1树中任意两点之间有且只有一条链。性质7.2如图G中任意两点之间，有且只有一条链，则该图G是一个树。性质7.3一个树，则m=n-1。性质7.4树中任意两个不相邻的点之间增加一条边，则形成唯一的圈。性质7.5一个树如果去掉任何一条边，该
10、图就不再连通。7.1图与网络的基本概念7.1.2树的概念及性质3、图的生成树生成树（支撑树）：图G的生成子图是一棵树，则称该树为G的生成树图G中属于生成树的边称为树枝，不属于生成树的边称为弦定理7.3：图G=（V,E）,有生成树的充分必要条件为G是连通图4、最小生成树：图G=(V，E)的生成树所有树枝上的权数的总和,称为生成树的权。权数最小的生成树称为最小生成树。寻找最小生成树的方法：避圈法、破圈法最小生成树权=115、根树有向树：若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树。根树：有向
11、树T，恰有一个结点入次d-(vi)=0，其余各点入次d-(vi)=1，则称T为根树根树中入次d-(vi)=0的点称为根出次d+(vi)=0称为叶其他点称为分枝点7.1图与网络的基本概念在根树中，若每个顶点的出次d-(vi)≤m，称这棵树为m叉树。若每个顶点的出次d-(vi)=m或0，则称这棵树为完全m叉树7.1图与网络的基本概念v2v3v7v1v8v4v5v66134105275934682求从v1到v8的最短路径标号：T标号（试探性标号）P标号（永久性标号）1、狄克斯托算法（Dijkstra）:标号法7
12、.2最短路问题V2V3V7V1V8V4V5V66134105275934682S={v1}P(v1)=0,T(vi)=∞T(v2)=2,T(v4)=1,T(v6)=3min{T(v2),T(v4),T(v6)}=min{2，1，3}=1P(v4)=1S={v1,v4}P(v1)=0L12=2L14=1L16=3P(v4)=1v2v3v7v1v8v4v5v66134105275934682S={v1,v4}P(v2)=2P(v1
