图的基本概念

这篇具有很好参考价值的文章主要介绍了图的基本概念。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

图的基本概念

一个图 G 它可以由顶点集(图 G 中顶点的有限非空集) V 和边集(图 G 中顶点之间的关系集合) E 所组成。图中顶点个数也可以称为图的阶;任何一条边的两头必须连接某一个顶点。图不可以是空,即顶点集 V 一定是非空集,但边集 E 可以是空集。

子图,数据结构,图论,数据结构,算法

有向图 无向图
无向图里的各条边我们可以把它称为无向边(或者简称弧) 有向图里把各条边称为有向边(或者简称为边)
<v,w>,v:弧尾 w:弧头 弧头弧尾顺序调换表示的不一样 (v,w) 或(w,v) 这两种方式等价

简单图:在这个图里不存在重复的边,并且也不存在顶点到自身的边。

子图,数据结构,图论,数据结构,算法

多重图

一个图里存在重复的两条边或者自身连向自身的边。

子图,数据结构,图论,数据结构,算法

顶点的度

在无向图中,指依附于这个顶点的边到底有多少条,记为 TD(V),V指的是某一特定的点。

子图,数据结构,图论,数据结构,算法

在有向图中,入度是以顶点为终点的有向边的数目,记为 ID(V);出度是以顶点为起点的有向边的数目,记为 OD(V);顶点 v 的度等于入度和出度之和 TD(V) = ID(V) + OD(V).

子图,数据结构,图论,数据结构,算法

路径-----顶点 vp 到顶点 vq 之间的一条路径是指顶点序列

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

简单路径-----在路径序列中,顶点不重复出现的路径称为简单路径

简单回路-----除了第一个顶点和最后一个顶点之外,其余的顶点都不重复出现的回路

路径长度-----两个顶点之间的路径,这个路径上总共有多少条边

点到点的距离-----两个顶点之间最短路径的长度作为顶点到顶点之间的距离;如果两个顶点之间根本就不存在路径的话,那么我们需要把它们之间的距离记为∞(无穷)。

无向图中,若从顶点v到顶点w有路径存在,则称v和w是连通的;有向图中,若从顶点v到顶点w和从顶点w到顶点v之间都有路径,则称这两个顶点是强连通的.

注意:

  1. 对于 n 个顶点的无向图 G, 若 G 是连通图,则最少有 n -1 条边; 若 G 是非连通图,则最少有子图,数据结构,图论,数据结构,算法条边.

  2. 对于 n 个顶点的有向图 G, 若 G 是强连通图,则最少有 n 条边(形成回路)

子图与生成子图

子图:一个图里边有一些顶点集和边集,取出几个顶点,然后再取出整个边集当中的某一个子集,用这样的方式构建的这个图就是原图的一个子图。注意并不是从原图当中任意选择几个顶点,任意选择几条边都能构成子图的,因为子图首先它必须是一个图。

子图,数据结构,图论,数据结构,算法子图,数据结构,图论,数据结构,算法

生成子图:子图里边包含了原图当中的所有顶点,那么这个子图就可以称为原图的一个生成子图。

子图,数据结构,图论,数据结构,算法

对于有向图的子图和生成图的概念一样。

连通分量(无向图)与强连通分量(有向图)

