第一节 图论的基本概念

  在前面的学习中,我们简单地接触到了树、图等图论知识的基础概念,在这一章中,我们将对图论做系统的研究。图论相关的知识是ACM中比较重要的一部分,在日常的软件设计中,也较为常用。

图论的历史

  图论是一门应用十分广泛、内容非常丰富的数学学科,也是近几十年来较为活跃的数学分支之一。它的起源很早,瑞士数学家欧拉在1736年解决了当时颇为有名的一个数学问题,即哥尼斯堡七桥问题,从而使他成为了图论的创始人。

  七桥问题呢,就是在一个城市的中间,有一条河,河中有两个小岛。在两岸和小岛之间呢,有七座桥。我们需要找到一个路径,使得我们从这四块陆地的其中一个开始,通过每一座桥,并恰好回到起点。

  欧拉为了解决七桥问题,将这个问题转化为了一个数学问题。他认为这种走法是否存在,与岛的形状、大小、以及桥的长短等因素都没有关系,重要的是陆地之间是否有桥联通。因此他用点表示陆地,线表示陆地间的桥梁,就得出了七桥问题的示意图。欧拉在1736年证明了这个路径是不存在的,并进行了进一步的推广得出了一个判别法则—,用于判别给定一个图是否可以走遍。

  除此之外,我们在高中曾经学习过基尔霍夫电压定律。基尔霍夫在1847年运用图论解决了电路理论中求解联立方程组问题,并引入了“树”的概念,可惜在当时并没有受到重视。1857年,凯莱在研究饱和碳氢化合物时,发现了一族重要的图,称其为树,并利用树来计算其同分异构体的数目。

  20世纪后,图论的应用渗透到了其他的很多领域,在计算机网络、博弈论等方面起到了重要的作用。它是组合数学的一个分支,和数值分析、拓扑学等有着密切的联系。比如对于基础的图论来说,它不需要有高深复杂的数学工具,只需要一些集合、二元关系与线性代数知识,结合一般的逻辑推理来解决问题。

图论简介

  这里我们讨论的图论并不是几何学上的图形,而是客观世界中,某些具体事物间相互联系的一个数学抽象。用点来表示事物,用边来表示关系。这种由定点及连接这些点的所有边组成的就是我们图论中的图。其中的点我们称为顶点,线称之为边。当边具有方向性时,图是有向图。(否则为无向图)

  图在研究现实问题时会经常使用到,比如在地图上找到一条能够最快到达目的地的线路。这都是我们今后将要学习的内容。

  从一个顶点出发,如果存在一个路径,能够回到该顶点,我们称之为圈。没有圈的连通图称为树,树是特殊的图。在解决问题时,我们有时候需要将图转化为它的“生成树”再对问题进行处理。