图的基础知识

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


目录
相关文章
|
程序员 C# 图形学
【Unity 3D】C#中条件语句if else switch的讲解
【Unity 3D】C#中条件语句if else switch的讲解
308 1
|
容器 微服务 Kubernetes
带你读《Istio入门与实战》之一:服务网格与Istio
本书系统化介绍Istio技术要点与应用技巧,可帮助读者快速搭建微服务架构并进行管理。主要内容包括:service mesh基本概念与使用,Istio架构设计与主要功能,快速搭建一个微服务实验,介绍如何让服务流量控制更简单,让服务更具弹性,让服务故障测试更容易,让服务通信更安全可控,让服务更易观测与监控,以及istio维护方案。本书内容丰富、案例讲解,实用性强,非常适合入门级读者快速掌握Istio技术。
|
缓存 前端开发 JavaScript
如何优化前端性能:7个实用技巧
在当今互联网高速发展的时代,前端性能优化成为了每个开发者必须面对的挑战之一。本文将介绍7个实用的技巧,帮助前端开发者提升网站性能,提升用户体验。
|
SQL 数据管理 关系型数据库
数据管理DMS产品使用合集之如何设置SQL执行的超时时间
阿里云数据管理DMS提供了全面的数据管理、数据库运维、数据安全、数据迁移与同步等功能,助力企业高效、安全地进行数据库管理和运维工作。以下是DMS产品使用合集的详细介绍。
155 1
|
10月前
|
5G 网络架构
怎么区分5G卡片开启的网络类型是NSA(非独立组网)还是SA(独立组网)
要确定5G卡片开启的网络类型是NSA(非独立组网)还是SA(独立组网),你通常需要进行以下操作:
|
机器学习/深度学习 数据采集 开发者
深度学习中的模型优化策略
【9月更文挑战第20天】在深度学习的海洋里,每一个研究者和实践者都在追求更高效、更准确的模型。本文将深入探讨深度学习中模型优化的策略,从数据预处理到正则化技术,再到超参数调整,我们将一步步揭开模型优化的神秘面纱。无论你是初学者还是有经验的开发者,这篇文章都将为你提供宝贵的见解和实用的技巧。让我们一起探索如何让你的深度学习模型更加出色吧!
235 8
|
前端开发 JavaScript 开发者
介绍一下React生命周期
介绍一下React生命周期
205 9
|
消息中间件 Java 数据库连接
实时计算 Flink版产品使用合集之将sdkMode从rpc模式改为jdbc模式后,table.exec.mini-batch.enabled参数还生效吗
实时计算Flink版作为一种强大的流处理和批处理统一的计算框架,广泛应用于各种需要实时数据处理和分析的场景。实时计算Flink版通常结合SQL接口、DataStream API、以及与上下游数据源和存储系统的丰富连接器,提供了一套全面的解决方案,以应对各种实时计算需求。其低延迟、高吞吐、容错性强的特点,使其成为众多企业和组织实时数据处理首选的技术平台。以下是实时计算Flink版的一些典型使用合集。
152 0
|
11月前
|
人工智能 搜索推荐 安全
中药药材推荐系统
中药药材推荐系统
151 0
|
语音技术 开发工具 git
要进行ModelScope-Funasr实时ASR的微调,您可以按照以下步骤操作:
要进行ModelScope-Funasr实时ASR的微调,您可以按照以下步骤操作:
1367 5