欢迎来到图论（Graphs）的世界！
在进阶数学（Further Mathematics）中，当我们谈论“图”（Graphs）时，指的并非你在 GCSE 阶段所学的 \(x\) 和 \(y\) 轴图表。这里我们要探讨的是离散数学（Discrete Mathematics）。试想一下伦敦地铁的路线图，或是社交媒体上人与人之间的关系网，这些都是由点和连接点的线所构成的网络，这就是我们这里所说的“图”！
在本章中，我们将学习描述这些链接的专业术语，并探索隐藏在背后的运作规律。如果刚开始接触到许多新词汇，请别担心——一旦你看出了当中的规律，就会发现这部分数学其实非常有逻辑且直观。
1. 图的词汇表
要像一位离散数学家那样沟通，你需要了解图的“解剖结构”。让我们拆解最关键的术语。
基础知识
- 顶点（Vertex，复数：Vertices）： 图中的“点”。你可以把它们想象成地图上的城市。
- 边（Edge）： 连接点与点的“线”。你可以把它们想象成城市之间的道路。
- 度数（Degree 或 Valency）： 与一个顶点相连的边的数量。如果一个城市有三条路通往外面，它的度数就是 3。
路径与连接
- 迹（Trail）： 一个边的序列，其中没有任何边被重复使用。
- 环（Cycle）： 一个封闭的迹。你从某个顶点出发，沿着路径走，在不重复任何边的情况下回到起点。
- 连通图（Connected Graph）： 一个图，你可以在其中透过边从任何一个顶点到达另一个顶点。图中没有“孤岛”。
- 子图（Subgraph）： 大图中的一小部分。就像集合论中的子集一样，它是从原图中选取部分顶点和边所组成的。
特殊属性
- 回路（Loop）： 一个起点和终点都在同一个顶点上的边。
- 多重边（Multiple Edges）： 当两个顶点之间有多于一条边连接时。
- 简单图（Simple Graph）： 没有回路且没有多重边的图。这是图中最“干净”的形式。
- 细分（Subdivision）： 将一条边替换为两条边，并在中间加入一个新顶点。想象一下在路中间新增一个巴士站。
快速复习：
顶点（Vertex）是点。边（Edge）是线。度数（Degree）是连接到该点的线的数量。环（Cycle）是一趟绕圈的旅程。
2. 树与完全图
有些图拥有非常特殊的结构，这让它们在解决问题时非常实用。
什么是树（Tree）？
在数学中，树是一种连通且没有环的图。
类比： 想象家谱。它会不断分支出去，但永远不会绕回来形成一个圆圈。
完全图（Complete Graphs, \(K_n\)）
完全图是指每一个顶点都恰好与其他所有顶点透过一条边相连的图。我们使用符号 \(K_n\) 来表示，其中 \(n\) 是顶点的数量。
例子： 在 \(K_4\) 中，共有 4 个顶点，每个顶点的度数都是 3。
二分图（Bipartite Graphs）
在二分图中，顶点被分为两个独立的集合。边只能连接来自第一个集合的顶点与第二个集合的顶点。你永远不可能有一条边连接同一个集合内的两个顶点。
现实生活例子： 想象一组“工作”和一组“工人”。你将工人与他们有资格担任的工作连接起来，你绝不会把工作与工作连接在一起！
重点总结：
树没有环。完全图（\(K_n\)）是完全连接的。二分图则像是在“配对”两个不同的群体。
3. 邻接矩阵（Adjacency Matrices）
有时候，画图会显得很混乱。我们可以用一个数字表格来表示同样的信息，这称为邻接矩阵。
在邻接矩阵中：
1. 行和列代表各个顶点。
2. 格子内的数字告诉你那两个顶点之间连接了多少条边。
常见错误：
对于简单图而言，主对角线（从左上到右下）永远会是零，因为简单图没有回路（顶点不会与自身连接）。
4. 欧拉图与哈密顿图
本节的主题是“可遍历性”——我们能否遵循特定的规则走遍整个图？
欧拉图（Eulerian Graphs）
如果一个图可以让你从某个顶点出发，走过每一条边恰好一次，并回到起点，那么它就是欧拉图。
诀窍： 一个连通图是欧拉图的充要条件是每个顶点的度数都是偶数。
半欧拉图（Semi-Eulerian Graphs）
如果你可以走过每一条边恰好一次，但最终停在与起点不同的顶点上，它就是半欧拉图。
诀窍： 这发生在恰好有两个顶点具有奇数度数的情况下（分别作为起点和终点）。
哈密顿图（Hamiltonian Graphs）
哈密顿图的情况略有不同。这里我们关注的是顶点，而不是边。如果一个图存在一个能访问每个顶点恰好一次的环，那么该图就是哈密顿图。
记忆小撇步： Eulerian = Edges（边）。Hamiltonian = Homes（顶点/家）。
你知道吗？
欧拉问题起源于“柯尼斯堡七桥问题”，当时人们试图在不重复经过同一座桥的情况下走遍七座桥。莱昂哈德·欧拉正是利用上述这些度数规则，证明了这是不可能的任务！
5. 平面性与欧拉公式
平面图（Planar Graph）是指可以被画出来且没有任何边互相交叉的图。即使看起来很乱，只要你能重新安排点的位置让线不交叉，它就是平面图。
欧拉公式
对于任何连通平面图，顶点数（\(V\)）、边数（\(E\)）和面数（\(F\)）之间存在一个神奇的关系：
\(V + F - E = 2\)
注意： 面是指由边围成的封闭区域，加上包围整个图的无限大外部区域（“外部”面）。
库拉托夫斯基定理（Kuratowski’s Theorem）
我们如何确定一个图无法在不交叉的情况下画出呢？库拉托夫斯基发现了两个特定的图是“非平面”的：
1. \(K_5\)（有 5 个顶点的完全图）。
2. \(K_{3,3}\)（一个二分图，两个集合各 3 个顶点，每个顶点都与另一方的所有顶点相连）。
库拉托夫斯基定理指出，如果一个图包含 \(K_5\) 或 \(K_{3,3}\) 的细分，则该图就是非平面的。
6. 同构（Isomorphism）
如果两个图实际上是同一个图，只是画法不同，我们称它们为同构图。它们拥有相同数量的顶点，以相同的方式连接，且每个顶点的度数都相同。
如何检查两个图是否“不同构”：
如果你被要求证明两个图不相同，请寻找“不匹配”之处：
- 它们的顶点数或边数是否不同？
- 它们的度数序列是否不同？（例如：一个图有度数为 4 的顶点，另一个则没有）。
- 其中一个是否有长度为 3 的环（三角形），而另一个没有？
鼓励一下：
寻找同构就像是在玩“找不同”游戏。保持耐心，逐个顶点核对连接情况，你一定没问题的！
摘要清单
- 我能定义度数、迹和环这些基本术语吗？
- 我知道欧拉图意味着所有顶点的度数都必须是偶数吗？
- 我会对平面图使用 \(V + F - E = 2\) 吗？
- 我认得 \(K_5\) 和 \(K_{3,3}\) 是“被禁止”的非平面图吗？
- 我能解释为什么树没有环吗？