1.2 图的基本知识

图是我们日常生活中一种常见的数据结构，也是一种可以表示复杂关系的数据结构。图在计算机科学中一直是研究的热点和难点。因为万物互联都可以抽象成图模型，所以可以将图及图的拓扑结构的研究结果拓展到新的领域。

1.2.1 什么是图

在离散数学和计算机科学领域，图被抽象为由多个点及连接这些点的线所构成的对象，如图1-1所示。图中有多个点，这些点被称为顶点或者节点。顶点之间由线连接，这些线被称为边。

图关系可以应用于许多领域，如社会学、语言学、化学、物理学、植物学等，因为它可以描述实体之间的关系。在社会学中，图可以表示个体之间的关系。在语言学中，图可以用于分析句子的结构和语法。在化学中，图可以表示以原子为顶点、以化学键为边的化合物。图结构还可以应用于知识图谱领域，让科学家在自然语言处理、图像处理以及其他人工智能领域拥有更强大的工具。例如，文本段落中的实体可以构建成网络来用于问答系统中，文本之间的相似度可以构建成图来实现文本分类。科学家还使用机器学习分析、研究图结构，这个领域的研究成果受到越来越多的关注。例如，我们可以使用图结构进行节点分类、链接预测和聚类分析，最具代表性的实例是推荐系统。对于推荐系统，一般是构建在用户和产品图上，根据用户的购买习惯给用户推荐感兴趣的产品，我们可以把它看作一个异构图上的链路预测问题。此外，图结构也可以用于生物医疗领域，例如预测蛋白质的作用界面等。

1.2.2 图中基本元素及定义

如图1-1所示，图中所有的边都是没有方向的，所以它被称为无向图。反之，如果图中所有的边都是有方向的，那么它被称为有向图，如图1-2所示。

例如：可以把网页链接路径抽象成有向图，如果一个网页指向另一个网页，则这两个网页之间可以用一条具有指向的边进行连接。有向图在应用过程中不仅和顶点、边有关，还和连接的方向有关。

我们可以对图进行精准的数学定义。一个图可以表示为G={V,E}，其中V={v₁,…,v_N}是N个节点的集合，E={e₁,…,e_M}是M个边的集合。如果连接一条边的两个节点并没有顺序之分，即，则这种图结构被称作无向图。而在有向图中，该等式可能是不成立的，即。

度指在图G={V,E}中，节点v_i∈V的度定义为图G中与节点v_i相关联的边的数目，公式为

式中，L_ε（·）被定义为指示函数[1]，且

平行边指连接同一对节点的多条边。自环边指从同一个节点连接到自己的边。没有平行边也没有自环边的图称为简单图；否则，称为非简单图。如图1-3所示。图中的各个节点不一定都连在一起成为一个整体，那些和图中的节点都不相连的节点称为孤立节点。没有连成一个整体的图叫作非连通图。保持最大连通性的部分称为连通分支。

对于图来说，节点之间是否相连是最重要的，而图的描述就不那么重要了。在生活中，我们经常会看到在描述图的过程中，图的边上会带上一个非负整数值，这种图被称为赋权图，这个非负整数值被称为权值。赋权图不仅可以在边上赋值，在节点处也可以赋值，这种在节点处赋值的图被称为顶点赋权图，在边上赋值的图被称为边赋权图，如图1-4所示。在一张表示两个城市路径连接的图中，我们可以有多种选择来找到最短路径。因此，在表示所有路径的图上，我们可以通过边上的权值大小来规划一条合适的路径，找到最优解。

前文总结了图的数学表示方法，下面介绍计算机科学中是如何表示图数据结构的。在计算机科学中，我们可以用邻接矩阵来表示图。

邻接矩阵：给定一个图G={V,E}，其邻接矩阵表示为A∈{0,1}N×N，邻接矩阵A的行列元素可以表示为A_ij，它表示v_i和v_j的连接关系，即如果v_i和v_j相邻，则A_ij=1，否则A_ij=0，即

在无向图中，若v_i和v_j相邻，A_ij=A_ji。很显然，无向图的邻接矩阵是一个对称矩阵。

在图1-5中，节点的集合可以表示为V={v₁,v₂,v₃,v₄}，边的集合可以表示为E={e₁,e₂,e₃,e₄,e₅}，那么图G={V,E}的邻接矩阵可以表示为

