一、图论的起源与发展

图论作为应用数学的重要分支，起源于1736年欧拉对柯尼斯堡七桥问题的解决。欧拉将城市区域抽象为顶点，桥梁抽象为边，证明了无法不重复走完七座桥，由此开创了图论研究。1859年，汉密尔顿提出的“绕行世界”游戏，推动了汉密尔顿回路问题的研究；1852年诞生的四色猜想，历经百年，最终在1976年由阿佩尔和哈肯借助计算机完成证明，成为图论发展的重要里程碑。20世纪中后期，随着计算机科学、运筹学等领域的兴起，图论不断拓展出拟阵理论、超图理论、代数图论等分支，应用范围也愈发广泛。

二、图的基础概念

1. 图的定义：图G是由顶点集V和边集E组成的二元组（V, E），其中E是V中元素的二元子集，用于表示顶点间的连接关系。顶点是图的基本元素，边则是连接顶点的纽带。

2. 图的分类

• 按边的方向：分为有向图（边有方向，从一个顶点指向另一个顶点）和无向图（边无方向，连接的两个顶点地位平等）。

• 按边的权重：分为带权图（边带有表示成本、距离等的权重）和无权图（边仅表示连接关系）。

• 按连通性：连通图中任意两个顶点都可通过路径相连，无向图中称为连通无向图，有向图中若任意顶点间都有双向路径则为强连通图；非连通图存在无法相互到达的顶点子集。

• 其他类型：还包括简单图（无自环和重复边）、多重图（允许重复边）、自环图（允许顶点到自身的边）、有向无环图（DAG，无循环路径）、二分图（顶点可分为两个独立集合，边仅连接不同集合顶点）等。

3. 核心术语

• 路径：由顶点序列组成，相邻顶点间通过边连接。

• 环：起点和终点为同一顶点的路径。

• 度数：无向图中顶点的度数是相连边的数量（自环算两次）；有向图中分为入度（以该顶点为终点的边数）和出度（以该顶点为起点的边数）。

• 生成树：包含图中所有顶点且无环的子图，是连通图的极小连通子图。

三、重要定理与算法

1. 握手定理：无向图中所有顶点的度数之和等于边数的两倍，由此可推导出度数为奇数的顶点必有偶数个；有向图中所有顶点的入度之和等于出度之和。

2. 度数序列可图化判定

• Havel - Hakimi算法：通过将度数序列降序排列，依次将最大度数顶点与后续顶点相连并更新度数，若最终能归约到全零序列，则该序列可简单图化。

• Erdős–Gallai定理：度数之和为偶数，且对于任意1≤r≤n−1，前r个顶点的度数之和不超过r(r−1)加上剩余顶点中每个顶点与r的较小值之和，满足此条件的序列可简单图化。

3. 平面图相关定理

• 若连通平面图G的每个面的度数≥l（l≥3），则边数m满足m ≤ l/(l - 2)×(n - 2)，反之若m > l/(l - 2)×(n - 2)，则G为非可平面图，如完全二分图K3,3，因l=4时，9 > 4/(4 - 2)×(6 - 2)=8，故为非可平面图。

• 若连通平面图G的每个圈长度为l，则m(l - 2)=l(n - 2)。

• 简单平面图的最小度数δ≤5。

4. 经典算法

• 最短路径算法：迪杰斯特拉算法用于求解带权图中从单个源点到其他顶点的最短路径，适用于边权非负的情况；贝尔曼 - 福特算法可处理存在负权边的图，还能检测负权环。

• 最小生成树算法：克鲁斯卡尔算法通过按边权从小到大排序，依次添加不形成环的边；普里姆算法从任意顶点出发，逐步添加与当前生成树相连的最小权边，最终得到包含所有顶点且边权和最小的生成树。

四、图论的应用领域

图论为复杂关系网络提供了强大的建模工具，在多个领域广泛应用：

• 计算机科学：用于网络拓扑设计、数据结构构建、编译器优化等，如通过图表示程序的控制流进行优化。

• 网络设计：帮助优化通信网络、交通网络的布局，减少传输成本和延迟。

• 社交网络分析：通过图建模用户关系，实现好友推荐、影响力分析等功能。

• 运筹学：解决物流配送路径规划、任务调度等优化问题。

• 生物信息学：用于基因调控网络分析、蛋白质相互作用研究等，揭示生物分子间的复杂关系。