文集简介

这个文集是John Adrian Bondy的Graph Theory An Advanced Course一书的笔记，包括内容梳理与习题解答，当然也会加入一些笔者个人认为比较有趣的内容，但主体仍然大部分来自于本书。在之后可能会出现的其他文集中，笔者会介绍一些图论学科与其他学科交叉的内容或一些有意思的结论，包括为人津津乐道的“六度分隔理论”（小世界理论）等。

祝大家和笔者自己学习愉快！

图论的起源

图论是一门比较古老的数学分支，普遍认为图论起源于十分有名的哥尼斯堡(Konigsberg)七桥问题，哥尼斯堡位于如今的俄罗斯飞地加里宁格勒州，历史上它曾经属于普鲁士公国，闻名于世的七桥问题也诞生在这个时期。

问题的背景相当简单，是一个经典的“一笔画”问题：

这种一笔画问题在图论中被称作“连绘图”问题，当时有许多人对这个问题感到好奇并尝试将其解决但始终无果，这个问题最终被当时访问哥尼斯堡的大数学家欧拉(Euler)解决。1736年，欧拉向圣彼得堡科学院提交了论文《哥尼斯堡七桥》，在彻底解决了这个问题的同时开创了一个对后世产生了深远影响的数学学科——图论(Graph Theory)，这一学科对后来的数学研究乃至计算机科学的发展产生了巨大的作用。欧拉不愧是伟大的数学天才，和他同一个星座笔者感到十分荣幸。

那么话说回来，欧拉是怎么解决这个问题的呢？他将地图中的每一个地区抽象为一个点(node)，而将“两地之间有桥连接”这种事实抽象为两个点之间有边(edge)连接，那么原本的七桥问题就可以换一种表述方式：“是否能找到一条路径将每条边经过且仅经过一次，并回到出发点？”，这样的路径在之后的图论研究中被称作欧拉回路(Euler circuit)，关于欧拉回路的性质以及相关算法将在文集的后续笔记中介绍，欧拉通过七桥问题给出了一笔画问题（对无向图而言）有解的必要条件，即该图联通，且所有节点度数都是偶数。之后这个条件也被证明是一个无向图存在欧拉回路（或者说是该图的一笔画问题有解）的充要条件。

本文用word编写，故而书写公式及排版方面很不方便，因此这篇就只水这么一点内容，下篇笔记将开始介绍图论这一学科中经典的研究对象与概念，随机更新，但应该不会晚于5月15日，彼时篇幅也将加长。

图片来自网络，侵删。