论文标题
图形，路径和旅行销售人员问题的固有对称性
Inherent Symmetries of graphs, paths, and Traveling Salesperson Problems
论文作者
论文摘要
如果不对加权图的弧形长度施加限制，则不能预期对称结构。但是，它们存在。为了找到它们，将图分解为一个组件，该组件决定了所有封闭的路径属性（例如，最短和最长的路径），以及可以去除的多余组件。剩余的剩余图揭示了构成所有封闭路径属性的基础的固有对称结构。对于某些不对称问题，对称性是三循环的对称性。对于一般的无向设置，它是一种四循环的类型；对于不对称成本的一般定向问题，它是三个和四个周期的产物。一切都立即扩展到不完整的图。
Without imposing restrictions on a weighted graph's arc lengths, symmetry structures cannot be expected. But, they exist. To find them, the graphs are decomposed into a component that dictates all closed path properties (e.g., shortest and longest paths), and a superfluous component that can be removed. The simpler remaining graph exposes inherent symmetry structures that form the basis for all closed path properties. For certain asymmetric problems, the symmetry is that of three-cycles; for the general undirected setting it is a type of four-cycles; for general directed problems with asymmetric costs, it is a product of three and four cycles. Everything extends immediately to incomplete graphs.
