NOIP普及讲座7-图的基本知识(C++版).ppt

《NOIP普及讲座7-图的基本知识(C++版).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图的基本知识◆图的概念◆图的存储◆图的遍历◆图的应用江苏省金湖中学张厚林图的引入1736年欧拉利用图论思想解决了哥尼斯堡七桥问题（一笔画）（1）图的表示（2）无向图、有向图、带权图提问：指出上图中哪个是无向图、哪个是有向图、哪个是带权图？14235相关概念提问1：一个图中，全部顶点的度数为所有边数的倍;2提问2：有向图中所有顶点的入度之和是(大于、等于、小于)所有顶点的出度之和；提问3：任意一个无向图一定有（偶数、奇数）个奇点；√√以上为关于图的度的三个定理2.顶点的阶、度、入度、出度、奇点、偶点14235课上小练1、假设我们用d=(a1,a2,...,a5),表示无向图G的5个顶点

2、的度数，下面给出的哪（些）组d值合理（）。A.{5，4，4，3，1}B.{4，2，2，1，1}C.{3，3，3，2，2}D.{5，4，3，2，1}E.{2，2，2，2，2}2、无向图G有16条边，有3个4度顶点、4个3度顶点，其余顶点的度均小于3，则G至少_______个顶点。3、一个无向图有4个结点，其中3个的度数为2，3，3，则第4个结点的度数不可能是_______(北京理工,99年)A.0B.1C.2D.4相关概念欧拉图1）定义：欧拉通路——通过图中每条边一次且仅一次，并且过每一顶点的通路。欧拉回路——通过图中每条边一次且仅一次，并且过每一顶点的回路。欧拉图——存在欧拉回路的图

3、。2）定理1：存在欧拉路的条件：图是连通的，且存在0个或2个奇点。如果存在2个奇点，则欧拉路一定是从一个奇点出发，以另一个奇点结束。定理2：存在欧拉回路的条件：图是连通的，且不存在奇点。相关概念周游世界游戏问题哈密尔顿图1）定义：哈密尔顿通路——通过图中每个顶点一次且仅一次的通路。哈密尔顿回路——通过图中每个顶点一次且仅一次的回路。哈密尔顿图——存在哈密尔顿回路的图。2）判定：遗憾的是至今尚未找到一个判别哈密尔顿回路和通路的充分必要条件。课上小练在下图中，从顶点（）出发存在一条路径可以遍历图中的每条边一次，而且仅遍历一次。A、A点B、B点C、C点D、D点E、E点课上小练判断下图是否具

4、有哈密尔顿回路，通路。例1.城市公交网。有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。14235例2.奇怪的电梯。呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1<=i<=N)上有一个数字Ki(0<=Ki<=N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3

5、3125代表了Ki(K1=3,K2=3,……)，从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？核心：主要是点、边的存储。所以我们想尽办法，存储……建立模型1.邻接矩阵邻接矩阵：是表示顶点之间相邻关系的矩阵。设G(V，E)是具有n个顶点的图，顶点序号依次为1、2、…、n，则G的邻接矩阵是具有如下定义的n阶方阵。0A[i，j]=1对于无向图（Vi，Vj）或（Vj，Vi）∈E(G)对于有向图∈E(G)反之图的存储邻接矩阵表示为：邻接矩阵表示为：A1=∞21210∞2∞8∞9128∞6310∞6∞7∞937∞

6、A2=000100000101000011000000014235建立带权无向图的领接矩阵intmain(){constmax=1E5,n=10;intg[n+1][n+1];inti,j,k,e,w;g:graph;for(i=1;i<=n;i++)for(j=1;j<=n;j++)g[i][j]=max;输入样式：81221312141023825946353457for(i=1;i<=n;i++){for(j=1;j<=n;j++)cout<>e;for(k=1;k<=e;k++){cin>>i>>j>>w;g[i][j]=w

7、;g[j][i]=w;}2.边集数组边集数组：是利用一维数组存储图中所有边的一种图的表示方法。起点终点权无向带权图的边集数组表示法11122334234354552121089637图的边集数组表示算法描述（以无向带权图为例）voidcreate3(GE)；{图用边集数组存储}{for(k=1;k<=e;k++){cin>>i>>j>>w;{读入一条边（Vi，Vj）的两端点序号及权值}G[k].formvex=i;G[k].endvex=j;G[k].we