如图1-5所示，与节点v₄相邻的节点有3个（v₁,v₂,v₃），所以它的度为3。此外，该图的邻接矩阵中第4行有3个非零元素，这同样意味着v₄的度为3。

邻域：在图G={V,E}中，节点v_i的邻域N（v_i）是所有和它相邻的节点的集合。对于节点v_i，邻域N（v_i）中的元素个数等于v_i的度，即d（v_i）=|N（v_i）|。一个图G={V,E}中所有节点的度之和是图中边的数量的两倍：

这里有一个推论，即无向图的邻接矩阵的非零元素个数是边的数量的两倍。

如图1-5所示，在图G={V,E}中共有5条边，所有节点的度之和为10，并且邻接矩阵的非零元素的个数也是10。

前文已经讲过连通图的概念，这里继续讲解关于图中连通度以及和连通度有关的一些基本概念。连通度是图的一个比较重要的性质。在图1-3中，并不是所有的节点都连通。在图G={V,E}中，途径是指节点和边的交替序列，从一个节点开始至另一个节点结束，其中每条边和紧邻的节点相关联。

从节点u开始到节点v结束的途径可以表示为u-v。途径长度是途径中边的数量。

边互不相同的途径称为迹。节点各不相同的途径称为路，也称为路径。

如图1-5所示，在图G={V,E}中，（v₁,e₅,v₄,e₃,v₃,e₂,v₂）是一条长度为3的v₁-v₂途径，它是一条迹也是一条路。

在图G={V,E}的邻接矩阵A中，我们可以用An表示该邻接矩阵的n次幂。那么An的第i行第j列的元素等于长度为n的v_i-v_j途径的个数。

子图是图的一部分。假设图G={V,E}的子图为G′={V′,E′}，如果V′⊆V并且E′⊆E，则称G′为G的子图。如果在子图中任意一对节点之间至少存在一条路，且V′中的节点不与任何V/V′中的节点相连，那么G′就是一个连通分量或者连通域。如果一个图只有一个连通分量，那么G是连通图。从图1-6中可以得到，图上有两个连通分量。

最短路径：给定图G={V,E}中的一对节点V_s、V_t，且P_st表示节点V_s到节点V_t的所有路的集合。那么，节点V_s与节点V_t间的最短路径定义为

式中，p表示P_st中一条长度为|p|的路，表示最短路径。任意给定的节点对之间可能有多条最短路径。

在实际应用中，图的应用要复杂得多。所以根据实际情况，下面介绍几个和复杂图相关的基本概念。

对于图G={V,E}，如果称为G的补图。简单地说，G和有相同的节点集合，G和边的集合互补，即G中有边的地方，中没有，反之亦成立，如图1-7所示。

前文提到推荐系统涉及对异构图上链路的预测问题。所以，这里引出同构概念。对于两个图G₁=（V₁,E₁）和G₂=（V₂,E₂），如果从V₁到V₂满足同构映射条件，则称G₁和G₂是同构（同质）的。所谓同构映射，是指一种映射需要满足如下条件：对于任意两个节点u,v∈V₁，都有（f（u）,f（v））∈E₂，当且仅当（u,v）∈E₁。如果f是同构映射，很明显G₁的节点V₁和G₂的节点V₂有相等的度。在分析图神经网络的表达能力时，我们需要对图的同构进行分析。

再来看看异构图，异构图也称为异质图。一个异构图G={V,E}由一组节点V={v₁,v₂,…,v_n}和一组边E={e₁,e₂,…,e_n}构成。其中，每个节点和每条边都对应一种类型，T_n表示节点类型的集合，T_e表示边类型的集合。一个异构图存在两个映射函数：将每个节点映射到对应类型的ϕ_n:V→T_n以及将每条边映射到对应类型的ϕ_e:E→T_e，如图1-8所示。

从上面的分析可以看出，同构图是节点类型和边类型只有一种的图。异构图是节点类型和边类型之和大于2的图。在推荐系统中，异构图非常常见，如图1-9所示。

在搜索和推荐系统中，我们还会利用二分图来解决一些实际的算法问题。比如，在电商网站，节点分为用户和商品两类，节点之间存在的关系有浏览、收藏、购买等。用户的历史行为可以构建成一个二分图，如图1-10所示。

假设给定一个图G={V,E}，G是一个二分图，当且仅当V=V₁∪V₂，V₁∩V₂=Ø，并且对于所有的边都有和。