连通分量:无向图中的极大连通子图(子图必须连通,且包含尽可能多的顶点和边

子图,数据结构,图论,数据结构,算法

强连通分量

如图在图 G 中A,B,E,C,D是强连通的,将这个部分择出来就是一个极大的强连通分量。而顶点 F 和 A,B,C,D,E不是强连通的(从其他顶点到 F 的路径存在,而 F 到其他顶点的路径不存在),所以 F 和 A,B,C,D,E是不强连通的。

子图,数据结构,图论,数据结构,算法

生成树和生成森林

生成树:对于一个连通的无向图,它的生成树指的是这个图里边的全部顶点的一个极小的连通的子图。也就是说这个子图它要包含原图里边的全部顶点,要包含全部顶点,同时要保证这个子图连通,而且要极小(指在这个子图里边的边要尽可能的少,但要保持连通)。若图中顶点数为 n ,则他生成树含有 n-1 条边。若砍去一条边,则会变成非连通图;若加上一条边则会形成一个回路。

子图,数据结构,图论,数据结构,算法

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

子图,数据结构,图论,数据结构,算法

边的权,带权图/网,带权路径长度

边的权------为图中的每条边标上具有特殊含义的数值,这个数值则为边的权。

带权图/网------边上带有权值的图称为带权图(或网)

带权路径长度------指这条路径上所有的边的权值之和称为带权路径长度

特殊形态的图

无向完全图------其中的任何两个顶点之间都存在边子图,数据结构,图论,数据结构,算法

有向完全图------其中的任意两个顶点之间都存在着方向相反的两条弧子图,数据结构,图论,数据结构,算法
稀疏图------边很少的图

稠密图------边很多的图
子图,数据结构,图论,数据结构,算法
------图里边不存在回路,并且这个图中各个节点是相互连通的,它是一个连通图。那么这种形状的图其实就是一个树

对于 n 个顶点的数一定有 n 减一条边,如果说 n 个顶点的图它的边大于 n-1 条,那么这个图一定是有回路的
子图,数据结构,图论,数据结构,算法

对于无向图来说,森林里边各个子图是极小的,同时各个子图又是连通的。

子图,数据结构,图论,数据结构,算法

有向树:只有一个顶点的入度是0,然后其他所有顶点的入度都是1

子图,数据结构,图论,数据结构,算法

注意:树是一个连通图,各个顶点之间是连通的,但是有向树,它并不是一个强连通图。
子图,数据结构,图论,数据结构,算法子图,数据结构,图论,数据结构,算法文章来源地址https://www.toymoban.com/news/detail-628202.html

到了这里,关于图的基本概念的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图的基本概念辨析,包括连通图、极大连通子图、连通分量、强连通图、极大强连通子图等

    概念(1-4)都是针对无向图的   图中从一个顶点到达另一顶点,若存在至少一条路径,则称这两个顶点是连通着的。例如图 1 中,虽然 V1 和 V3 没有直接关联,但从 V1 到 V3 存在两条路径,分别是 V1-›V2-›V3 和 V1-›V4-›V3,因此称 V1 和 V3 之间是连通的。 图 1 顶点之间的连

    2024年02月15日
    浏览(57)
  • 图论_(1)_图的基本概念

    图(graph) 是由顶点集合和顶点间的二元关系集合(即边的集合或弧的集合)组成的数据结构,通常可以用 G ( V , E ) G(V,E) G ( V , E ) 表示 顶点集合(vertext set) 用 V ( G ) V(G) V ( G ) 表示,其中元素称为 顶点(vertex) ,用 u 、 v u、v u 、 v 等符号表示。 边的集合(edge set) 用 E ( G ) E(G) E ( G

    2024年02月05日
    浏览(45)
  • 离散数学-图论-图的基本概念(11)

    1.1 图的定义 定义1: 一个 无向图 G是一个有序的二元组V,E,其中 (1)V是一个非空有穷集,称为顶点集,其元素称为顶点或结点。 (2)E是无序积VV的有穷多重子集,称为边集,其元素称为无向边,简称边。 定义2: 一个 有向图 D是一个有序的二元组V,E,其中 (1)V是一个非

    2024年02月13日
    浏览(47)
  • 数据结构——图的基本定义以及图的存储结构,邻接矩阵,邻接表

    目录 图的定义和术语 图的存储结构 顺序存储结构—邻接矩阵 链式存储结构 邻接表 邻接多重表 十字链表 图的遍历 图的连通性问题 有向无环图及其应用 最短路径 图的定义:图是一种非线性的复杂的数据结构,图中的数据元素的关系是多对多的关系 ,在图中我们常常把数

    2024年02月04日
    浏览(55)
  • 数据结构--图的基本操作

    使用的存储模式: 图的基本操作: • Adjacent(G,x,y):判断图G是否存在边x, y或(x, y)。 • Neighbors(G,x):列出图G中与结点x邻接的边。 • InsertVertex(G,x):在图G中插入顶点x。 • DeleteVertex(G,x):从图G中删除顶点x。 • AddEdge(G,x,y):若无向边(x, y)或有向边x, y不存在,则向图G中添加该

    2024年02月16日
    浏览(50)
  • 【数据结构】图的基本操作

    一、问题描述 分别以邻接矩阵和邻接表作为存储结构,实现以下图的基本操作: 增加一个新结点v,Insert(G,v); 删除顶点v及其相关的边,Delete(G,v); 增加一条边v,w,Insert(G,v,w); 删除一条边v,w,Delete(G,v,w); 二、设计思路 1、邻接矩阵实现:         邻接矩阵实现图的基本

    2024年02月06日
    浏览(46)
  • 数据结构入门(C语言版)图的概念和功能函数实现

    图是一种比线性表和树更复杂的数据结构。在线性表中,数据元素之间仅有 线性关系每个元素 只有 一个直接前驱 和 一个直接后继 。在树形结构中,数据元素之间存在明显的层次关系,并且每层的元素可能和下一层的多个元素(即其孩子结点)相邻,但只能和上一层的个元素(即其

    2024年02月06日
    浏览(49)
  • 【图论】图的概念和基本术语(顶点、边、度、路径等)

    在数学和计算机科学中,图是由 顶点(节点) 和 边(连接) 组成的一种 数据结构 ,用于描述对象之间的关系。图是一种广泛应用于许多领域的数学概念,包括计算机科学、网络分析、运筹学、社交网络分析等。 图可以用于表示各种现实世界中的问题,如社交网络中的用户

    2024年02月07日
    浏览(52)
  • 【数据结构】一、数据结构的基本概念

    数据是 信息的载体 ,是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序 识别 和 处理 的符号的集合。 数据是计算机程序加工的原料。 数据元素 是数据的基本单位。通常作为一个整体进行考虑和处理,用一个 数据元素 描述一个个体。一个数据元素可

    2024年03月10日
    浏览(88)
  • 【数据结构与算法】一、数据结构的基本概念

    抽象数据类型(ADT)定义举例:Circle的定义 如何处理杂乱无章且多样化的数据: 数据元素 :数据中的个体被称为数据元素。 数据对象 :性质相同的数据元素组成的集合。 数据结构 :数据元素加上数据元素之间的关系,就形成了数据结构。 逻辑结构 :数据结构的逻辑模型。

    2023年04月17日
    浏览(97)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包