图论研究点和线的关系。点是圆圈。线是连接圆圈的直线或曲线。点可以代表任何事物。线可以代表任何联系。城市是点。道路是线。人是点。认识关系是线。网页是点。超链接是线。这种抽象很简单。这种抽象很有力量。

许多问题可以画成点和线。我们寻找问题的答案。我们观察图的结构。图由顶点和边组成。顶点就是点。边就是线。两个顶点有边连接。我们说它们相邻。一条边连接两个顶点。这条边是这两个顶点的边。顶点可以有很多边。边只能有两个顶点。

我们研究路径。路径从起点顶点开始。路径走到相邻顶点。继续走到下一个相邻顶点。不能重复走边。最后到达终点顶点。路径的长度是边的数量。我们寻找最短路径。快递员送快递需要最短路径。手机地图导航寻找最短路径。网络数据包传输寻找最短路径。最短路径算法很著名。迪杰斯特拉算法是一个方法。这个算法像水流蔓延。从起点开始。水慢慢流向四周。最先到达终点的水流路径最短。计算机执行这个算法很快。

我们研究连通性。一个图可能分成几块。每一块内部顶点有路径相连。不同块的顶点没有路径相连。这样的一块叫连通分量。我们检查图是否连通。连通图只有一个连通分量。通信网络必须连通。所有用户才能互相通话。电力网络必须连通。所有家庭才能获得电力。如果几条边断开网络就分裂。这些边叫桥。我们找出所有桥。保护这些边非常重要。加强这些边的保护。网络就更可靠。

我们研究树。树是一种特殊的图。树是连通的。树没有环。环是一条起点终点相同的路径。树像一棵倒过来的树。有根在最上面。叶子在最下面。实际树枝可以交叉。图论中的树不能有环。树很简单。树很容易分析。许多网络用树结构。公司组织结构是一棵树。总经理是根。部门经理是下级。员工是叶子。文件系统是一棵树。文件夹是顶点。子文件夹是边。树没有环。操作不会循环。

我们研究环。环是闭合路径。环需要三条边以上。三角形是最小的环。环带来冗余。环提供备用路线。道路网络有环。一条路封闭。你可以走另一条路。环也带来复杂。消息在环中可能循环传送。网络协议要防止循环。我们检测图中是否有环。有环的图性质不同。无环的图就是森林。森林由多棵树组成。

我们研究图的着色。给每个顶点涂颜色。相邻顶点颜色不能相同。最少需要几种颜色。这个数量叫色数。地图着色是经典问题。每个国家是一个顶点。相邻国家用边连接。给地图着色。相邻国家颜色不同。四种颜色一定足够。这是四色定理。证明需要计算机帮助。课程安排也是着色问题。课程是顶点。时间冲突是边。安排考试时间。冲突课程不能同时考。颜色代表考试时间。我们需要最少的时间段。

我们研究匹配。匹配是边的集合。匹配中边没有公共顶点。工作分配是匹配问题。工人是一个顶点集合。工作是另一个顶点集合。每个工人能做一些工作。边表示工人能胜任工作。匹配就是分配方案。一个工人一份工作。一份工作一个工人。最大匹配让最多工人有工作。医院实习分配也是匹配。学生匹配到医院岗位。稳定匹配很重要。没有两个人愿意互换。盖尔-沙普利算法解决这个问题。这个算法用于毕业生求职。用于学校招生。用于器官捐献匹配。

我们研究网络流。图变成运输网络。边是管道。顶点是中转站。边有容量。容量是管道粗细。我们需要从源头运水到汇点。最大能运多少水。这是最大流问题。福特-富尔克森方法求解。不断寻找增广路径。增加流量直到饱和。这个算法用途广泛。交通流量分析。电路电流计算。数据流传输。都是网络流问题。

我们研究图的平面性。图能否画在平面上。边不能交叉。边只能顶点处相交。印刷电路板设计需要平面图。电线不能交叉。交叉会产生短路。我们测试图是否平面。库拉托夫斯基定理给出判断。某些小图不能出现在平面图中。如果图包含这些子图。它就不是平面图。这个定理很抽象。但判断方法很明确。

图论研究特殊图。完全图是所有顶点两两相连。社交网络中可能形成小完全图。一个小团体所有人互相认识。二分图顶点分成两组。所有边连接两组顶点。合作网络是二分图。演员是一组顶点。电影是另一组顶点。边表示演员出演电影。我们分析这样的网络。发现演员的合作关系。发现电影的类型关联。

图论算法需要效率。顶点可以很多。边可以更多。社交网络有几十亿顶点。普通算法太慢。我们设计快速算法。我们利用图的结构。稀疏图边很少。稠密图边很多。不同算法适合不同图。我们分析算法时间。我们比较算法好坏。计算机科学家不断改进算法。

图论研究不断深入。随机图是随机生成的图。我们研究随机图的性质。大多数随机图是连通的。大多数随机图直径很小。小世界现象由此解释。你认识一个人。他认识另一个人。只要几步就能认识任何人。六度分隔理论这样说。在线社交网络验证这个理论。平均距离只有四步或五步。

图论应用在互联网。搜索引擎用图论。网页排名算法基于图。网页是顶点。链接是边。重要网页有很多链接。更重要网页有重要网页链接。这个算法叫PageRank。它模拟随机上网的人。随机点击链接。最终停在某个网页的概率。概率越高网页越重要。这个想法非常巧妙。

图论应用在生物学。蛋白质相互作用网络用图表示。蛋白质是顶点。相互作用是边。我们寻找密集子图。密集子图可能是功能模块。我们寻找关键蛋白质。删除它网络就分裂。这个蛋白质可能是药物靶点。基因调控网络也是图。基因调控其他基因。理解这些网络理解生命。

图论应用在推荐系统。用户和商品构成二分图。用户购买商品形成边。我们分析图的结构。发现相似用户。发现相似商品。推荐你可能喜欢的商品。推荐系统改变购物方式。

图论是数学的分支。图论是计算机科学的基础。图论是理解世界的工具。世界充满联系。联系构成网络。网络形成图。我们画出图。我们分析图。我们解决问题。图论简单直接。图论强大有效。点和线。这就是图论。