文章目录
- 基本概念
- 图Graph
- 有向图:
- 无向图:
- 简单图
- 完全图(简单完全图)
- 有向完全图
- 子图
- 连通
- 连通图
- 极大连连通子图(连通分量)
- 完全图和连通图问题
- 最多允许几条边保持不连通?
- 多少条边就可以保证连通?
- 生成树
- 连通图的生成树
- 非连通图的生成森林
- 强连通(顶点对)
- 强连通图
- 强连通分量
- 至少需要n条边
- 小结
- 顶点的度
- 相关性质
- 边的权
- 带全图(网)
- 稀疏图&稠密图
- 路径相关
- 顶点间路径
- 路径长度
- 回路(环)
- 有环的充分条件
- 简单路径
- 简单回路
- 顶点间距离(最短路径)
- 森林/树/图
- 有向树
- 树&图
基本概念
图Graph
- 由顶点V(vertex)和边E(edge)构成,记图为G(V,E)
- V(G)表示图G中顶点的有限非空集合
- V={}
- |V|表示顶点集合中的顶点个数,即图G的顶点数
- 要求|V|>0,图不可以是
"空图"
- E(G)表示图G中顶点间的边(关系)集合
- E={}
- |E|表示图G中的边数
- ,图中允许只有点而没有边
有向图:
- 集合中的边是有向边的有限集的图
无向图:
- 和有向图相对应,边都是无向边
简单图
- 图中不存在重复边
- 不存在顶点到自身的边
- 数据结构中讨论的是简单图
完全图(简单完全图)
- 条边的无向图称为完全图(任意两个结点见都有直接边)
- 对于无向图,
- 这个范围在讨论优向完全图的时候解释
有向完全图
- 有向完全图中任意两个结点间都存在方向相反的两条弧
- 可以考察一个图G的任意一个点v
- 点v相关的边有两类:出边和入边
- 显然出边有条(图G总共有n个结点)
- 其他结点邻接到v的边,也就是v的入边数也是
- 所有出边形如:
- 其中
- 类似的对V中其他顶点建立所有出边,就是的过程
- 这样一来,每个结点都有n-1条出边和入边
- 此时这个图有n(n-1)条有向边,而且是任意两个结点都有一来一往两条边
- 回到无向图,是不去分方向的,因此任意两个结点间的一来一往两条边合并为一条无向边
- 所以无向图最多有条边
子图
连通
- 在无向图中,如果顶点v到顶点w的路径存在,那么v和w是连同的
- 注意,只要求路径存在,而不要求路径的长度为1(直达)
连通图
- 如果图G中的任意两个顶点是连同的,那么图G是连通图
- 否则为非连同图
极大连连通子图(连通分量)
- 无向图中极大连通子图称为连通分量
- 这里的极大指的
- 是连通子图包含尽可能多的边
- 极小连通子图:
- 既要保持图的连通又要使得边数最少(尽可能的少)
- 如果在分配一个点给极大联通子图就会造成连通性被破坏,那么这样的联通子图才是极大联通子图
- 一个图G的联通子图可以有很多,但是极大联通子图的数量就比较有限,但往往也不是唯一的
- 而且不同的极大联通子图具有不一定相等的顶点数;这些极大联通子图都是图G的连通分量
- 如果一个包含n个顶点的图是连通图,那么这个连通图至少含有n-1条边
- 设顶点集合;图G的点分布在中
- 现在我们往里头加点
- 因此,n个结点的连通图至少含有n-1条边,否则该图是不连通的!!
完全图和连通图问题
最多允许几条边保持不连通?
- 另方面,如果一个含有n个结点的图G想要避免构成连通图,那么最多允许几条边?
- 容易联想到,n个顶点具有最多边的情况是n阶完全图(这肯定是连通图)
- 现在考虑从n阶完全图中去掉尽可能少的边,来构成非连通图
- 我们抓住一个点,将它与其他n-1个点的联系全部去掉,就构成了有尽可能多边的非联通图
- 这个数值就是n-1阶完全图的边数()
多少条边就可以保证连通?
- 如果某个无向图有n个顶点,那么至少需要多少条边,使得该图一定是一个连通图
- 这类问题也是完全图的问题
- 考虑n-1条边
- 这种情况下,剩下的一个顶点将游离于前n-1个顶点,图还是可能不连通
- 但是如果在加上一条边,由于前n-1个顶点间的边已经完全饱和,那么新增的一条边导致n个结点连通起来
生成树
连通图的生成树
- 包含图中所有顶点的极小连通子图
- 根据上面的分析,如果连通图的顶点数为n,那么它的生成树含有n-1条边(不多也不少)
- 在生成树中,减去一条边会导致不再连通
- 加上一条边,会导致回路的形成
- 尽管如此,同一个连通图的生成树不一定唯一
- 例如一个环图G,去掉任何一条边即可得到G的一个生成树
- 因此有最小生成树这类算法
非连通图的生成森林
- 非连通图可以从连通分量的角度考察,它们它是由它若干的极大联通子图构成的
- 分别计算连通分量的生成树
- 这些生成树构成生成树森林
强连通(顶点对)
- 在有向图G中,如果一对顶点v,w;v到w以及w到v都有路径,则这两个顶点是强连通的(双向连通的)
- 注意,连通和强连通一样,只要求路径存在,而不要求路径的长度为1(直达)
强连通图
- 如果有向图G中,所有顶点都是强连通的,那么G是强连通图
- 如果我们按照定义去考察一个有向图是否为连通图,可以分别考察每个顶点是否能够到达其他所有顶点
- 这需要次比较
强连通分量
- 有向图中的极大强连通子图称为有向图的强连通分量
至少需要n条边
- 鉴于有向图的有向性,
- 传递性:如果点v能够到达B,B能够到达集合{C}中的任意点,那么认为v可以到达{C}中的任意点(直观)
- 从开始考虑
- n:至少需要的条边数
- 1:0
- 2:2(一条边仅单向可达,必须两条)(记现在的两个顶点为a,b)
- 3:?
- 在n=2的规模内,要让三个点(记为c)能够到达a或者b,至少需要从c出发,邻接一条边到a/b
- 另一方面,为了能够让a/b出发能够到达c,也至少要从a/b出发一条边邻接到c
- 即,任意生成树中的每个结点至少有一条出边和一条入边(这是至少的下限)
- 现在想让n个结点有尽可能少的边,可以尝试:
- 复用边:good idea!
- 比如三个点:A–>B–>C
A
B
C
- 其中A–>C的路径就复用了B–>C的路径(BC边)
- 这是传递性的体现;
- 现在,AB,AC,BC,都没问题
- 但是BA,CB,CA不可以
- 为了让C能够到达A,必须在加一条边
-
A
B
C
- 现在CA,BA(B->C->A),CB(C->A->B),都可以
- 这是传递性的体现;
- 让每个结点上的边的端点(弧头/弧尾尽可能少)
- 仅保留必要的一组弧头/弧尾
- 可以发现
顺序闭环
- 可以实现必要的边数实现所有点互通的目的
- 这是容易验证,因为任意顶点数为N的顺序环上的任意结点x沿着顺序环行进,可以遍历所有环内结点
- 这意味着,从任意一个结点x(x可以取环上的任意结点,不失一般性)开始,沿着一个方向行进,总是可以到达环内任意指定的第二个结点y,包括起点本身
小结
- 在无向图中讨论连通性
- 有向图中讨论强连通性
顶点的度
- 在无向图中
- 顶点v的度:图G中依附于顶点v的边的条数
- 有向图中
- 入度(In Degree)和出度(Out Degree)之分
- 入度是以顶点v作为有向边的终点(弧头)
- 出度是以顶点v作为有向边的起点(弧尾)
相关性质
- 无向图中,n个顶点,e条边的无向图,
- 无向图的全部顶点的度数之和为边数2倍
- 因为,每条边依赖于两个顶点,每一条都会为其两个断点各贡献一度
- 因此,在统计边数的时候,每条边会贡献2度
- 即,总度数是总边数的2倍
- 至于顶点数n,我们不关心
- 还是从统计(有向)边的角度考察
- 每个有向边都分别为他的起点顶点贡献一个出度,以及为他的终点顶点贡献一个入度
- 统计所有边,则得到有向图的顶点总入度和总出度相等(都等于边数e)
边的权
- 在一个图中,每条边都可以标注有含义的数值(类似于带权结点);数值称为权值
带全图(网)
- 边上带有权值的图称为带权图或者网
稀疏图&稠密图
- 边数相较于顶点数少的比较明显的图称为稀疏图(模糊概念)
路径相关
顶点间路径
路径长度
- 路径上的边数就是路径长度
回路(环)
- 环是一种特殊路径:起点和终点一致的路径
有环的充分条件
- 顶点数为n,边数大于n-1的图一定带环
- 前面对生成树的边数的分析结论表明,n个结点最多消耗n-1条边而不差生回路(或者重复边)
简单路径
- 路径序列中,顶点不重复出现的路径是简单路径
简单回路
- 如果一个回路(环)只有首尾结点重复,那么称为简单回路
顶点间距离(最短路径)
- 如果顶点u到顶点v存在最短路径,那么这个最短路径的长度就是顶点u,v的距离
- 如果不存在可达路径,则是距离记为无穷远
森林/树/图
有向树
- 自定向下构造的树类似的形状
- 其中一个顶点的入度为0(相当于根结点)
- 其余顶点的入度为1
- 出度不做任何限制
树&图
- 树是可空的,但是图是不可空的
- 但从图形上看,树或森林总是有对应的图可以描述
- 森林中的k棵树犹如连通图断开k-1条边一样
- 如果某个无向图对应于一个森林(包含n个顶点/e条边)
- 由树和图的性质
![【数据结构】 医院选址[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)