Task02：图理论基础

在这一章中主要讲了图的相关基础知识，包括图的定义、图的定义、图的性质、图的表示和图的类型。以及这一章有些基础代码关于如何创建一个图以及网络平均度的计算等。

飞书链接：https://oq07ful5ge8.feishu.cn/wiki/MdVRwAnNAiG27VkPrghcbRWCnOf?from=from_copylink

一、柯尼斯堡七桥问题

柯尼斯堡七桥问题（德语：Königsberger Brückenproblem；英语：Seven Bridges of Königsberg）是图论中的著名问题。这个问题是基于一个现实生活中的事例：当时东普鲁士柯尼斯堡（今日俄罗斯加里宁格勒），市区跨普列戈利亚河两岸，河中心有两个小岛。小岛与河的两岸有七条桥连接。在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍？——葡萄书

莱昂哈德·欧拉在1736年提出将这个问题转化为一个几何问题，即将每块陆地抽象为一个点，每座桥抽象为连接两个点的线。这样，问题就变成了是否存在一条路径，可以从一个点出发，经过每条线恰好一次，最后回到起点。

欧拉通过分析发现，如果一个图形可以一笔画成，那么它必须满足以下条件之一：

图形中所有点都是偶点（即与该点相连的线的数量是偶数）。
图形中只有两个奇点（即与该点相连的线的数量是奇数），且这两个奇点必须是路径的起点和终点。

在柯尼斯堡七桥问题中，欧拉发现所有点都是奇点，因此不存在一条路径可以满足要求。换句话说，无法从任意一个起点出发，经过每座桥恰好一次，最后回到起点。

二、图的定义

图（Graph）是一种数学结构，用于表示对象之间的关系。它由两个集合组成：节点（Vertex）集合和边（Edge）集合。通常图表示为 G=\{V,E\}，

其中 V=\{v_1,…,v_N\} 是数量为 N=∣V∣ 的节点的集合， E=\{e_1,…,e_M\} 是数量为 $$M$$ 的边的集合。

节点（Vertex）

节点是图的基本元素，用于表示图中的对象或实体。节点通常用点或圆圈表示，并可以用一个唯一的标识符来标记。

边（Edge）

边是连接两个节点的线段，用于表示节点之间的关系。边可以是有向的（Directed Edge）或无向的（Undirected Edge）。

有向边：表示从一个节点到另一个节点的单向关系，通常用箭头表示方向。
无向边：表示两个节点之间的双向关系，没有特定的方向。

边可以具有权重（Weight），用于表示关系的重要性或强度。权重可以是正数、负数或零，具体取决于应用场景。

代码中在使由于NetworkX在绘制图时使用了默认的布局算法——随机布局所以创建出来的图的节点是随机的，可以使用pos = nx.circular_layout(g)进行固定。

三、图的性质

以下是一些常见的图的性质：

无向图和有向图：根据边的方向性，图可以分为无向图和有向图。无向图中的边没有方向，表示顶点之间的双向关系；而有向图中的边有方向，表示顶点之间的单向关系。
完全图：完全图是指任意两个顶点之间都有边相连的图。无向完全图中，每个顶点与其他所有顶点都有边相连；有向完全图中，每个顶点与其他所有顶点都有有向边相连。
稀疏图和稠密图：根据边的数量，图可以分为稀疏图和稠密图。稀疏图是指边的数量相对较少的图，而稠密图是指边的数量相对较多，接近完全图的图。
网：网是指边或弧带有权值的图，用于表示边或弧的代价或距离。
邻接和关联：邻接是指两个顶点之间有边或弧相连的关系，而关联是指边或弧与顶点之间的关系。
顶点的度：顶点的度是指与该顶点相关联的边的数量。在无向图中，顶点的度是与该顶点相连的边的数量；在有向图中，顶点的度分为入度和出度，入度是指以该顶点为终点的有向边的数量，出度是指以该顶点为起点的有向边的数量。
平均度：是一个表达网络整体性质重要的参数。对于无向图来说，平均度的计算为 \bar{d}(G) = \frac{1}{N}\sum\limits_{i = 1}^Nd_{i} = \frac{2M}{N}对应了代码中的avg_degree = 2*num_edges/num_nodes。
路径和回路：路径是指图中连续的边或弧所构成的顶点序列，而回路是指起点和终点相同的路径。简单路径是指除了起点和终点外，其他顶点都不相同的路径，简单回路是指除了起点和终点外，其他顶点都不相同的回路。
图的连通性：图的连通性是指图中任意两个顶点之间是否存在路径。连通图是指任意两个顶点之间都存在路径的图，非连通图是指存在两个顶点之间没有路径的图。

