欢迎来到图论的世界！
在你大部分的数学课中，“图形”（Graphs）通常指 \(y = x^2\) 或直线。但在离散数学中，图形更像是地图或社交网络，它们仅仅是由“点”通过“线”连接而成的集合。
读完这些笔记后，你将能像专家一样描述这些图表，理解如何穿梭其中，甚至解决困扰数学家数百年的难题！如果一开始接触到很多新词汇，请别担心——我们会循序渐进地学习。
1. 图的构造
在开始任何高深的运算前，我们必须先认识各部分的名称。可以把一个图想象成城市与连接城市的道路集合。
关键词汇（课程大纲 DA1 及 DA6）
顶点 (Vertex，复数：Vertices)： 即“点”。在现实世界的例子中，这些点可以是社交网络中的用户，或是地铁路线中的车站。
边 (Edge)： 连接顶点的“线”。它们代表两点之间的关系或路径。
度 (Degree 或 Valency)： 连接到特定顶点的边数。贴士：如果顶点上有环（Loop），该环在计算度数时计作 2！
环 (Loop)： 起点和终点都在同一个顶点的边。
多重边 (Multiple Edges)： 连接相同两个顶点的多于一条边。
简单图 (Simple Graph)： 一个没有环且没有多重边的图。这是图最“纯净”的形式。
构建图形
子图 (Subgraph)： 大型图的一部分。想象一下拿着英国地图，但只关注伦敦市内的道路——这就是一个子图。
细分 (Subdivision)： 当你对一条边进行“放大”，并在其中间放置一个新顶点，从而将一条边变为两条时，这就称为细分。
连通图 (Connected Graph)： 在这个图中，你可以通过边从任何顶点到达其他任何顶点。它不一定是直接路径，但不能有任何“孤岛”。
重点速览：
- 顶点 (Vertices) = 点
- 边 (Edges) = 线
- 度 (Degree) = 在一个点上汇集的线条数量
- 简单图 (Simple) = 没有环或双重线
2. 穿梭图中：轨迹与回路
现在我们有了“地图”，该如何移动呢？（课程大纲 DA1）
轨迹 (Trail)： 一系列边的序列，其中没有边被重复使用。你可以重复访问同一个顶点，但不能两次走过同一座桥！
回路 (Cycle)： 一个闭合的轨迹。这意味着你从同一个顶点出发，最后回到该顶点，过程中没有重复使用任何边。
类比：将“轨迹”想象成在公园散步，你想走遍所有路径，但绝不走回头路。而“回路”就像是在赛车场跑了一圈。
3. 欧拉图与哈密顿图
接下来我们要探讨图的一些特殊性质。这些性质以两位著名的数学家 Leonhard Euler（欧拉）和 William Rowan Hamilton（哈密顿）命名。（课程大纲 DA2）
欧拉图 (Eulerian Graphs)
欧拉图是指你能找到一条轨迹，恰好使用每一条边一次，并回到起点。
秘诀： 一个连通图是欧拉图的充要条件是，每一个顶点的度数都是偶数。
半欧拉图 (Semi-Eulerian)： 你可以使用每一条边一次，但起点和终点在不同位置。这发生在图中刚好有两个奇数度顶点时（这两个点分别是起点和终点）。
哈密顿图 (Hamiltonian Graphs)
哈密顿图关注的是顶点，而不是边。它是一个包含一个能恰好访问每个顶点一次（并回到起点）的回路的图。
记忆法：Eulerian = Edges（边）。Hamiltonian = Homes（顶点/家）。
核心重点：
- 欧拉图 (Eulerian)：“我不提起笔或重叠线条，能画完这个图吗？”
- 哈密顿图 (Hamiltonian)：“我能每个城市只去一次并回到家吗？”
4. 特殊类型的图
有些图拥有特定的结构，使它们在模拟不同情况时非常有用。（课程大纲 DA5 及 DA6）
完备图 (\(K_n\))
在完备图中，每个顶点都与其他所有顶点通过一条边相连。我们用 \(K_n\) 表示，其中 \(n\) 是顶点的数量。
例子：在 \(K_4\) 中，有 4 个顶点，每个顶点的度数均为 3。
二分图 (Bipartite Graphs)
在二分图中，顶点被分成两个独立的集合（我们称为集合 A 和集合 B）。边只存在于两个集合之间，而永远不会存在于集合内部。
现实例子：一个展示“学生”与“课程”的图。边连接学生和他所选修的课程。学生与学生之间不会相连，课程与课程之间也不会相连。
树 (Trees)
树是一种非常简单的连通图，且没有回路。
你知道吗？ 一个有 \(n\) 个顶点的树，必定刚好有 \(n - 1\) 条边。如果你多加任何一条边，就会产生一个回路！
5. 邻接矩阵与补图
有时候，手绘图表会显得很混乱，这时我们可以使用表格（矩阵）来代替。（课程大纲 DA5）
邻接矩阵 (Adjacency Matrix)： 一个网格，行和列分别代表顶点。格内的数字告诉你那两个顶点之间连接了多少条边。
补图 (Complement of a Graph)： 想象一个图 \(G\)。补图（记作 \(G'\)）是一个拥有相同顶点，但包含所有在原图中不存在的边的图。
类比：如果 \(G\) 代表“互为朋友的人”，那么补图 \(G'\) 就代表“互为陌生人的人”。
6. 平面图与欧拉公式
你能画出一个没有边交叉的图吗？（课程大纲 DA3）
平面图 (Planar Graph)： 一个可以被画成没有边交叉的图。即使目前绘制的方式有交叉，只要你能通过调整将其“理顺”，它就是平面图。
欧拉公式 (Euler’s Formula)
对于任何连通平面图，顶点数 (\(V\))、边数 (\(E\)) 和面数 (\(F\)) 之间存在一个神奇的关系：
\(V + F = E + 2\)
什么是“面”？
面是由边所围成的区域。
常见错误： 永远记得要把图形外面那个“无限大”的区域也算作一个面！如果你画一个正方形，它共有 2 个面：正方形内部，以及它外面的广阔区域。
简单例子：
一个简单的三角形：
- \(V = 3\)
- \(E = 3\)
- \(F = 2\)（内部和外部）
验证：\(3 + 2 = 3 + 2\)。成立！
总结表：关键性质
树 (Tree)： 连通、无回路、\(E = V - 1\)。
完备图 (Complete - \(K_n\))： 每个顶点均与其他所有顶点相连。
平面图 (Planar)： 没有边需要交叉，遵循 \(V + F = E + 2\)。
欧拉图 (Eulerian)： 所有顶点的度数均为偶数。
二分图 (Bipartite)： 顶点分为两组；连接仅存在于组与组之间。
如果一开始觉得困难，别担心！离散数学的核心在于视觉化这些连接。试着亲自画出这些不同类型的图——这是让定义深入脑海最好的方法！