强乘积图的Euler性

On the Euler property of the strong product graphs

强乘积是一种通过若干规模较小的网络构造出规模较大的网络的方法,由此构造出来的大网络包含小网络作为它的子网络,并且保留了小网络一些好的性质,如连通性、可嵌入性等.强乘积图 G1 - G2 的拓扑结构由乘积因子图 G1 和 G2 的拓扑结构所决定.图的 Euler 迹问题是图论中一个重要的问题,在实践中也有着许多应用.本文通过因子图来研究强乘积图的 Euler 环游和 Euler 通路问题,得出并证明了两个图的强乘积存在 Euler 环游和 Euler 通路的充分必要条件.

Strong product is a method of constructing large-scale networks through some smaller networks. The large network constructed from this method contains small networks as its subnetworks, and retains many good properties of small networks, such as connectivity , embedability and so on. The topological structure of strong product graph is closely related to the topological structure of factor graph. The Euler problem of graphs is an important problem in graph theory , and has many applications in practice, such as the Chinese postman problem. In this paper, we study the Euler problem of strong product graphs, and obtain and prove the necessary and su cient conditions for the existence of Euler tours and Euler entries for the strong product of two graphs.