东凤网站建设,一级网站建设,WordPress换主题文件夹,网上买手表哪个平台最好第六章 图
6.1 图的基本概念
概念 图的概念#xff1a;G由点集V和边集E构成#xff0c;记为G(V,E)#xff0c;边集可以为空#xff0c;但是点集不能为空 注意#xff1a;线性表可以是空表#xff0c;树可以是空树#xff0c;但图不可以是空#xff0c;即V一定是非空集…第六章 图
6.1 图的基本概念
概念 图的概念G由点集V和边集E构成记为G(V,E)边集可以为空但是点集不能为空 ·注意线性表可以是空表树可以是空树但图不可以是空即V一定是非空集 无向图与有向图 无向图 无向边简称边 无序对例如(a,b)(b,a)表示a和b两个点相连 有向图 有向边简称弧 有序对例如v,w称为从顶点v指向顶点w的弧其中v称为弧尾w称为弧头v,w≠w,v 简单图与多重图数据结构课程只探讨 简单图 简单图包含简单有向图、简单无向图 不存在重复边 不存在顶点到自身的边 多重图 图G中某两个结点之间的边数多于一条 允许顶点通过同一条边和自己关联 顶点的度、入度、出度 对于无向图 顶点v的度是指依附于该顶点的边的条数记为TD(v) 无向图每条边贡献两个度因此n条边的无向图总度数为2n 对于有向图 入度是以顶点v为终点的有向边的数目记为ID(v) 出度是以顶点v为起点的有向边的数目记为OD(v) 顶点v的度等于其入度和出度之和即TD(v) ID(v) OD(v) 有向图每个边贡献一个入度和一个出度因此有向图总出度等于总入度等于边的个数 顶点与顶点的关系 路径 顶点a到顶点b之间的一条路径是指顶点序列acde…fgb 有向图的路径方向必须符合有向边的方向 有向图和无向图均有不存在路径的情况 无向图一个孤立点没有任何边——没有到这点的路径 有向图一个点没有被任何弧头指到——没有路径 回路第一个顶点和最后一个顶点相同的路径称为回路或环 简单路径在路径序列中顶点不重复出现的路径称为简单路径。 简单回路除第一个顶点和最后一个顶点外其余顶点不重复出现的回路称为简单回路 路径长度路径上边的数目 点到点的距离从顶点u出发到顶点v的最短路径若存在则此路径的长度称为从u到v的距离若从u到v根不不存在路径则记该距离为无穷 (∞) 无向图中若从顶点v到顶点w有路径存在则称v和w是连通的 有向图中若从顶点v到顶点w和从顶点w到顶点v之间都有路径则称这两个顶点是强连通的 连通图若无向图G中任意两个顶点都是连通的则称图G为连通图否则称为非连通图。 对于n个顶点的无向图G若G是连通图则最少有 n-1 条边 对于n个顶点的无向图G若G是非连通图则最多可能有条边 强连通图若有向图中任何一对顶点都是强连通的则称此图为强连通图 对于n个顶点的有向图G若G是强连通图则最少有(n)条边(形成回路) 图的局部 子图设有两个图G(V,E)和G’(V,E)若V是V的子集且E’是E的子集不存在边两端的任何一端没有点的情况则称G’是G的子图 生成子图包含原图的所有顶点和部分边的子图 连通分量无向图中的极大连通子图子图必须连通并且包含尽可能多的顶点和边 强连通分量有向图中的极大强连通子图子图必须连通并且包含尽可能多的边 生成树连通图的生成树是包含图中全部顶点的一个极小连通子图 保持连通且边尽可能少 若图中顶点数为n则它的生成树含有 n-1条边。 对生成树而言若砍去它的一条边则会变成非连通图若加上一条边则会形成一个回路。 应用场景用最少的道路边树连接所有地区点 生成森林在非连通图中连通分量的生成树构成了非连通图的生成森林 边的权在一个图中每条边都可以标上具有某种含义的数值该数值称为该边的权值。 带权图/网边上带有权值的图称为带权图也称网。 带权路径长度当图是带权图时路径上所有边的权值之和称为该路径的带权路径长度 几种特殊形态的图 无向完全图无向图中任意两个顶点之间都存在边 若无向图的顶点数|V|n则 有向完全图有向图中任意两个顶点之间都存在方向相反的两条弧 若有向图的顶点数|V|n则 稀疏图与稠密图边数很少的图称为稀疏图反之称为稠密图 树不存在回路且连通的无向图 n个顶点的树必有n-1条边 n个顶点的图若边数大于n-1则一定有回路 树是连通图无向图 有向树1个顶点的入度为0其余顶点的入度均1有向图称为有向树 有向树是有向图但不是强连通图 理解 连通图连起来就行最少的马路连通最多的村子 完全图每个点都除他以外的所有点完全连接
技巧 当有n个点若边数等于n-1则无环连通但若边数超过n-1则有环未必连通 有n个顶点的无向图边数v的几个临界值 如果vn-1一定不是连通图 如果n-1≤v C n − 1 2 1 C_{n - 1}^{2} 1 Cn−121则可能是连通图也可能不是 如果v C n − 1 2 1 C_{n - 1}^{2} 1 Cn−121则一定是连通图确保n个顶点连通的思路n-1个顶点形成完全图再加上一个边那么一定连通
