1.概述

在本教程中,我们将讨论一些最重要的数据结构〇在计算机科学领域

我们将首先学习图论的基础知识,以便熟悉它的概念基础。然后我们会研究机器学习应用中可以找到的图表类型。

在本教程结束时,我们将知道图形是什么以及存在的类型的图形。我们还会知道图形原始组件的特征是什么。

图表理论的基础知识

2.1.图的定义

图是一个结构体包括一组顶点和一组边缘。因此,为了有一个图表,我们需要定义两组的元素:顶点和边缘。

顶点是一个图存在所必需的基本单位.通常情况下,图形必须至少有一个顶点,但没有真正的理论解释为什么会这样。顶点是一种数学抽象概念,它对应于根据某种标准相互关联的对象。

相反,边是可选的,也就是说没有边的图仍然可以被定义.一条边(如果它存在)是一个链接或图中任意两个顶点之间的连接,包括顶点与自身的连接。边缘背后的意思是,如果它们存在,它们表明两个物体之间存在一种关系,我们可以想象这些边缘连接起来。

我们通常表明V = \{v_1, v_2,…, v_n \}顶点的集合,和E = {e_1, e_2,…e_m \}边的集合。然后我们可以定义一个图G随着结构G (V, E)它模拟了两组之间的关系:

注意括号之间的两个集合的顺序,因为按照惯例,我们总是先表示顶点,再表示边。一个图表H (X, Y)因此,这是一种建模顶点集合之间关系的结构吗X和边的集合Y,而不是另外一边。

在我们继续之前,简要说明一下术语:图是数学和网络理论共同研究的课题.两条学科中使用的术语略有不同,但它们总是指同样的概念。对于本文,我们将使用数学术语,但我们可以使用一个转换表如有必要,在两者之间进行翻译。

2.2。顶点的一般属性

现在我们将更详细地关注顶点和边所具有的特征。金宝搏官网188be我们先从顶点开始。

如前所述,图需要顶点,但不一定需要边。事实上,有图是完全可能的G (V, \ O)完全由顶点组成。不与任何其他点相连的顶点,如空图中的顶点,称为孤立的:

我们也说孤立的顶点有度数δ(v) \等于零。在这里,Degree指的是数量事件的边缘一个顶点。

对于不是孤立的顶点它们有一个正度数,我们通常用\δ(v) > 0.顶点的度数可以是任何自然数。

命名叶表示一种特殊的顶点,一个有度数的顶点\δ(v) = 1.这个术语与层次树,同样地,也关注与另一个且仅与另一个顶点相连的顶点。

2.3.标签的顶点

顶点还可以具有与它们相关联的值。这些值可以采用任何格式,对它们没有特定的限制。具有关联值的顶点称为标记的顶点,而没有关联值的顶点被称为未标记

通常,我们可以基于其成对顶点来区分任何两个未标记的顶点。标记顶点之间的比较要求我们研究两个顶点和分配给它们的值的成对:

有关顶点的最后一个注意事项涉及数字V | |在一个图表中。这个数字有特殊的重要性,我们称之为图的顺序。

2.4.边缘的一般属性

我们现在可以研究边缘的特征了。与顶点不同,边不能孤立存在。这是由于考虑到图本身需要顶点才能存在,而与图相关的边也存在。

一条边可以连接图中的任意两个顶点。由一条边连接的两个顶点称为这条边的端点.通过其定义,如果存在边缘,则它有两个端点。

边连接两个以上顶点的图也存在并被称为图超图.本教程并不关注它们,但由于它们的存在,我们不得不提到它们历史当代的重要性为了开发知识图形。

2.5.端点、方向、循环

根据它们是指向顶点还是远离顶点,进一步区分一条边的两个端点是可能的。我们称之为一个传入边缘的边缘,而我们呼叫源自顶点的边缘是一个传出边缘

在上图中,边缘e_ {a,b}连接两(a,b)对应的边不是往复的吗e_ {B}连接B一个.在这种情况下,我们说图表G(\{A, B\}, \ e_{A, B}})是一个有向图,我们称之为边e_ {A、B}一个弧。

也可以无论哪个是该边缘的原点的顶点连接到两个顶点。这种类型的边称为直线,并且任意两个顶点(A, B)由它们连接,可以在两个方向上横贯。看这个的一种方法是想象一条直线e”之间的一个B对应于弧e_ {A、B}加一个弧形e_ {B}

这种思维方式的优点是它能很好地转化为图的邻接矩阵

