第八章_图与网络.ppt

第 八 章 图 与 网 络 分 析;第一节 图与网络的基本知识;1、18世纪哥尼斯堡城中普雷?格尔河中有两个小岛C、D，它们之间与两岸A、B共有七座桥相连。; 1736年，著名数学家欧拉把此问题简化为图，并发表了论文：“依据几何位置的解题方法”。; 2、1847年，物理学家基尔霍夫为解决有关线性方程组而发展了“树”的理论。他将网络中的电感、电容、电阻等抽象为点和线，得到一简单的组合结构。这种结构便于运算，不必指明为何种元素。; 5、1857年，英国数学家哈密尔顿发明了一个游戏，他用一个实心正12面体象征地球，正12面体的20个顶点分别表示世界上的20个城市，要求寻找一条路径：由某个城市出发每城市仅去一次，最终回到出发点。; 1、有向图与无向图：如果顶点之间的连线皆是无方向的（称为边，边的集合记为E），此时图G称为无向图，记为G=（V，E）； 如果顶点之间的连线有方向，即有向边（或称为弧，弧的集合记为A） ，此时图G称为有向图，记为 D =（V，A）。用m(D)=│E│（ │A│）表示图D 中边（弧）的数量；用n(D)=│V│表示图D中顶点的数量。;;;; 4、链：点、边交替的序列（V1,e1, V2,e2, …,Vi,ei) ； 简单链： 边不重复， {A, C, D, B, G,D,N}; 初等链： 点、边不重复， {A, B, G, F, N}; 。; 5、 圈：链上首、尾节点是同一节点时，称为圈； 简单圈：圈中没有重复的边；(A,B,G,B,D,C,A) 初等圈：既无重复点，也无重复边;(A,B,D,C,A); 路：链上边方向一致时，称为路； 回路：路上首、尾节点是同一节点时，称为回路。; 6、顶点的次：以点vi为端点的边数，记为d(vi )。 ; 出次：以点vi为始点的边数，用d+(vi )表示 。 入次：以点vi为终点的边数，用d-(vi )表示。 d+(vi ) +d-(vi )= d(vi )（用于有向图）。;偶点：d(v) = 偶数； 奇点：d(v)=奇数 悬挂点：d(v)=1； 悬挂边：与悬挂点连接的边； 孤立点：d(v)=0； 空图：E = ?，无边图;7、连通图：图G=（V,E）中任意两点间至少有一条链。 子图： G′=（V′,E′），其中 V′?V ，E′? E。;支撑（生成）子图：对于子图G′=（V′，E′），当V′=V时，且与图G=（V，E）的连通性相同的子图称为支撑子图，或生成子图。; 8、完全图：任意两点间皆有边相连的无向简单图。;9、基础图：将有向图中弧去掉其方向所形成的无向图，称为原有向图的基础图。 网络：给图的边或点赋予某些数量指标（我们称之为“权”），这种赋权图又称为网络。; 10、图的矩阵表示：邻接矩阵与权矩阵;;定理1 任何图中，顶点次的总和等于边数的2倍。; 次为奇数的点为奇点，次为偶数的点为偶点。奇点的集合可记为V1，偶点的集合记为V2。; ;定理：无向连通图G是欧拉图，当且仅当G中无奇点。;五、中国邮路问题(Chinese postman problem);;;第 二 节 树 ;1.树——连通且不含圈的无向图称为树。树中次为1的点为树叶，次大于1的点称为分枝点。;2.生成树——若图G的生成子图是一棵树，则称该树为G的生成树（或支撑树）。简称为图G的树。图中属于生成树的边叫树枝, 不在生成树的边叫弦。;3.最小生成树——连通图G=( V，E )，每条边上有非负权L( e )。一棵生成树所有树枝上权的总和称为这棵生成树的权。具有最小权的生成树称为最小生成树（最小支撑树），简称最小树。; 定理3 设图G（V，E）是一棵树，n(G)≥2，则G 中至少有两个悬挂点; （1）T无圈，且m=（n-1）。; （2）T连通，且m=（n-1）。 （3）T无圈，但每加一新边即得唯一一个圈。; （4）T连通，但任舍去一边就不连通。 (5 ) T中任意两点，有唯一链相连。; 定理5：图G有支撑树的充要条件为G是连通图。;;;;;;（1）避圈法——每步从未选的边中选取e，使它与已选边不构成圈，且e是未选边中的最小权边，直到选够（n-1）条边为止。;最小树权值为W(T) =5+2+3+2+3+4+6+1=26。;;第 三 节 最 短 路 问 题;二、