（贵州省普通高中信息学奥赛CSP-JS NOIP—提高组C++知识点讲解）第11讲 图

学科竞赛编程 C++ NOIP NOI IOI 1 思考： 【 快递员在送快递时，为了节省路途，于是想：每次总是从多个地点中选择一个合适的地点出发，途经每个地点仅且经过一次，送完手中所有的快递。 如何规划路线？ 【 一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？ 哥尼斯堡七桥问题 风景秀丽的哥尼斯堡城 （今俄罗斯加里宁格勒） 是德国的一座历史名城。 普莱格尔河贯穿整个哥尼斯堡小城，这条河有两条支流，它们环绕一个小岛， 在这两条支流上有七座桥（见右图）将岛与河岸连接。 城里的居民晚饭后喜欢到这里散步，久而久之，就有了这样一个问题 ： 大家都试图找出问题的答案，但是谁也解决不了这个问题。 3 哥尼斯堡七桥问题 C A B D C A B D · · · · 【 七桥问题：一笔画问题 —图论的起源 于是问题就被送到了正在俄国圣彼得堡（原列宁格勒）的科学院做研究的大数学家欧拉手里。 欧拉并没有跑到哥尼斯堡去走走，他将陆地和小岛用点表示，而将七座桥用线表示， 于是七桥问题就等价于右图中图形的一笔画问题了。 欧拉用严格的数学方法证明了这种画法是不存在的。 对于类似的更一般的图形，欧拉也找到了一个简便的原则: 一笔画定理，判定它能否一笔画出 ：它们是连通的，且奇顶点 ( 通过此点边的条数是奇数 )的个数为 0 或 2。这就是“一笔画”定理，也称为欧拉定理，经过每个点恰好一次的回路也称为“欧拉回路”。 欧拉通过对七桥问题的研究，不仅圆满地回答了哥尼斯堡居民提出的问题， 而且由此开创了数学的两个新的分支——图论与拓扑。 4 图结构及图 【 图结构：是研究数据元素之间的多对多的关系。 【 图：是由有限个数的顶点和顶点之间边的组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。 什么是图？ 在前面讲解的线性表中，每个元素之间只有一个直接前驱和一个直接后继，在树形结构中， 数据元素之间是层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关。 在这种结构中，任意两个元素之间可能存在关系。 即结点之间的关系可以是任意的，图中任意元素之间都可能相关。 5 【 注意 图中数据元素称为顶点（结点） 图中顶点是有限个并且不为0 图中任意两个顶点之间都可能有关系 图结构及图 线性表中我们把数据元素叫元素，在树中叫结点，在图中数据元素我们则称之为顶点 线性表可以没有数据元素，称为空表，树中可以没有结点，叫做空树，图结构中顶点集合V要有穷非空。 线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系， 6 【 图的边有方向，只能按箭头方向从一点到另一点。 有向边的表示：用尖括号将边两边的顶点括起来。 有向边也叫弧，Vi称为弧尾，Vj称为弧头。 有向图 1 1 4 2 3 上图G1是一个有向图，G1=(V1,E1),其中 V1={1,2,3,4}， E1={<2,1>,<2,3>,<3,1>,<1,4>}   图的概念—有向图 始点为弧尾 终点为弧头 <Vi,Vj> 强调有序偶数对，用尖括号 起点为弧尾，指向的点为弧头 7 【 图的概念—无向图 图的边没有方向，可以双向。 无向边：用圆括号将边两端的顶点括起来来表示。 无向图 上图G2是一个无向图，G2=(V2,E2),其中 V2={1,2,3,4}， E2={(1,2) ,(2,3),(3,4),(4,1),(1,3)} 说明：无序对(1,2) 表示顶点1和2之间的一条边,因此 (1,2) 和(2,1)代表的是同一条边。   2 1 4 2 3 （Vi,Vj） 强调无序偶数对用圆括号 8 完全图 有向完全图 无向完全图 & 【 有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧。 含有n个顶点的有向完全图有n*(n-1)条边。 【 无向图中，任意两个顶点之间都存在边。 含有n个顶点的无向完全图有n*(n-1)/2条边。 1 4 2 3 1 4 2 3 12条边 6条边 9 子图 1 4 2 3 【 子图举例 3 1 1 4 1 2 4 2 3 1 4 2 3 【 子图举例 1 1 4 1 2 3 1 4 2 3 【 如果图1可以看作是图2的一个组成部分，则图1是图2的子图。 度，入度，出度 度 1 4 2 3 【 顶点V的度是和V相关联的边的数目。 右图中顶点1的度为____。 3 入度 【 有向图中，以顶点V为终点的有向边的数目。 出度 【 有向图中，以顶点V为起点的有向边的数目。 1 4 2 3 右图二中，顶点1的入度为____，出度为____,度为____。 2 1 3 11 权值 【 权值：边的“费用”, 可以形象地理解为边的长度。 带权的图通常称为网。 1 4