图的基础知识

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


目录
相关文章
|
9月前
|
监控 网络协议 网络性能优化
不再困惑!一文搞懂TCP与UDP的所有区别
本文介绍网络基础中TCP与UDP的区别及其应用场景。TCP是面向连接、可靠传输的协议,适用于HTTP、FTP等需要保证数据完整性的场景;UDP是无连接、不可靠但速度快的协议,适合DNS、RIP等对实时性要求高的应用。文章通过对比两者在连接方式、可靠性、速度、流量控制和数据包大小等方面的差异,帮助读者理解其各自特点与适用场景。
|
安全 程序员 编译器
c未定义行为
c未定义行为
203 0
|
12天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1255 5
|
1天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
11天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1275 87