四、图的连接表示

邻接矩阵

邻接矩阵是一种二维数组，用于表示图中节点之间的连接关系。矩阵的行和列分别对应图中的节点，矩阵中的元素表示节点之间的连接关系。如果节点i和节点j之间存在连接，则邻接矩阵中对应位置的元素值为1，否则为0。邻接矩阵适用于稠密图，即节点之间的连接相对较多的图。

关联矩阵（Incidence Matrix）

关联矩阵是一种用于表示图中顶点和边之间连接关系的矩阵。它是一个n x m的矩阵，其中n表示图中的顶点数量，m表示边的数量。关联矩阵中的元素dij表示顶点i和边j之间的关系。

对于有向图，关联矩阵的元素定义如下：

如果顶点i是边j的起点，则 d_{ij} = 1
如果顶点i是边j的终点，则 d_{ij} = -1
如果顶点i与边j无关，则 d_{ij} = 0

对于无向图，关联矩阵的元素定义如下：

如果顶点i和边j相关联（即顶点i在边j上），则 d_{ij} = 1
如果顶点i与边j无关，则 d_{ij} = 0

关联矩阵的特点包括：

对于有向图，每一列只有两个非零元素，一个是+1，一个是-1，且每一列的元素之和为零。
对于无向图，每一列有且只有两个1。
关联矩阵的每一行中的所有元素之和对应于该行顶点的度。

拉普拉斯矩阵（Laplacian Matrix）

拉普拉斯矩阵是图论中用于描述图的拓扑结构和性质的矩阵。它是一个n x n的矩阵，其中n表示图中的顶点数量。拉普拉斯矩阵可以通过度矩阵和邻接矩阵来计算得到。

拉普拉斯矩阵的定义如下：

对于无向图，拉普拉斯矩阵 L = D - A，其中D是度矩阵，A是邻接矩阵。
对于有向图，拉普拉斯矩阵 L = D_{out} - A（使用出度矩阵）或 L = D_{in} - A（使用入度矩阵）。

拉普拉斯矩阵的特点包括：

拉普拉斯矩阵是半正定矩阵。
拉普拉斯矩阵的特征值中0出现的次数等于图的连通区域的个数。
拉普拉斯矩阵的最小特征值是0，对应的特征向量为全1列向量。
拉普拉斯矩阵的每一行的行和为0。

区别和联系

关联矩阵和拉普拉斯矩阵都是图论中常用的矩阵表示方法，但它们的侧重点和应用场景有所不同。

关联矩阵主要关注图中顶点和边之间的连接关系，通过关联矩阵可以方便地获取图的信息，如顶点的度数、边的数量、图的连通性等。它通常用于描述图的拓扑结构和连接关系，以及分析图的性质和特征。

拉普拉斯矩阵则更侧重于描述图的拓扑结构和性质，它通过度矩阵和邻接矩阵来计算得到，可以用于图的聚类、分割、特征提取等方面。拉普拉斯矩阵在图论、机器学习、计算机视觉等领域具有广泛的应用。

五、图的类型

文章中图的类型并没有细致的分，我总结了根据五种根据不同的属性和结构的分类，以下是一些常见的图的类型：

根据边的方向性分类：

无向图（Undirected Graph）：边没有方向性，表示顶点之间的对称关系。
有向图（Directed Graph）：边有方向性，表示顶点之间的非对称关系。

根据边的连接方式分类：

简单图（Simple Graph）：图中没有重边（即没有两个顶点之间有多条边）和自环（即没有顶点到自身的边）。
多重图（Multigraph）：图中允许有重边，但不允许有自环。
伪图（Pseudograph）：图中允许有重边和自环。

根据图的连通性分类：

连通图（Connected Graph）：任意两个顶点之间都有路径相连。
非连通图（Disconnected Graph）：图中至少存在两个顶点之间没有路径相连。
强连通图（Strongly Connected Graph）：对于有向图，任意两个顶点之间都有双向路径相连。
弱连通图（Weakly Connected Graph）：对于有向图，如果忽略边的方向，任意两个顶点之间都有路径相连。

根据图的规则性分类：

规则图（Regular Graph）：图中每个顶点的度数都相等。
二分图（Bipartite Graph）：图的顶点可以分成两个不相交的集合，使得每条边都连接不同集合中的顶点。
完全图（Complete Graph）：图中任意两个顶点之间都有边相连。

根据图的生成方式分类：

生成树（Spanning Tree）：连通图的生成树是包含图中所有顶点且没有回路的子图。
平面图（Planar Graph）：图可以画在平面上，使得边之间没有交叉。