连续发表（之十五）

雷明85639720

连续发表（之十五）：《四色问题与欧拉公式》一书的第二章《图论的基本知识》中的第10节《图中的道路》（请打开以下DOS文件查看）。

  看了上面网页的文件后，第5小标题的文章中略有变动和增减，现奖修改后的第5小标题的文章全录在下面，作为修改和补充。

5、各种各样的道路
pn道路的边数e与顶点数v比例的不同，会产生下列不同的道路：
（1）当e＝v－1时，pn既是一条哈密顿道路（即一次性遍历图中各顶点的道路），又是一条欧拉道路（即一次性遍历图中各条边的道路），且都是一条初级道路（即道路中没有重复的顶点）；
（2）当e＝v时，有两种情况。① 一种情况是：道路的首尾相接，pn是一个初级圈（圈中无重复顶点），这时pn既是一条哈密顿回路，又是一条欧拉回路，且是一个初级回路（也即走完该回路不走重复的顶点）；② 又一种情况是：pn是一条只有一个重复顶点且只重复一次的道路，是一个具有起笔点和落笔点是不同的两个顶点的一笔画图形的欧拉道路。这种重复可能是道路中的一个端点顶点与道路中的其它一个顶点的重复，也可能是道路中除了两个端点顶点以外的其它两个顶点的重复的；
（3）当e＝v＋1时，pn是一条只有一个重复顶点且只重复一次的欧拉回路，是一个具有起笔点和落笔点是同一个顶点的一笔画图形的欧拉回路；
（4）当e＞v＋1时，也有两种情况。① 道路中只有两个顶点的度（顶点的度即顶点所相邻的边数，关于顶点的度请见后面第16节《顶点度与正则图》一节中的“顶点度”部分）是奇数时，pn是一条有交叉顶点的欧拉道路，即是起笔点和终笔点是不同的两个点的一笔画图形，这时起笔点和终笔点分别就是度为奇数的那两个顶点；② 道路中所有顶点的度全是偶数时，pn也只是一条非初级的欧拉回路，但这是起笔点和终笔点是同一个顶点的一笔画图形，图中的所有顶点都是这样的顶点。
以上的（1）和（2）中的①的情况是走完pn后，各顶点和各边均经过一次且仅一次，既是遍历Pn中各顶点的旅行路线（巡回售货）问题中的哈密顿道路和哈密顿回路，也是遍历pn中各边的投递路线（中国邮路）问题中的欧拉道路和欧拉回路；而（2）中的②以及（3）和（4）的情况则是走完pn后，各边经过一次且仅一次，但各顶点可能通过不至一次的遍历pn中各边的道路，也即投递路线（中国由路）问题中的欧拉道路和欧拉回路。
以上的讨论，我们没有考虑道路中带有环或平行边和情况（有关环和平行边请见后面的第12节《单纯图与多重图》一节中的“环”和“平行边”部分），如果有了这种情况，则更复杂一些。有了“环”，道路一定只是欧拉道路（或回路），因为要经过环边必须从一个顶点出发绕环一圈还要回到该顶点来，而哈密顿道路（或回路）是不能走重复顶点的；有了“平行边”，则是当相于有了重复边的欧拉道路（或回路）（求一个图的中国邮路的解时是允许走重复边的）。