图论是什么？研究点和连线关系的数学分支

图论（Graph Theory）是数学的一个分支，研究的对象是“图”。这里的图不是指图片，而是一种由若干个“顶点”（也叫节点）和连接这些顶点的“边”组成的结构，用来描述事物之间的关系。比如城市和城市之间的道路、人和人之间的朋友关系、网页和网页之间的链接，都可以用图来表示。

起源：哥尼斯堡七桥问题

图论通常被认为起源于 1736 年瑞士数学家莱昂哈德·欧拉对“哥尼斯堡七桥问题”的研究。当时的普鲁士城市哥尼斯堡（今俄罗斯加里宁格勒）有一条河穿城而过，河中有两座小岛，七座桥把两岸和小岛连接起来。当地人想知道：能否从某个地方出发，每座桥恰好走一次，最后回到出发点？欧拉把陆地抽象成点，把桥抽象成连接点的线，证明了这样的路线是不存在的。他发现，要想一笔画完所有的边并回到起点，图中每个顶点连接的边的数量都必须是偶数，而七桥问题中的四块陆地连接的桥数都是奇数。这一抽象的思路开创了图论。

基本概念

有向图和无向图：如果边有方向，比如单行道、微博上的“关注”关系（我关注你，你不一定关注我），就是有向图；如果边没有方向，比如双向的道路、微信上的好友关系，就是无向图。带权图：边上带有数值，比如道路的长度、通行的时间、网络连接的带宽。度：一个顶点连接的边的数量，比如在社交网络中，一个人的“度”就是他的朋友数量。路径和连通性：从一个顶点沿着边走到另一个顶点所经过的路线叫路径；如果任意两个顶点之间都有路径相连，这个图就是连通的。树：一种特殊的图，任意两个顶点之间有且只有一条路径，没有回路，家谱、公司的组织结构图、文件夹的目录结构都是树。

经典的问题

最短路径问题：在一个带权图中，找出两个顶点之间总长度最短的路径。荷兰计算机科学家迪杰斯特拉在 1956 年提出的算法是解决这个问题的经典方法，手机地图的导航就基于这类算法。旅行商问题：一个推销员要访问多个城市，每个城市只去一次，最后回到出发地，怎样走总路程最短？这是一个著名的难题，当城市数量很多时，目前还没有找到高效的精确解法。图着色问题：用最少的颜色给图的顶点着色，使相邻的顶点颜色不同。著名的“四色定理”指出，任何一张平面地图，都只需要四种颜色就能让相邻的区域颜色不同，它在 1976 年借助计算机得到证明，是第一个主要依靠计算机证明的重要数学定理。此外还有最小生成树、最大流、匹配等问题。

图论的应用

图论的应用非常广泛：地图导航和物流配送的路线规划；社交网络分析，比如推荐“你可能认识的人”、发现社群、识别有影响力的用户；谷歌的 PageRank 算法把整个互联网看作一张巨大的有向图，根据网页之间的链接关系来评估网页的重要性；通信网络和电网的设计；化学中用图来表示分子的结构；以及知识图谱，用图来表示实体和实体之间的关系，比如“北京”是“中国”的首都。

图论与人工智能

在人工智能中，很多数据天然就是图的形式，比如社交网络、分子结构、交通网络、知识图谱。图神经网络（GNN）是专门处理图结构数据的深度学习方法，它让每个节点不断地从相邻的节点那里汇集信息，学习到节点和整个图的表示，被用于推荐系统、药物发现、交通流量预测、欺诈检测等领域。此外，神经网络本身的计算过程也可以表示为一张计算图，深度学习框架就是基于计算图来自动计算梯度的；在检索增强生成中，GraphRAG 等方法也利用知识图谱来帮助大模型更好地组织和检索信息。