运筹学第六章图与网络分析a管理精品资料.ppt

该【运筹学第六章图与网络分析a管理精品资料 】是由【落意心冢】上传分享，文档一共【121】页，该文档可以免费在线阅读，需要了解更多关于【运筹学第六章图与网络分析a管理精品资料 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。邮递员送信送报要走完全部所负责的街道,最后回到邮局,如何走路程最短?第一节图的基本概念一、图的概念(无向图)图是由点与边组成的集合,记为:G=(V,E),其中V≠Φ,表示图G中点的集合,E表示图G中边的集合。图中点的个数记为p,称为图的阶;图中边的条数记为q。、关联边、相邻若边e可以表示为e=(vi,vj),则称vi和vj是边e的端点;边e称为点vi和vj的关联边。若点vi、vj与同一条边关联,称点vi和vj相邻。若边ei、ej有公共的端点,称边ei和ej相邻。,多重边,简单图如果边e的两个端点相重,称该边为环。如果两个端点之间的边多于一条,称为多重边。无环、无多重边的图称为简单图。,奇点,偶点,孤立点,悬挂点与某一个点vi相关联的边的数目称为点vi的次。记为d(vi)。次为奇数的点称为奇点,次为偶数的点称为偶点。次为0的点称为孤立点。次为1的点称为悬挂点。,部分图对图G1={V1,E1}和图G2={V2,E2},若有,则称G1是G2的一个子图。若有,则称G1是G2的一个部分图。定理:在图G中,所有顶点次之和等于边数的两倍。即:定理:在任一图中,奇点的个数必为偶数。例:有八种化学药品,某些不能放入同一个仓库,用连线表示。见下图。(v1)(v2,v4,v7)(v3,v5)(v6,v8)例:四色问题。对图G1={V1,E1}和图G2={V2,E2},如果顶点集合V1与V2之间以及边的集合E1与E2之间都建立了一一对应关系,并且图G1的两顶点之间的边对应于图G2对应顶点的边,则称图G1与图G2是同构的。