图论入门及基础概念（图篇）

程序员文章站 2022-03-26 10:36:59

...

图篇

这是第一次写博客，为了下载积分而来。
随便写些，各位大佬们多多指。

本次内容是关于图论的引入的，内容如下：

矩阵引入
什么是图？其如何表示？
图论起源之七桥问题
图论引入
图论相关基本概念
图论的表示引入
图的表示法

矩阵引入

线性代数学的好的可以直接跳过，当然，看不懂的也可以直接跳过，这部分引入只是计为了后面计算上方便，

矩阵可以用在生活的方方面面，出现在各个学科中，
例如，我们如何用矩阵（向量）来描述化学反应方程式：

首先，用向量描述一个物体必须先划分维度。

由于原子守恒原理我们知道氧原子和氢原子相互独立，互不相关。
所以我们假设两个维度空间为氧空间和氢空间
并且这两个空间相互垂直（即线性无关）

基于空间运算的封闭性，我们得出该方程式存在的完备空间S为：

由于向量空间运算的封闭性，我们有：

我们分别将氧气和氢气表示为该空间下的向量点：

于是化学方程式配平便变成了向量之间的运算：

由于氧气和氢气是该完备空间的基，即单质。
容易运算出答案：

图及其表示

什么是 图

要说什么是图，这个有点不太好说，概念的东西太抽象，我还是直接说图的表示吧，知道图的表示形式，自然也就知道什么是图了。

·图的表示一般是分为两块的：

（1）某类具体事物
（2）这些事物之间的联系

·而在图论中，只存在两种形态：

①节点
②边

这两种形态通常这样对应：

由于这种对应关系，我们通常把这种关系转化为矩阵描述，在前言中我们提到了一个例子：

在这里，具体事物即：

抽象事物（事物间的联系）即其中的数量关系。

于是我们将化学方程改为如下矩阵式：

我们可以看到，矩阵分为两块：

PS: 所以说，用矩阵描述问题能使描述过程更加清晰化，建议采用。

图论起源之七桥问题

七桥问题很经典，我们都知道大数学家欧拉将其转为一笔画的问题，并顺利解决，由此开创了图论的先河。

用下图举个例子：

若将其看做画线问题：

对于任意非起始点，我们要一笔通过他只有如下两种可能：

(1)两条路线：

有进必有出，必然是能够一笔完成的

(2)四条路线：

由于通过外界一圈以后又回来所以对于这种偶数条线路，可以等效为如下形式：

即将该节点视为另外一个圈起始点，其中的闭圈必然能够由一笔画完成，由于该圈可以独立出去，我们将该圈等效为不存在，便将偶数边节点等效为如下一进一出的两条边节点:

三条路线：

三条线路相对复杂，但它的进出也只有如下两种可能形式：

同样，我们运用等效原理将其等效为如下形式：

我们将其中的闭圈化简去掉，即等效为：

所以，该节点必然是一笔画的起点（右图形式）或者终点（左图形式）

所以，我们得出了如下的基本结论：

①拥有偶数边的节点
可以等效为只有一进一出两条边的点。
即该点等效为过程点。
②拥有奇数边的节点
可以等效为要么进，要么出的单边的节点。
即该点等效为起始点。

唧唧歪歪了这么多，我们还是回到七桥问题吧:

那么问题来了：

问：该图能否由一笔画完成，并说明理由。

首先我给出答案不能，理由是：

A、C、D、B节点均为奇数边
故等效为4个起始点，而一个一笔画的图最多只能有两个起始点。

PS:若要求一笔画的终点和起点重合，则图节点中必然全为偶数边，这就是十分显然的了。

图论引入

图论，顾名思义，必然是关于图的理论咯
由于图的表示分为两块：

①节点
②边

我们不妨假设对于图图论入门及基础概念（图篇）：

①节点集记为:
，
② 边集记为:

那么问题来了：

我们该如何去表示其中的某个节点或边呢？
PS：马克思说：“人的本质不是单个人所固有的抽象物，在其现实性上，它是一切社会关系的总和。”（《马克思恩格斯选集》第2版第1卷第60页）

附即兴打油词一首：
《如果说》—妖米
如果说人类是一个集合，那么某个人便由他的社会关系总和来定义。
如果说节点集是一个集合，那么某个节点便由他的边的总和来定义。
如果说边集是一个集合，那么某条边便由他连接的点的总和来定义。
2018-9-4 —— 23：12