图与网络-西安电子科技大学经济管理学院.pptx

该【图与网络-西安电子科技大学经济管理学院 】是由【小屁孩】上传分享，文档一共【101】页，该文档可以免费在线阅读，需要了解更多关于【图与网络-西安电子科技大学经济管理学院 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。运筹学图与网络分析2021/10/101第十章??????图与网络赵玮2021/10/102主要内容:(一)Bellman最优化原理(二)Dijustra算法(双括号法)(三)通信线路布施问题(四)(一)基本概念与理论(二)Kruskal算法(加边法、破圈法)(三)丢边法(破圈法)2021/10/103主要内容:(一)基本概念(二)(一)基本概念(二)求解算法2021/10/104§:一个无向图(简称为图)G是一个有序的二元组,记为G=(V,E)。其中V={V1…Vn}称为G的点集合,E=(eij)称为G的边集合,evj为连接VV与Vj的边。2021/10/105若N和E均为有限集合,则称为G为有限图,否则称无限图。若G中既没有有限回路(圈),也没有两条边连接同一对点,则称G为简单图。如右图之(a),右图之(b)不是简单图。若G为简单图,且G中每个点对之间均有一条边相连,则称G为完全图。如图(a)是简单图,但不是完全图。图a图b2021/10/106def2:一个有向图G是一个有序的二元组,记为G=(V,A),其中V=(V1V2…Vn)称为G的点集合,A={aij}称为G的弧(有向边)集合,aij是以Vi指向Vj的一条弧。|V|=n表示G中节点个数为n,此节点个数n也称为图G的阶|A|=m表示有向图G中弧的个数为m任一顶点相关联(连接)的边的数目称为该顶点的次数2021/10/1072连通图def3:在有向图G中,一个点和边的交替序列{VieijVj…VkeklVl}称为G中从点Vi到Vl的一条路,记为A,其中Vi为此路A的起点,Vj为路A的终点;若路A的起点与终点重合,则称A为回路;又若G中点Vi与Vj间存在一条路,则称点Vi与Vj是连通的;若G中任何二点都是连通的,则称G为连通图,或图G为连通的。在无向图中有对应的概念。有向图路回路无向图链圈2021/10/1083子图def4:设有两个图:G1=(V1,E1),G2=(V2,E2)若有,则称G1为G2的子图,记作;若有V1=V2而,则称图G1=(V1,E1)是图G2=(V2,E2)的生成子图(支撑子图)。2021/10/109例:下示图G1是图G的子图,图G2是图G的生成子图。V1V3V2V4V1V2V4V1V3V2V4(a)图G(b)图G1(c)图G22021/10/1010