Euler 图

                     

贡献者： 零穹

预备知识　链、路、圈、回

　　 [1] 在链、路、圈、回中我们已经介绍了 Euler 迹和 Euler 回，现在我们介绍 Euler 图的概念。Euler 图是为了纪念图论创始人 Euler 的，其是通过推广 Euler 解决 Konigsberg 七桥问题中抽象出的图的一类图。七桥问题大概是说：一个人可否从家出发经过所有的七座桥一次且仅一次并返回家。若把桥看成边，连接桥的两边陆地看成点，经过桥必须先经过桥两边的陆地，而要经过所有的桥，相当于要经过所有的点和所有的边，且仅经过一次然后最后返回家相当于：从某个代表家所在陆地的点出发，行走通过所有的边一次且经过所有的点最终回到起点。若按点边点排列，这相当于边不同的一个序列，即迹，并且端点相同，即还是回。这就是我们定义 Euler 迹和 Euler 回的历史渊源。Euler 图就是有 Euler 回的图。

定义 1　Euler 图

　　 设 $G$ 是个图，若 $G$ 有 $Eluer$ 回，则称 $G$ 是Euler 图。

定理 1　

　　 $G$ 是 Euler 图，等价于 $G$ 是连通的平衡图（定义 2 ）。

推论 1　

　　 $G$ 是 Euler 图，等价于 $G$ 不含奇度点。

推论 2　

　　 非平凡图有 Euler 迹，等价于 $G$ 连通且最多有两个奇度点。

[1] ^ 徐俊明.图论及应用. 中国科学技术大学出版社, 合肥.1998.

                     

© 保留一切权利