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

文档介绍：作业:P170~171 (c) (b) 第六章图与网络分析
哥尼斯堡七桥问题 德国古城—哥尼斯堡—普雷格尔河—七
桥问题:从任一桥头出发,依次走过每座
桥,每座桥只走一次,最后回到出发点。
——一笔画问题
2. 中国邮递员问题 邮递员送信送报要走完全部所负责的街道,最后回到邮局,如何走路程最短?
第一节图的基本概念一、图的概念1. 图(无向图) 图是由点与边组成的集合,记为:G=(V,E),其中V≠Φ,表示图G中点的集合,E表示图G中边的集合。图中点的个数记为p,称为图的阶;图中边的条数记为q。
2. 端点、关联边、相邻 若边e可以表示为e=(vi,vj),则称vi和vj是边e的端点;边e称为点vi和vj的关联边。 若点vi、vj与同一条边关联,称点vi和vj相邻。 若边ei、ej有公共的端点,称边ei和ej相邻。
3. 环,多重边,简单图 如果边e的两个端点相重,称该边为环。 如果两个端点之间的边多于一条,称为多重边。无环、无多重边的图称为简单图。4. 次,奇点,偶点,孤立点,悬挂点 与某一个点vi相关联的边的数目称为点vi的次。记为d(vi)。 次为奇数的点称为奇点,次为偶数的点称为偶点。 次为0的点称为孤立点。次为1的点称为悬挂点。
.v6