开发者社区> ggbond233> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

图的基础知识

简介: 图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的有向图,称为有向树


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

相关文章
js基础知识
js基础知识
10 0
Eureka基础知识
Spring Cloud 封装了 Netflix 公司开发的 Eureka 模块来实现服务治理 在传统的rpc远程调用框架中,管理每个服务与服务之间依赖关系比较复杂,管理比较复杂,所以需要使用服务治理,管理服务于服务之间依赖关系,可以实现服务调用、负载均衡、容错等,实现服务发现与注册。
50 0
二极管的基础知识
(1)定义:导电能力介于导体和绝缘体之间的一类物质,称为半导体。常用的半导体材料是硅和锗。 (2)敏感特性:半导体的导电能力对温度、光照、磁场、电场等很敏感。 (3)导电特征: ①纯净的半导体中的半导体中自由电子、空穴数目相等且数量少,导电能力极差。(所以使用“掺杂”特性) ②自由电子、空穴同时参与导电,这是半导体区别于导体的重要导电特征。
57 0
触发器基础知识(中)
JK触发器是在同步RS触发器的基础上引入两条反馈线构成的。
76 0
苹果开发基础知识
App ID(应用ID) App ID是识别不同应用程序的唯一标示符。每个app都需要一个App ID或者app标识。 目前有两种类型的App标识:一个是精确的App ID(explicit App ID),一个是通配符App ID(wildcard App ID)。
1122 0
数组基础知识
/* ============================================================================ Name : TestArray.
442 0
摄影基础知识
一、光圈(Aperture)   光圈是用来控制通过镜头进入相机内感光元件的光线数量   光圈f值 = 镜头的焦距 / 镜头口径的直径 常见的光圈:f2,f2.8,f4,f5.6,f8,f11,f16,f22 f值越小,镜头口径越大,同一时间的进光量越大,此时应适当将快门调慢   光...
534 0
+关注
文章
问答
文章排行榜
最热
最新
相关电子书
更多
典型模型-卷积神经网络入门 从概念原理到应用实现
立即下载
阿里云视觉计算开发者系列手册-目标检测入门必读指南
立即下载
低代码开发师(初级)实战教程
立即下载