Graphs and Networks

欢迎来到图论与网络的世界！

欢迎来到进阶数学中最实用且直观的章节之一！在离散数学的这一部分，我们处理的不是平滑曲线或微积分，而是图论与网络（Graphs and Networks）——这是一种数学地图，用于模拟从社交媒体好友关系、神经网络路径，到航空公司航线和互联网等各种结构。如果这看起来和你以前学过的数学有点“不一样”，别担心；重点在于逻辑和连接。让我们开始吧！

1. 基本构件：术语与标记法

在解决复杂问题之前，我们必须先掌握图论的语言。你可以将“图”（Graph）想象成由线连接而成的点的集合。

关键术语

• 顶点（Vertex 或 Node）：图上的点。（复数：Vertices）。
• 弧（Arc 或 Edge）：连接两个顶点的线。
• 度（Degree 或 Order）：与一个顶点相连的弧的数量。比喻：想象一个火车站，度就是接入该站的铁轨数量。
• 关联（Incident）：如果一条弧物理上连接到某个顶点，则称该弧与该顶点“关联”。
• 相邻（Adjacent）：如果两个顶点之间有弧直接相连，则称它们“相邻”。如果两条弧在同一个顶点相交，则称它们相邻。

快速复习：
如果顶点 A 和顶点 B 之间有一条线相连：
1. A 和 B 是相邻顶点。
2. 该线与 A 和 B 均关联。
3. A 的度增加 1。

图的类型

• 简单图（Simple Graph）：没有环（从同一个节点出发又回到该节点的弧）且没有多重边（两个节点之间有多于一条的弧）的图。
• 连通图（Connected Graph）：在图中，你可以通过一系列弧从任何一个顶点到达其他任何顶点。
• 树（Tree）：一个没有圈（cycle）的连通图。它看起来就像树的分支一样！
• 单连通（Simply Connected）：就我们目前的教学范围而言，这指的是那些没有“洞”或复杂重叠连接的图，使它们可以被视为一个整体来处理。

常见误区：学生常误以为“树”必须长得像植物。但在数学中，只要是连通且没有封闭圈的图，就是树！

2. 行走：路径、迹与通路

在图论中，我们如何从 A 移动到 B 非常重要。根据是否重复经过节点或弧，我们有特定的命名方式。

路径层级

• 行走（Walk）：最一般的路径。你可以随意走，重复经过任何顶点或弧。
• 迹（Trail）：不重复经过任何弧的行走。（你仍然可以多次访问同一个顶点）。
• 通路（Path）：不重复经过任何顶点的迹。记忆法：Path = People（人）。人们不喜欢被重复提及！
• 圈（Cycle）：一个封闭的通路。你从同一个顶点出发并回到该点，途中不重复经过任何其他节点或弧。
• 路径（Route）：对行走、迹或通路的统称，可以是开放的（起点和终点不同）或封闭的（起点和终点相同）。

重点归纳：所有的通路都是迹，所有的迹都是行走，但反过来则不成立！

3. 特殊图：\(K_n\) 与 \(K_{m,n}\)

有些图非常常见，以至于它们拥有自己的专属名称与公式。

完全图（Complete Graphs, \(K_n\)）

完全图是指图中每一个顶点都恰好通过一条弧与其他所有顶点相连。我们使用标记 \(K_n\)，其中 \(n\) 是顶点的数量。

神奇公式：具有 \(n\) 个顶点的完全图拥有 \(\frac{1}{2}n(n-1)\) 条弧。

例子：在 \(K_4\) 中，有 4 个顶点。弧的数量 = \(\frac{1}{2} \times 4 \times 3 = 6\)。

二分图（Bipartite Graphs, \(K_{m,n}\)）

二分图被分成两组顶点（我们称之为集合 X 和集合 Y）。弧只连接集合 X 中的顶点与集合 Y 中的顶点。同一集合内的两个顶点之间没有连接。
比喻：一种“舞伴”图，一组是领舞者，另一组是跟随者。

完全二分图（\(K_{m,n}\)）在一个集合中有 \(m\) 个顶点，另一个集合中有 \(n\) 个顶点，且两个集合之间存在所有可能的连接。
弧的数量公式：简单地等于 \(m \times n\)。

4. 欧拉图：遍历的艺术

你知道吗？这个主题起源于“柯尼斯堡七桥问题”。当时的人们想知道是否能走遍整座城市，穿过每一座桥刚好一次并回到起点。

• 欧拉图（Eulerian Graph）：每个顶点的度皆为偶数的图。你可以遍历每一条边刚好一次并回到起点。
• 半欧拉图（Semi-Eulerian Graph）：拥有恰好两个奇度顶点的图。你可以遍历每一条边刚好一次，但必须从一个奇度顶点开始，并在另一个奇度顶点结束。
• 两者皆非：如果奇度顶点多于两个，则你无法在不提笔或重复走过某条边的情况下画出该图！

逐步检查法：
1. 列出每个顶点的度。
2. 计算有多少个奇数度。
3. 0 个奇数？欧拉图。2 个奇数？半欧拉图。多于 2 个？无法遍历。

5. 同构：数学上的双胞胎

如果两个图在本质上是一样的，即使它们的画法不同，我们也称这两个图为同构（Isomorphic）。想象一个由橡皮筋组成的图；如果你可以拉伸并移动顶点，使一个图看起来像另一个而不切断任何连接，那么它们就是同构的。

如何证明两个图是同构的：

• 它们必须拥有相同数量的顶点和弧。
• 它们必须拥有相同的度序列（degree sequence）（按顺序排列的顶点度数列表）。
• 警告！拥有相同的度序列是同构的必要条件，但非充分条件。你还必须检查顶点之间的连接方式是否匹配（例如，如果图 A 中一个度为 3 的顶点与两个度为 2 的顶点相连，那么在图 B 中也必须满足此条件）。

6. 有向图与网络

有时候，连接只允许单向通行。

有向图（Digraphs / Directed Graphs）

在有向图中，弧带有箭头以显示方向。比喻：城市中的单行道。

• 入度（Indegree）：指向某个顶点的弧的数量。
• 出度（Outdegree）：从某个顶点指出的弧的数量。

网络（Networks）

网络只是一个加权图。这意味着每一条弧都分配有一个数字（权重），代表距离、时间或成本等信息。

7. 图的表示法：矩阵

画图固然很好，但计算机更喜欢数字。我们使用两类型的矩阵：

• 邻接矩阵（Adjacency Matrix）：用于图。第 \(i\) 行第 \(j\) 列的数值告诉你顶点 \(i\) 与顶点 \(j\) 之间有多少条弧连接。（对于简单图，通常为 0 或 1）。
• 权重矩阵（Weighted Matrix）：用于网络。矩阵中的数值为弧的权重。如果没有连接，我们通常使用无穷大符号（\(\infty\)）或横线表示。

总结：
图论与网络帮助我们将现实世界的关系转化为数学。无论你是通过观察顶点度数来检查图是否为欧拉图，还是识别同构的“双胞胎”，请记住，关键在于事物是如何连接的，而不是画图看起来有多美观！如果这让你觉得像在解谜，别担心——这本来就是一场谜题挑战！