此外,边缘可以同时是相同顶点的输入边缘和输出边缘。在这种情况下,我们称之为循环。

循环是一种特殊的边,并不存在于所有的图中。我们称无循环图为简单图,以区别于其他图:

最后,我们可以提到边的数量| E |在一个图中是该图的一个特殊参数。我们称这个数字为图形的大小,它有一些特殊的性质,我们稍后会看到。

2.4.图中的路径

具有非空边缘的图表具有路径,其由连接两个顶点的边缘序列组成.我们可以将与有向边序列相关的路径称为有向路径;与无向边相关的路径没有特殊的名称。

观察路径和图之间关系的一种方法是想象一下每个图形都是一个迷宫它的每个顶点都是一个交点:

在该模型中,路径的起始顶点对应迷宫的入口,目标顶点对应迷宫的出口。如果我们使用这个概念框架,我们就可以想象穿过迷宫,留下一条小道,我们称之为路径

一种特殊的路径是遍历图中的所有顶点的路径,这被称为a哈密顿路径.哈密顿路径并不一定存在于所有的图中。我们称包含哈密顿路径的图为可追踪的,因为它可以留下一条覆盖其所有顶点的完整轨迹:

最后,我们可以提到起始顶点和结束顶点重合的路径是特殊的,并且被调用周期.是很重要的检测图中的循环因为寻找路径的算法最终可能会在这些路径上无限循环。

为什么路径在计算机科学中特别重要?这是因为有高效的算法方法,比如迪杰斯特拉算法一个*这样我们就能很容易地找到最短路径。这反过来又允许计算机解决诸如优化流程、物流和处理搜索查询等问题。

3.类型的图表

3.1.空的图

我们之前提到过,只有当图的顶点集不为空时,图才存在。然而,它们的边集也可能是空的。如果是这种情况,我们说图是空的:

一个空的图形G (V, \ O)一直大小| E |= 0.

3.2.的有向图

如上所述,有向图是具有至少一条边的图e_ {A、B}在两个顶点之间一个B哪个没有相应的边e_ {B}在相反的方向连接相同的顶点。

定向图具有它们模拟真实世界关系的特征,我们无法自由地互换主题和对象。作为一般规则,如果我们不确定图形是否应定向或未向导,则图表是指的:

我们只能在有向图的已有有向边的方向上遍历。

对于有向图,我们可以简单地提到,有一些通用的方法来确定一个有向图是否包含最大可能的边缘数量.这是很重要的原因有向图的熵

3.3.无向图

无向图是任意边存在的图e_ {A、B}之间的顶点(A, B)表示存在相应的边e_ {B}

无向图允许在由一条边连接的任意两个顶点之间进行遍历。对于有向图就不一定是这样了。

3.4.连通图和不连通图

我们还可以根据图的路径特征来区分图。例如,我们可以根据是否有路径连接所有顶点对,或者是否有顶点对之间没有任何路径来区分。如果任意两个顶点之间至少有一条路径,则称该图为连通图:

同样地,我们说一个图是不连通的,如果至少有两个顶点彼此分离。

3.5.Hamiltonian-Connected图

哈密顿连通图是指在任意两个顶点之间有一条哈密顿路径的图。注意连通图不一定是汉密尔顿连通的:

汉密尔顿连接的图形始终是一个可追溯的图形,但相反不一定是真的。

3.6。完整的图表

我们说一个图是完全的,如果它包含在所有可能的顶点对之间的一条边。对于一个有序的完全图V | |,它的大小| E |总是| E |= \ FRAC {| v |\ cdot(| v |  -  1)} {2}

所有具有未标记顶点的相同阶完全图都是等价的。

3.7。世界杯

竞赛图是一种只包含有向边的完全图:

该名称源于其频繁应用于体育赛事的匹配组成。

3.8。加权图

最后一种图是加权图。加权图是这样一种图,它的边被赋予了一个权值(即一个数值):

机器学习中常用的典型加权图是人工神经网络.我们可以把神经网络的概念定义为定向加权图形每个顶点都有一个额外的顶点激活函数分配给它。

4.结论

在本教程中,我们学习了图论的概念基础。我们还熟悉了图、顶点、边和路径的定义。

我们还研究了我们可能遇到的图的类型,以及它们在顶点、边和路径方面的可预测特征。

1评论
最古老的
最新的
内联反馈
查看所有评论
劳尔M马林
13天前

感谢您提供的非常简明但非常全面的教程

这篇文章的评论已经关闭!