图的基础知识

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


目录
相关文章
|
3月前
|
机器学习/深度学习 搜索推荐 图计算
图基础知识
图基础知识
|
4月前
|
人工智能 前端开发 JavaScript
前端学习路线图
前端学习路线图
67 2
|
6月前
|
存储 算法 Python
数据结构与算法 - 图
数据结构与算法 - 图
29 0
|
算法 vr&ar
第七章 图【数据结构与算法】2
第七章 图【数据结构与算法】2
65 0
|
存储 算法
第七章 图【数据结构与算法】3
第七章 图【数据结构与算法】3
74 0
|
存储 人工智能 算法
第七章 图【数据结构与算法】1
第七章 图【数据结构与算法】1
89 0
|
测试技术 数据库 uml
UML之旅—九种图
开始我按照自己的思考,将所有的用户、所有的用例都画在了一起,真心的很大、很乱,再加上刚开始画图就有一种抵触的冲动了,就让旁边的师傅给我说了说,她建议我将这些分开
离散数学_十章-图 ( 2 ):图的术语和几种特殊的图(一)
离散数学_十章-图 ( 2 ):图的术语和几种特殊的图(一)
127 0
|
机器学习/深度学习
离散数学_十章-图 ( 2 ):图的术语和几种特殊的图(二)
离散数学_十章-图 ( 2 ):图的术语和几种特殊的图(二)
2597 0
|
存储 算法
【数据结构与算法】图的概述(内含源码)
【数据结构与算法】图的概述(内含源码)
96 0