图的基础知识-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

图的基础知识

简介: 图G(graph)由顶点集V(vertex)和边集E(edge)组成,记为G(V,E)

图G(graph)由顶点集V(vertex)和边集E(edge)组成,记为G(V,E)

在图中,如果有边,那么此边的两端一定有点;否则不构成图

  1. 顶点的个数也称为图的阶
  2. 线性表可以是空表,树可以是空树,但图不能是空图,即顶点集V一定是非空集,但边集E可以为空集

无向图与有向图

若E是无向边(简称边)的有限集,则称G为无向图

  1. 边是顶点的无序对(一条边可以由一对无序的顶点表示),记为(v,w)或(w,v),因为(v,w)=(w,v)
  2. 顶点v和顶点w互为邻接点

若E是有向边(简称弧)的有限集合,则称G为有向图

  1. 弧是顶点的有序对(一条边可以由一对有序的顶点表示),记为<v,w>,是一条从顶点v到顶点w的弧,v为弧尾,w为弧头(有箭头的一端)
  2. <v,w>也称v邻接到w,或w邻接自v

简单图与多重图

简单图:不存在重复边;不存在顶点到自身的边

多重图:与简单图相反

数据结构课程只讨论“简单图”

顶点的度、入度、出度

对于无向图:

  • 顶点v的度指与该点相连的边的条数,记为TD(v)
  • 全部顶点的度之和是边数的两倍

对于有向图:

  • 入度是以顶点v为终点的有向边的数目,记为ID(v)
  • 出度是以顶点v为起点的有向边的数目,记为OD(v)
  • 顶点v的度等于其入度与出度之和,即TD(v)=ID(v)+OD(v)
  • 所有顶点的入度之和=出度之和=|E|

顶点-顶点的关系描述

路径:一个顶点到另一个顶点的的路径是指顶点序列

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

简单:即要求不重复

简单路径:一个路径中没有没有重复的顶点

简单回路:除了第一个顶点与最后一个顶点,其余顶点不重复的回路称为简单回路

路径长度:路径上边的数目

点到点的距离:两点之间最短路径的长度就是点到点的距离;若两点间不存在路径,那么记该距离为无穷\infty

连通

  • 无向图中,若两顶点之间有路径存在,则两顶点是连通的
    任意两个顶点都是连通的,那么称图G为连通图,否则称为非连通图
  • 有向图中,若两顶卖之间既有正向路径,也有逆向路径,那么两顶点是强连通的
    若任意两个顶点都是强连通的,那么称此图为强连通图
  • 常见考点:对于n个顶点的无向图G
    1. 若G是连通图,则最少有n-1条边
    2. 若G是非连通图,则最多可能有C^2_{n-1}(有一个顶点与其他顶点都没有连接,而其他顶点组成完全图,n-1个里任选2个)
  • 对于n个顶点的有向图G
    1. 若G是强连通图,则至少有n条边(形成回路)

子图

图G1的顶点集和边集都是图G的子集,那么称G1是G的子图

若G1和G的顶点集相同,那么称G1是G的生成子图

连通分量

无向图中的极大连通子图称为连通分量

有向图中的极大强连通子图称为强连通分量

生成树

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

  1. 连通图的生成树不唯一
  2. 若图中顶点数为n,则生成树的边数是n-1

生成森林

非连通图中,连通分量的生成树构成了非连通图的生成森林

边的权、带权图/网

边的权:在一个图中,每一条边都可以标上具有某种含义的数值,该数值称为该边的权值

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

带权路径长度:当图是带权图时,一条路径上所有边的权值之和,称为该路径的带权路径长度

几种特殊形态的图

无向完全图:无向图中任意两个顶点之间都存在边

  1. 无向完全图的边总数为:C^2_n

有向完全图:有向图中任意两个顶点之间都存在方向相反的两条弧

  1. 有向完全图的边总数为:2C^2_n

稀疏图:边数很少的图

稠密图:与稀疏图相对的图

:不存在回路,且连通的无向图

  • n个顶点的树,则必有n-1条边
  • 常见考点:n个顶点的图,若|E|>n-1,则一定有回路

有向树一个顶点的入度为0,其余顶点的入度都为1的有向图,称为有向树


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章
最新文章