凸性

研究文章ALL-PATH凸性：两个特征，一般位置编号和一个算法

摘要凸理论是数学的一个完善的（尽管不是主流）分支，在各种环境中的应用包括“连​​续”和离散的结构[14]。这种多功能性部分是因为在集合上的凸度定义类似于拓扑结构。特别是，集合x上的凸度是其子集的任何集合C，满足三个简单的公理：∅，x∈C; C在任意交集下关闭； C在嵌套工会下关闭。C的元素称为凸集。在集合x上建立凸度的一种方法是从间隔运算符开始，这是从x×x到x（此类映射也称为二进制超操作）的映射I（x，y∈I（x，x，y）和i（x，x，y）= i（y，y）= i（y，x）= i（y，x）= i（y，x）= i（y，x）= i（y，x）。我们将i（x，y）解释为“在”给定x，y∈X的所有元素的集合。随后，我自然会通过声明A集a⊂x凸面来诱导x上的凸度，但如果i（x，y）⊂a a for All x，y∈A。The most well-known examples of convexities arising this way are convexities induced by metric intervals [ x, y ] d = { z ∈ X : d ( x, z ) + d ( z, y ) = d ( x, y ) } in metric spaces and linear intervals [ x, y ] l = { αx + (1 − α ) y : α ∈ [0 , 1] } in normed spaces.实际上，固定集X上的所有凸与X上的所有间隔运算符之间都有GALOIS连接（请参阅命题2.2.1）。图理论，由于顶点对之间的多种路径，自然定义了几个间隔操作器（诱导相应的凸度）。本文结构如下。最短的路径，诱导路径，局部最短路径，无弦路径和其他路径家族产生的间隔操作员如下。如果p是图G中的路径集合，其中g中的每对顶点均与p的至少一个元素连接在一起，然后将i p（x，y）= {z∈V（g）放置在p上的某个路径上，从p连接x，y}。在本文中，我们关注由Interval Operator I P引起的全路径凸度，其中P是给定图中所有（简单）路径的集合。最初，[9]中考虑了这种特殊的凸度，并且[8]中建立了与该凸度有关的经典问题的算法方法。我们还指工作[3]，其中相应的间隔运算符以抽象的方式表征。在第2节中，我们概述了所有在工作中将使用的所有基本定义和初步结果。特别是，第2.1节涵盖了图理论的基础，第2.2节介绍了凸空间，间隔运算符和图形中的全路径的所有必要背景。在第3节中，我们提出了我们的主要结果。首先，我们在第3.1节中给出了全路径凸集的新表征。也就是说，定理3.1.1提供的理论标准比[8]中的理论标准更多，该标准可以轻松地用于获取所有PATH凸集集的所有已知重要属性。此外，定理3.1.1允许我们获得块图（定理3.1.2）的新表征，并在第3.2节中计算All-Path covexity（定理3.2.1）的一般位置号。All-Path的标准