文档介绍：2019/12/30管理运筹学ABCDACBD图论起源——哥尼斯堡七桥问题结论:每个结点关联的边数均为偶数。问题:一个散步者能否从任一块陆地出发,走过七座桥,且每座桥只走过一次,最后回到出发点?2019/12/30管理运筹学§1图的基本概念由点和边组成,记作G=(V,E),其中V={v1,v2,……,vn}为结点的集合,E={e1,e2,……,em}为边的集合。,记作G=(V,E)有向图,记作D=(V,A)例1:哥尼斯堡桥问题的图为一个无向图。有向图的边称为弧。例2:五个球队的比赛情况,v1v2表示v1胜v2。v1v2v3v4v52、图的分类2019/12/30管理运筹学v1v2v3v4v53、链与路、圈与回路链点边交错的序列圈起点=终点的链路点弧交错的序列回路起点=终点的路v1v2v3v4v5无向图:有向图:2019/12/30管理运筹学4、连通图任何两点之间至少存在一条链的图称为连通图,否则称为不连通图。G1G2G1为不连通图,G2为连通图例:2019/12/30管理运筹学5、支撑子图图G=(V,E)和G'=(V',E'),若V=V'且E'E,则称G'为G的支撑子图。G2为G1的支撑子图v1v2v3v4v5G1v1v2v3v4v5G2例:2019/12/30管理运筹学6、赋权图(网络)图的每条边都有一个表示一定实际含义的权数,称为赋权图。记作D=(V,A,C)。:2019/12/30管理运筹学§2最小支撑树问题本节主要内容:树支撑树最小支撑树[例]今有煤气站A,将给一居民区供应煤气,居民区各用户所在位置如图所示,铺设各用户点的煤气管道所需的费用(单位:万元)如图边上的数字所示。要求设计一个最经济的煤气管道路线,并求所需的总费用。、树中任两点中有且仅有一条链;2、树任删去一边则不连通,故树是使图保持连通且具有最少边数的一种图形。3、边数=顶点数–1。树无圈连通图(A)(B)(C)树的性质:例判断下面图形哪个是树:一、树的概念与性质2019/12/30管理运筹学若一个图G=(V,E)的支撑子图T=(V,E´)构成树,则称T为G的支撑树,又称生成树、部分树。二、图的支撑树(G)(G1)(G2)(G3)(G4)例