图的基本概念思维导图

生杀予夺

2023-11-28

浏览量: 11

无向边的集合

不存在重复边

数据结构只讨论这个

图的基本概念介绍

树图思维导图提供《图的基本概念》在线思维导图免费制作，点击“编辑”按钮，可对《图的基本概念》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：6356267647072a32ea65c68a239f7388

思维导图大纲

定义

顶点集V = {v1,v2,...,vn}

|V|表示图G的顶点个数，也称图的阶

边集E = {(u,v)|u∈V，v∈V}

|E|表示图G中边的条数

边的两头一定各有1个顶点

注意点：

V一定是非空集，E可以是空集

无向图与有向图

无向图：E是无向边的集合

此时必有(v,w) = (w,v)，其中v、w是顶点

(v,w)是边，可以说w、v互为邻接点；边(v,w)依附于顶点v、w；边(v,w)与v、w相关联

有向图：E是有向边（也称弧）的集合

<v,w>未必＝<w,v>，<v,w>是边

v是弧尾，w是弧头，<v,w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接到v

简单图与多重图

简单图

不存在重复边

不存在顶点到自身的边

数据结构只讨论这个

多重图

G中某两个顶点边数多于1条

又允许顶点通过同一条边和自己关联

顶点的度、入度、出度

对于无向图，顶点v的度为依附该顶点的边的条数记为TD(v)

无向图全部顶点度的和 = 边数2倍

有向图

入度为以顶点v为终点的有向边条数，ID(v)

出度为以顶点v为起点的有向边条数，OD(v)

顶点v的度即为入度与出度之和，即TD(v) = ID(v) + OD(v)

各顶点入度之和 = 各顶点出度之和 = 总边数

顶点与顶点关系

路径

顶点v1和顶点v2之间一条路径指顶点序列v1,vi1,vi2,...,v2

回路

第1个顶点和最后1个顶点相同的路径称为回路或环

简单路径

路径序列中顶点不重复出现的路径

简单回路

除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路

路径长度

路径上边的条数

点到点的距离

u到v最短路径若存在，称该路径长度为u到v的距离

若u到v不存在路径，距离为∞

无向图中若u到v有路径存在，称为u和v是连通的

有向图中若u到v的路径存在，v到u的路径也存在，称这两个顶点强连通

连通图与非连通图

图G中任意两个顶点连通，则G为连通图，否则为非连通图

对于n个顶点的图G

若G是连通图，则最少有n-1条边（树），反过来说，若|E|< n -1 必不连通

若G是非连通图，则最多有C(2,n - 1)条边（让其余n-1个结点为完全图）（排序数，上标2下标n-1，知道那意思就行）

由此可知，想让G连通，|E|≥C(2,n - 1) + 1

图G中任意两个顶点强连通，称为强连通图

n个顶点有向图G，若G强连通，最少n条边（回路）

图的局部

子图

V'是V的子集，E'是E的子集，则G’是G的子图，必须满足G‘满足图的特性

生成子图：如果G’顶点都是G的顶点，称为G’是G的生成子图

连通分量与强连通分量

连通分量：无向图的极大连通子图

子图必须连通，包含尽可能多的顶点和边

n个结点最少1个连通分量，最多n个连通分量

强连通分量：有向图的极大强连通子图

某顶点无入边 or 出弧，则其自成1个连通分量

生成树

连通图的生成树：包含图中全部顶点的极小连通子图

n个顶点连通图的生成树有n-1条边

生成森林

非连通图中连通分量的生成树

边的权、带权图/网

边的权：边上含有某种意义的数值

带权图/网：边上有权值的图为带权图，也称网

带权路径长度

带权图一条路径上所有边的权值之和

特殊图

无向完全图

无向图中任意两点之间都存在边

边数范围[0,n(n-1)/2]

有向完全图

有向图中任意两个顶点都存在方向相反的两条弧

边数范围[0,n(n-1)]

稀疏图、稠密图

稀疏图的边数远远小于顶点数的平方

树

无回路且连通的无向图

n个顶点必有n-1条边

若|E| > n - 1必有回路

有向树：一个顶点入度为0，其余顶点入度全为1的有向图

注意有向树未必强连通

补充内容

n个顶点，m条边，连通分量最多

以n=51，m=19为例

51个顶点->51个连通分量->问题转化为添加19条边使连通分量最多：令其接近完全图

7个顶点，21条边构成完全图，故选择7个顶点为其添加19条边使其成为1个连通分量，其余结点自成1个连通分量

共有51 - 7 + 1 = 45个连通分量

如何让有向无环图的顶点号重新安排使该图的邻接矩阵所有1都集中到对角线以上

首先，邻接矩阵所有的1都集中到对角线以上意味着：i->j，同时i<j，可以利用拓扑排序实现

图各个顶点之间的地位是平等的，因此可以按照需要对图中顶点重新编号

流程图表示思维导图

浮沉

0.31

树图思维导图提供《流程图表示》在线思维导图免费制作，点击“编辑”按钮，可对《流程图表示》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：5948c35cf208112e2ca32158796e1b7e

采购管理流程图思维导图

U351238109

树图思维导图提供《采购管理流程图》在线思维导图免费制作，点击“编辑”按钮，可对《采购管理流程图》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：002b6af92a5160b6083c068a0f49d862

思维导图模板

高校与高等教育

其他学科

正文

相似思维导图模版

思维导图模版推荐

安全工程在道路施工中的组织架构_副本思维导图

首页

我的文件

我的团队

个人中心