资源描述：
《图与网络分析(1-4).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图与网络分析Graph&NetworkAnalysis第六章图是最直观的模型1知识点要求了解图与树的基本概念；掌握最小部分树的求法：避圈法和破圈法掌握最短路问题连种算法：Dijkstra算法和矩阵算法掌握网络最大流及最小割的概念及其求法掌握网络计划技术方法2主要内容图的基本概念与模型树图与图的最小部分树最短路问题中国邮政问题网络的最大流网络计划技术方法3图的基本概念与模型第一节4在生产和日常生活中，我们经常碰到各种各样的图：公路或铁路交通图、管网图、通讯联络图等。运筹学中研究的图是上述各类图的抽象概括，它表明一些研究对象和这些对象之间的相互联
2、系。如交通图是表明一些城镇及这些城镇之间的道路沟通情况；管网图是表明供应源、用户、中间加压站之间管网的联系情况等。5图的概念Graph图由点和线构成。点代表所研究的对象线代表对象之间的关联性质V8V4V2V1V7V9V6V5V3e3e1e4e2e8e7e6e12e9e10e11e13e5图aV2V1V4V3V6V5图b6图的分类无向图：图中的线不带表示关联方向的箭头，线称为“边”,如图a有向图：图中的线带表示关联方向的箭头，线称为“弧”,如图bV8V4V2V1V7V9V6V5V3e3e1e4e2e8e7e6e12e9e10e11e13e5图a
3、V2V1V4V3V6V5图b7图的定义与表达点：表示研究的对象，边：表示这些对象之间的联系，图G：为点和边的集合，记作G={V，E}式中V是点/vertex的集合，E/edge是边的集合。8G与几何学中的图的区别在几何学中，图中点的位置、线的长度和斜率等都十分重要，而G={V，E}只关心图中有多少个点以及哪些点之间有线（边）相连（点的数量及点之间的关系）。9网络图——N NetGraph如果给图G={V，E}中的点和边赋以具体的含义和权数，如距离、费用、容量等，把这样的图称为网络图，记作N。图和网络分析的方法已广泛用于物理、化学、控制论、信息
4、论、计算机科学和经济管理等各个领域。10点与边Vertex&Edge图G={V，E}中的点用v表示（又称顶点或节点），边用e表示。每条边可用它所连接的点表示，如记作e1=[v1,v1]e3=[v1,v3]或e3=[v3,v1]11点的次数degree，特殊的点与某一个点vi相关联的边的数目称为点vi的次，记作d(vi)。图a中d(v1)=5,d(v3)=4,d(v5)=1。次为奇数的点称作奇点odd次为偶数的点称作偶点even次为0的点称作孤立点isolatedvertex次为1的点称作悬挂点pendentvertex（从图找出以上各类点）V
5、8V4V2V1V7V9V6V5V3e3e1e4e2e8e7e6e12e9e10e11e13e5图a12端点，关联边，相邻EndVertex,IncidentEdge&AdjacentEdge若有边e可表示为e=[vi,vj]，称vi和vj是边e的端点，称e为点vi或vj的关联边。若点vi、vj与同一条边关联，称点vi、vj相邻；若边ei、ej具有公共的端点，称边ei和ej相邻。13V2V1V4V3V6V5图b特殊的边，简单图如果边e的两个端点相重，称该边为环loop，如图中边e1为环。如果两个点之间边多于一条，称为具有多重边multi-edg
6、e，如图中的e4和e5与悬挂点相邻的边为悬挂边。对无环、无多重边的图称作简单图simplegraph。14链，路link,path点和边的交替序列为链{v4,e4,v2,e1,v1,e3,v3,e2,v2,e1}首尾相连的链为圈/闭链loop，如{v2,e1,v1,e3,v3,e2}无重复边的链为简单链{v4,e4,v2,e1,v1,e3,v3,e13,v6,e8,v1,e7,v8}无重复点的简单链为路{v4,e4,v2,e1,v1,e3,v3,e13,v6,e9,v8}首尾相连的路为回路circuit，{v1,e3,v3,e13,v6,e8
7、,v1}V8V4V2V1V7V9V6V5V3e3e1e4e2e8e7e6e12e9e10e11e13e5图a15V2V1V4V3V6V5图b连通图若在一个图中，如果每一对顶点之间至少存在一条链，称这样的图为连通图connectedgraph否则称不连通图disconnectedgraph。V8V4V2V1V7V9V6V5V3e3e1e4e2e8e7e6e12e9e10e11e13e5图aV2V1V4V3V6V5图b16子图，部分图sub-graph,componentgraph图G1={V1，E1}和图G2={V2，E2}如果有和，称G1是G
8、2的一个子图。若有V1=V2，，则称G1是G2的一个部分图。图6-2(a)是图6-1的一个子图，图6-2(b)是图6-1的部分图。注意部分图也是子图，但子图不一定是
