什么是图？

“大家可能会说：‘图’是什么还用介绍吗？迷宫的平面图不就是一个‘图’吗？《三毛流浪记》一整本漫画不也都是‘图’吗？错了，我们这里所说的‘图’指数学的一个分支——‘图论’中的专有名词。它跟迷宫的平面图、函数的图象和图画的图是不同的。让我们先看一些例子。

【例 1】假设有 5 个人，分别记作 A、B、C、D 和 E。在这 5 个人中，设A、B 两人互相认识；

B、C 两人互相认识； A、C 两人互相认识； B、D 两人互相认识； C、E 两人互相认识。

“我们可以用一个几何图形表示上面提到的 5 个人以及他们的‘认识’ 关系：每一个人用一个小圆圈表示；如果有两个人互相认识，就把表示这两个人的小圆圈用一条线段连起来，那么这 5 个人和他们之间的相互认识关系

就可以表示成图 4-1 了。

{ewc MVIMAGE,MVIMAGE, !16000290_0023_1.bmp}图 4-1

“如图 4-1 所画的图形就叫做一个‘图’。组成‘图’的小圆圈 A、B、C、D、E 叫做图的顶点。联结顶点的那些线段叫做图的边。如果 AB 是图的一条边，我们说顶点 A 和顶点 B 相邻，边 AB 与顶点 A 和 B 关联，顶点 A 和 B 是边 AB 的端点。

“从上面的例子中我们看到，在理解‘图’这个概念的时候，应当注意： 1.图的顶点的位置可以随便画。

  1. 图的边可以画成直线段，也可以画成曲线段，并且画长画短都没有关系。关键的是，一个图中有几个顶点（有几个人），哪些顶点间有边相连（哪些人互相认识）。

  2. 图的两条边可能在非顶点的地方相交，这时候它们的交点不是图的顶点。如图 4-1 中，顶点只有 5 个，应该把边 BD 想象为跨过边 AC 和 CE。所以， 画一个‘图’的时候，顶点一定要用小圆圈表示，以免和两条边的不是顶点的交点相混淆。

{ewc MVIMAGE,MVIMAGE, !16000290_0024_1.bmp}

“这样，我们也可以把图 4-1 画成图 4-2，它同样表示例 1 中的 5 个人和他们之间的认识关系。

【例 2】设有一个表示篮球队循环赛的图，如图 4-3 所示，它的一个顶点表示一个篮球队。如果两个篮球队已经比赛过了，就在图 4-3 表示这两个

篮球队的顶点间连一条边。你们能不能说说看，图 4-3 中表示几个篮球队？

哪两个篮球队间已经进行过比赛？哪些篮球队间还没有进行过比赛？”

{ewc MVIMAGE,MVIMAGE, !16000290_0025_1.bmp}

同学们七嘴八舌地回答，刘老师都听见了，她说：“对的！图 4-3 中有

6 个篮球队 A、B、C、D、E、F。其中，A、B；A、C；A、F；B、C；B、E；B、F；C、D；C、E；D、E；E、F 间都比赛过。而 A、D；A、E；B、D；C、F；D、F 间还没有比赛过。

“下面再看一个例子：

【例 3】用一个顶点表示一个市（县），两个市（县）间如有直达公路相连，就把这两个顶图 4-4 点用一条线段连起来。那么图 4-4 所表示的交通图也是一个图。

“从上面三个例子看出，一个图就是由一些顶点和这些顶点之间的一些边组成的图形。我们以后所讨论的图中的顶点数和边数都是有限个的，这种图也叫做有限图。一个图的顶点可以表示一个人、一个球队或一个城市，当然也可以表示其他事物。而边呢？它可以表示顶点所表示的事物间的某种关系。例如用顶点表示城市，用边表示城市间有公路相通的关系等等。

“由于顶点可以表示很多东西，边可以表示这些东西间的一种关系，所以我们就可以把图的知识应用于研究多种事物和它们各自的关系。例如我们要研究的迷宫，现在就可以用图来表示了。

“在游迷宫问题中，我们关心的是可以从哪个岔路口（或碰壁的绝点） 走到哪个岔路口（或绝点）。因此，我们可以把迷宫中的每个岔路口和绝点用一个顶点来表示，如果两个岔路口（绝点）有一条通道相通，就在这两个顶点间连一条边。这样我们就能用一个图来表示一个迷宫了。下面我用一个简单的迷宫作例子来说明这种表示方法（图 4-5）。

“设有一个迷宫（图 4-5（a）），我们先把所有岔路口和绝点标上英文字母（图 4-5（b）），再把有通道的顶点用边连起来（图 4-5（c）），这样， 就得到迷宫的一个图（图 4-5（d）），把它画得更顺眼一些，就得到图 4-5

  1. 。

{ewc MVIMAGE,MVIMAGE, !16000290_0027_1.bmp}

“现在请你们不要看黑板，自己在笔记本上把图 1-1 和图 2-1 的迷宫用图表示出来。”

这时，大家都动起手来，刘老师也在黑板上画出图 1-1 和图 2-1 两个迷宫相应的“图”（图 4-6（a）和（b））。

同学们把两个迷宫的平面图用“图”表示后，发现像图 2-1 那样复杂的迷宫，用图来表示（图 4-6（b））竟是那样简单，感到十分惊讶。大家开始对图的作用有了一点体会。

{ewc MVIMAGE,MVIMAGE, !16000290_0028_1.bmp}图 4-6

刘老师接着说：“现在我们的游迷宫问题，就变成了诸如在图 4-6 所表示的图中，从顶点 A 出发，走遍图中每条边至少一次，再回到 A 应当怎么走的问题了。”