从七桥问题说起.pdf

从七桥问题说起 ——窥视数学的后花园 2008-6-5 sxgao@gucas.ac.cn 1 下列图形分别能几笔画成？ 2008-6-5 sxgao@gucas.ac.cn 2 下列图形分别能几笔画成？ 2008-6-5 sxgao@gucas.ac.cn 3 七桥问题 时间：18世纪 地点：普鲁士的哥尼斯堡城（K?nigsberg）， 普雷格尔（Pregel）河 人物：悠闲的市民们， 欧拉 问题：能否经过每座桥一次且仅一次回到出发点？ 2008-6-5 sxgao@gucas.ac.cn 4 Euler闭迹(closed trail, tour, circuit)：经过图G的 每条边恰好一次的闭迹。 Euler迹（trail）：经过每条边恰好一次的迹。 Euler图：有Euler闭迹的图。 图中顶点的度：顶点关联的边的条数。 2008-6-5 sxgao@gucas.ac.cn 5 定理1 一个非空连通图是Euler图当且仅当它没有奇度顶点。 证明 必要性：设图G是Euler图，C是G中一个Euler闭迹。对G中任 一个 顶点 v，v必在C上出现。因C每经过v一次，就有两条与v关联的边被使 用。设C经过v共k次，则C经过了2k条于v关联的边，故v的度为2k。 充分性：无妨设图Ｇ的顶点个数n 1。因G连通，故至少有一条边。下 面用反证法证明充分性结论。 假设图G无奇度顶点，但它不是Euler图。令 S = {G | G是至少有一条边的n阶连通图，无奇度顶点，且不是Euler图} 则S非空。取S中边数最少的一个，记为G0 。因G0无奇度顶点，故G0中 顶点的度至少为 2，因此G0含有圈，从而含有闭迹。设C是中一条最长 的闭迹。由假设，C不是G0的Euler闭迹。因此G0中将C的边去掉后必有 一个连通分支至少含有一条边。记这个连通分支为G1。由于C是闭迹， 故G1中没有奇度顶点，且G1 的边少于G0 的边。由G0的选择可知， G1必 有Euler闭迹，记为 C1。因此C＋C1是的一条闭迹，且它比C更长，这与 C的选取矛盾。证毕。 2008-6-5 sxgao@gucas.ac.cn 6 重返七桥 问题：能否经过每座桥一次且仅一次回到出发点？ 答案：不能 为什么？因右图中不存在欧拉闭迹，因此不能一笔画 完且回到出发点。 新问题：不要求回到出发点能否一笔画完？到底几笔 能画完？——好奇是创新的钥匙！ 2008-6-5 sxgao@gucas.ac.cn 7 定理2 一个连通图有Euler迹当且仅当它最多有两个奇度顶点。 证明 必要性：设连通图G有Euler迹T。若T是Euler闭迹，则G中无奇度 顶点。否则，设T的起点和终点分别为u, v。在G的基础上，给u, v间添 加一条边e（若G中有边uv，则e是重边），所得之图记为G*，则T+e是 G*的Euler闭迹。由定理1，图G*无奇度顶点。故G最多只可能有两个 奇度顶点。 充分性： 若G无奇度顶点，则由定理1，G有Euler闭迹，自然有Euler迹。 若G只有两个奇度顶点，设其为u,v，则在u,v间给G添加一条新边e，所 得之图G +e的每个顶点都是偶度顶点，由定理1，G +e有Euler闭迹， 因此G有Euler迹。证毕。 推论 一个连通图可k笔画成当且仅当它最多有2k个奇度顶点。 2008-6-5 sxgao@gucas.ac.cn 8 再返七桥 问题：七桥问题对应的图几笔能画完？ 2008-6-5 sxgao@g