图论 图论是组合数学的重要分支，以“图”（Graph）为研究对象。图由 顶点 （节点）和连接顶点的 边 构成，用于描述事物之间的关系。下面从基础概念逐步展开。 1. 图的基本定义 图 \( G = (V, E) \) 包含两个集合： \( V \)：顶点的集合（如 \( V = \{v_ 1, v_ 2, ..., v_ n\} \)）。 \( E \)：边的集合，每条边连接两个顶点（如 \( e = (u, v) \)）。 无向图 ：边没有方向，\( (u, v) \) 和 \( (v, u) \) 表示同一条边。 有向图 ：边有方向，\( (u, v) \) 表示从顶点 \( u \) 指向 \( v \)。 2. 图的分类与特性 （1）按边的基本性质分类 简单图 ：任意两个顶点之间最多有一条边，且无自环（边连接同一顶点）。 多重图 ：允许两个顶点之间存在多条边。 完全图 \( K_ n \)：任意两个顶点之间均有一条边，边数为 \( \frac{n(n-1)}{2} \)。 （2）按顶点度数分类 度 （无向图）：与顶点相连的边的数量。 正则图 ：所有顶点的度数相同（如每个顶点度数为 \( k \) 的图称为 \( k \)-正则图）。 （3）路径与连通性 路径 ：顶点序列 \( v_ 0, v_ 1, ..., v_ k \)，其中每条边 \( (v_ i, v_ {i+1}) \) 属于图。 连通图 ：任意两个顶点之间存在路径。 连通分量 ：极大连通子图（无法通过添加更多顶点和边保持连通）。 3. 特殊图结构 （1）树 定义 ：无环的连通图。 性质 ： 任意两个顶点之间有且仅有一条路径。 边数 = 顶点数 - 1（即 \( |E| = |V| - 1 \)）。 应用 ：用于建模层次结构（如家族树、算法中的决策树）。 （2）二分图 定义 ：顶点集可划分为两个不相交子集 \( U \) 和 \( V \)，每条边连接 \( U \) 和 \( V \) 中的顶点。 判定定理 ：图是二分图当且仅当不含奇数长度的环。 （3）平面图 定义 ：可画在平面上且边不交叉的图。 欧拉公式 ：对连通平面图，\( V - E + F = 2 \)（\( F \) 为面数）。 4. 图论的核心问题 （1）图的着色问题 顶点着色 ：用最少的颜色给顶点着色，使相邻顶点颜色不同。 四色定理 ：任何平面图可用最多四种颜色着色。 （2）路径问题 欧拉路径 ：经过每条边恰好一次的路径（存在条件：图中恰有 0 或 2 个奇度数顶点）。 哈密顿路径 ：经过每个顶点恰好一次的路径（判定是 NP 完全问题）。 （3）网络流 最大流最小割定理 ：网络中从源点到汇点的最大流量等于最小割的容量。 5. 应用场景 社交网络 ：顶点表示用户，边表示关系（如好友关系）。 交通规划 ：顶点为地点，边为路线，用于最短路径计算。 计算机科学 ：图用于建模数据结构（如状态机、依赖关系）。 图论通过抽象建模关系，成为解决离散问题的重要工具。后续可进一步学习 图的算法 （如 Dijkstra 算法、Kruskal 算法）或扩展至 超图 、 随机图 等高级主题。