中国地质大学(北京)《离散数学》期末考试拓展学(2)

奥鹏在线作业,奥鹏离线作业,奥鹏入学考试,奥鹏期末考试题库

由于在对地图着色过程中不考虑图的具体形状只考虑点是否相邻，将平面图的不相连点使其相连（这样增加着色难度），形成有许多三角形相连的平面图（三点以下肯定成立）。如图1：添加辅助线（不相邻的点使其相邻，这样就增加了着色的色数，有利于证明），将图1分解为４个△ABC。

在平面图中的无数点中，任取相邻三点构成各点相邻的△ABC（见图2），则需3种颜色A B C,在平面图中再任取一点 D 与 A B C 三点相邻,同时D又与A B C三点相连后形成三角形。任取一点E与 A、B、C、D四色相连，E必与四色之一色相同即E点在△ABD中与C色相同、在△ACD中与B色相同、在△BCD中与A色相同、在△ABC外与D色相同，E 与另外三色相连形成新的三角形。

在三角形的三点之外任取一点只有在三角形的内部和外部两种情况且这两种情况的点不会相邻，该点最多与三角形的三点相连且又形成新的三角形。

继续选取一点进行着色，该点同样最多与三角形的三点相连且又形成新的三角形，该点至少为四色中的一色。逐点（第n点）着色至将所有点（第n+1点）着色只须A、B、C、D四色其中一色。

图的着色方法：任意一张地图，将孤立的点用一种颜色着色（Ａ色），不能形成密闭图形的相连的点用两种颜色（Ａ、Ｂ色）。将剩余的点不相连的用虚线使其相连形成许多三角形，完全不相连的图不进行相连。任取相连三点着三种颜色（Ａ、Ｂ、Ｃ色），再取与其相连的点，如果与Ａ、Ｂ、Ｃ三色的点都相连着Ｄ色，否则着与其不相连的其中一色，用虚线相连的点可以用同一种颜色也可以用两种颜色，依次取与着色的点相连的点用以上方法进行着色。这样对所有的点进行着色最多用四色（Ａ、Ｂ、Ｃ、Ｄ色）。

图论的广泛应用，促进了它自身的发展。20世纪40-60年代，拟阵理论、超图理论、极图理论，以及代数图论、拓扑图论等都有很大的发展拓扑学的由来。几何拓扑学是十九世纪形成的一门数学分支，它属于几何学的范畴。有关拓扑学的一些内容早在十八世纪就出现了。那时候发现一些孤立的问题，后来在拓扑学的形成中占着重要的地位。

在数学上，关于哥尼斯堡七桥问题、多面体的欧拉定理、四色问题等都是拓扑学发展史的重要问题。哥尼斯堡（今俄罗斯加里宁格勒）是东普鲁士的首都，普莱格尔河横贯其中。十八世纪在这条河上建有七座桥，将河中间的两个岛和河岸联结起来。人们闲暇时经常在这上边散步，一天有人提出：能不能每座桥都只走一遍，最后又回到原来的位置。这个问题看起来很简单有很有趣的问题吸引了大家，很多人在尝试各种各样的走法，但谁也没有做到。看来要得到一个明确、理想的答案还不那么容易。

1736年，有人带着这个问题找到了当时的大数学家欧拉，欧拉经过一番思考，很快就用一种独特的方法给出了解答。欧拉把这个问题首先简化，他把两座小岛和河的两岸分别看作四个点，而把七座桥看作这四个点之间的连线。那么这个问题就简化成，能不能用一笔就把这个图形画出来。经过进一步的分析，欧拉得出结论——不可能每座桥都走一遍，最后回到原来的位置。并且给出了所有能够一笔画出来的图形所应具有的条件。这是拓扑学的“先声”。

在拓扑学的发展历史中，还有一个著名而且重要的关于多面体的定理也和欧拉有关。这个定理内容是：如果一个凸多面体的顶点数是v、棱数是e、面数是f，那么它们总有这样的关系：f+v-e=2。