|
序言 本文总结来说就是，研究有权图中最短轨之间形成的代数结构，并尝试用更抽象的群论，启发最短路径问题的新思路。但由于学习程度和自身能力的不足并没有彻底解决这个问题，尤其是货郎问题，连判断图是否是* 图或者半图都困难重重。。。顺带提醒一下，熟悉图论和群论的小伙伴，括号里的内容可以不用看，专业大佬可以直接略过带*号标记的章节。 0.引言* （不同于现实世界中的列车或者行星轨道，即使二者有所共性，甚至后者由前者阐发抽象而来，）轨（ * ）在数学中专指一个点通过某种变换规则，所能得到的所有结果。轨通常定义为某个集合的子集，如果子集中的所有元素，都能由该集中的某个元素通过某个群的作用后得到。（在动力系统中，轨也用来描述某个点随时间演化所经过的所有路径或者状态序列。）本文中，轨则指图中以顶为起讫点的连续的顶边交错序列，这里的连续指的是在序列中相邻的元素在图中也相邻。轨有三种类型，其中不允许存在重复顶的为路（ * ），允许重复顶但不允许重复边的为迹（ * ），都允许的为途（ * ）。（可以分别直观理解成，需要掉头的旅途，笔画交叉的字迹，不能重复的心路。）接下来定义本文的核心概念最短轨半群。 1.代数结构* 1.1.半群* 在集合中定义一个二元运算，若运算封闭（运算结果还在集合内）且满足结合律，则该集合和该运算就构成一个半群。 1.2.幂等元* 半群中的元素是幂等元，当且仅当，该元素和其本身的运算结果是其本身。 1.3.逆半群* 其中每个元素都有半逆元的半群称作逆半群。逆半群中的元素 * 的半逆元 * 是指，在该逆半群中，满足 * 的元素（这里的 * 泛指所有二元运算）。该关系具有自反性（自反性是指每个元素都与自身相关），因此有 * ，即 * 。特别的，幂等元就是其本身的逆元。 1.4.半格* 半格是完全由幂等元构成的，满足交换律的逆半群。 1.5.幺半群* 有幺元的半群称为幺半群。幺元是指，在群中，和群中任一元素的运算结果，都为该元素本身的元素。幺元也有自反性，幺元和幺元的运算结果也是其本身。 2.最短轨 2.1.最短轨问题* 最短，指的是，在有权图中，一定限制条件下，使得轨上所有元素的权之和最小。注意，必须将路、迹、途，三种轨分别讨论，因为在3种轨下，最短的意义不尽相同。由于可以将顶权，以完全图的边权代替（把顶 * 用完全图 * 替换，并保留原有的每一边，各自连到 * 的每一顶上，一一对应，最后给这些改过的边都赋上顶的权），所以问题只用讨论边权，所有顶权都设为0。下面定义最短轨，研究最短轨的共性。 2.2.最短轨定义 在图 * 中，定义 * 为图中所有顶组成的集合，继续定义： 起讫顶（即出发顶点及到达顶点）分别为 * 和 * 的最短轨称为从 * 到 * 的最短轨（允许 * ），记为 * ； 经过 *的子集 * 里所有顶的最短轨称为遍历 * 的最短轨，记作 * ； 起讫顶分别为 * 和 * 且经过 * （ * 且 * ）中所有顶的最短轨称为从 * 到 * 的且遍历 * 的最短轨，记成 * 。 3.最短轨半群 3.1.起讫半群 定义 * 为起讫符，满足 * 。 为保证运算封闭性，下面仅讨论图中任两顶都可达的双向图或者无向图（若图中存在从顶 * 到顶 * 的轨，则从 * 到 * 可达）。 集合{ * 且 * }和起讫符 * 构成一个逆半群，记为({ * }, * )。 这是一个完全由幂等元构成的逆半群，其中任意两个元素都是彼此的逆元，命名为起讫半群。 3.2.遍历半格 定义 * 为遍历符，其中 * 。 ({ * }, * )也是一个完全由幂等元构成的带幺半格（存在幺元的半格），其中每个元素都是自身唯一的逆元，命名为遍历半格。 3.3.起遍讫半群 定义 * 为起遍讫符，则有 * （这里的 * 和 * 分别表示往集合中添加元素，或者从集合里删去元素，如果有的话）。 ({ * 且 * 且 * }, * )还是一个完全由幂等元构成的逆半群，其中每个元素都是自身唯一的逆元，命名为起遍讫半群。 4.半群的作用 4.1.特殊半群 显然最短途的子途也是最短途，但是对于有负权的图来说最短途没有意义（若图中存在权为负的边，则所有最短途都会无数次经过负权边以达到最短的 * ，同时所有无数次经过负权边的途都是最短途，那么这个问题在数值和结构上都失去了研究的价值），而在非负权图中，三种最短轨将完全等价（权非负，重复顶和边不会使轨更短，甚至可能会使轨更长）。值得注意的是，在无向图中，最短轨的逆轨也是最短轨（双向图中不一定，因为边权及其逆边的权不一定相等）。还有许多特殊情况下的性质，将这些性质表达在半群上，就得到了特殊半群，特殊半群相对来容易研究一些。 4.2.半群作用下的幂图集 把某个最短轨半群作用于图的幂图集（图的所有子图所构成的集合），即是将该半群中，和幂图集中的某个元素中的所有顶有关的轨，按照原来的关联关系组合成子图，作为该元素在该半群作用下的轨，特称为轨图，自然地可以定义路图、迹图和途图。 在起讫半群作用下，平凡子图（一个顶组成的子图）的轨图对应着单源最短轨问题，特别的，路图为树；2阶子图（图的阶数为图中元素的个数）的轨图对应着任两顶间的最短轨问题，特别的，非负权图下的2阶子图的轨图的子图，也是另一个2阶子图的轨图；3阶子图的轨图和遍历半格作用下的轨图同构，不做赘述；至于其他阶的子图的轨图，则对应随机起讫点下的最短轨问题，也是研究遍历半格作用下的轨图的基础，进一步则需要组合数学和计算数学的加入。 在遍历半格作用下，平凡子图的轨图是所有经过该顶的最短轨，可以反应该顶的重要程度；2阶子图的轨图和起讫半群作用下的轨图同构，不再多言；3阶以上的轨图对应着货郎问题及其衍生问题。 起遍讫半群则是连接上述两个半群的桥梁，但必须从3阶子图开始，既涉及到了起讫半群的最短路径问题，也涉及到了遍历半群的货郎问题。 可以看出，三个半群部分等价，关系密切，如果研究三个半群之间的相互作用，可能会有更多收获。 为了方便研究三个半群之间的相互作用，可以统一记号为 * ，当 * 时 * ，当{ * } * 时 * ，当 * 且 * 且 * 时 * （这里不用刻意衍生概念，比如当 * 且 * 且 * 时，因为其是可以用群中其他已有元素表示的） 。 4.3.一个启发算法 * 算法和 * 算法虽然高效，但针对的都是单源问题，而 * 算法虽然是全局计算，但效率较低，于是我想到一个不知道对不对的算法（只适用于非负权图）。 （1）所有顶同时正反进行 * 算法（每个顶可以从起顶推起，也可以从讫顶倒推），直至所有已推的最短路径形成一个有向连通图，并将得到的所有最短路径更新到最短路径矩阵中； （2）若顶 * 到顶 * 在该连通图中可达，且最短路径矩阵中没有其信息，则对比连通图中所有可能的路径，其中最短的就是从到的最短路径，将其及其子路径更新到连通图和最短路径矩阵中（感觉是对的，暂时不知道怎么证明）； （3）重复（2），直到最短路径矩阵包含了所有最短路径的信息（不知道程序会不会中断，也不会证明）。 谢谢你看到这里~ By Michael Liou，loves Yanqi，thanks dad and mom. （这里编辑不了公式，详情请见链接） |
|
|
