1.  路
    ==

在图 4-9 所示的图中，如果我们从 A 出发，沿边 e1 走到 B，再从 B 沿边e9 走到 E，从 E 又沿 e4 走到 D。我们就说这是一条从 A 到 D 的路（图 4-10）， 记作

P＝Ae1Be9Ee4D。

在一个简单图中，路也可以只用顶点来记。图 4-9 是简单图，所以刚才这条路可记为

P＝ABED。

{ewc MVIMAGE,MVIMAGE, !16000290_0031_1.bmp}图 4-9 图 4-10

实际上，这里“路”的概念跟我们平常走路的路的概念是很类似的。 在一条路中，顶点和边都允许重复经过。例如下述的 p1 和 p2 都是图 4-9

所表示的图中的路：

P1＝Ae1Be8Fe5Ee9Be2C

这条路经过顶点 B 两次，即在路 p1 中顶点 B 出现两次。

p2＝Ge11Ae1Be8Fe6Ae1Be2C。

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

这条路经过顶点 A、B 各两次，也经过边 e1 两次（见图 4-11（a）和图4-11（b））。

回路

如果一条路的起点和终点重合，这条路就叫做一条回路。下面写出的 p1、p2、p3 都是图 4-9 中所示的图的回路。为了容易看清楚，我们分别再画在图4-12 中。

p1＝Ae6Fe8Be1A（图 4-12（a））；

P2＝Ae7Ce3De4Ee10Ce2Be1A（图 4-12（b））； P3＝Ae6Fe8Be9Ee5Fe8Be1A（图 4-12（c））。5.连通图

设 A、B 是图中的两个顶点。如果在 A、B 间有一条路，我们称 A、B 两个顶点在这个图中是连通的。

如果一个图中任意两个顶点都是连通的，那么我们称这个图是连通图。换句话说，如果一个图是连通图，那么从图中随便一个顶点出发，都可

以经过某一条路走到任意的一个顶点去。

我们看到，图 4-6 中表示迷宫的两个图都是连通图。要是这两个图不是连通图，那么我们从 A 进去，就无法走遍迷宫的每条边，从而迷宫问题无解。所以今后在讨论迷宫问题时，我们总假设它的图是连通图。

如果表示一个迷宫的图中有回路，将表明游迷宫的人有可能一直绕着回路走而兜圈子。图 4-6 中的两个图都有回路，进入这两个迷宫的人，都有可能迷路。

刘老师介绍的这些图的名词，大家都感到很直观，很容易理解。刘老师接着说：“有了图的概念，你们去研究游迷宫问题就方便多了。现在我们假设怪物米诺陶就住在图 2-1 的迷宫的某处，请你们回去研究一下，提修斯带着一个线球能不能找到这个怪物并从迷宫入口出来？如果能找到，他该怎么走？下一次我们举行一次讨论会来讨论这个问题。要是你们有兴趣的话，可以做几个练习，用以加深对图这一新概念的理解。”说着，刘老师留下了几道练习题。

练习一

  1. 一中初三有 A、B、C 三个班；二中初三也有三个班 A′、B′、C′。两校初三年级联合举办一次篮球友谊赛，规定每校的一个班级代表队要和另一个学校的三个班级代表队各赛一次。如果友谊赛已结束，试用一个图表示这次友谊赛中，哪些队和哪些队进行过比赛。

  2. 下图中顶点 A、B、C 分别表示三个工人；A′、B′、C′、D′分别表示四项不同的工种。如果工人 A 能干工种 B′，则在 A、B′间连一条边，其余类推。试通过图指出，各工人能干一些什么工种？

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

  1. 下图中各顶点代表一种电器元件。如果 A、B 两元件间必需用导线接通，则在 A、B 间连一条边。试通过图指出这个电器系统有几个元件？哪些元件间必须用导线接通？

  2. 以上各题中，哪些图是连通图？哪些图不是连通图？

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

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

  1. 试把下列迷宫用图表示出来。

（2）

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