Helly图的凸性结构与几乎不动点性质

2的|理论计算机科学电子笔记161（2006）151-163www.elsevier.com/locate/entcsHelly Graphs中的凸性：集值函数的选择与几乎不动点性质Rueiher Tsaur1，2 和Michael B. Smyth史密斯1，3帝国理工学院计算机系，伦敦SW7 2BZ，英国摘要本文引入了图的凸性结构的概念，称为邻域凸性。证明了邻域凸性是Helly图为2-Helly的图的凸性。然后，我们考虑各种邻域凸几乎不动点性质的Helly图。特别地，我们证明了对任意正数p，每个Helly图都具有邻域凸性p-几乎不动p-弱多值函数的点性质;任何自映射邻域凸强多值函数都有选择。关键词：几乎不动点性质，不动团性质，图凸性，Helly图，多值性，选择性质AMS科目分类：05C99、52C071引言当比较离散结构，特别是图，与经典空间的不动点性质时，我们通常会发现，在离散情况下，我们至多有自同态的几乎作为一个例子，比较m-路径（图）与单位间隔.在以前的工作[11]中，我们已经证明，利用适当的机器，可以以这样一种方式发展比较，即离散结构（图）的几乎不动点性质和拓扑空间的不动点性质在重要的情况下是不可推理的。这个机制的一个重要部分是我们必须考虑多函数的几乎不动点这一点也许可以通过一个简单的1部分由EPSRC赠款GR/R 02344/01支助2 电子邮件地址：rt2@doc.ic.ac.uk3 电子邮件地址：mbs@doc.ic.ac.uk1571-0661 © 2006 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.04.030152R. Tsaur，M.B.Smyth/Electronic Notes in Theoretical Computer Science 161（2006）15121111111010110100011010100000 01 10 11001000000001 010 011 100 101 110111Fig. 1. f1和f2的图例如：考虑从单位区间I到I的连续函数f，定义为f（x）= 1−x对于x，0≤x≤ 1。我们将考虑通过将I（以及相应的I2）细分为单元来近似f细胞被视为封闭的。只有最高维度的封闭单元（因此，不是它们的正确面）出现在简单的表达方式。显然，1是f的精确不动点。此外，很容易看出，在f的逼近过程中，f的离散表示f1和f2可以变成多函数，即 f1：P3→ P3，00 <$→ {10，11}，01 → {01，10，11}，10 <$→ {00，01，10}和11<$→ { 00 ， 01};和f2：P7→P7，000<$→ {110 ， 111}，001→ { 101 ，110， 111}，010{ 100， 101， 110}，011›→ { 011， 100， 101}， 100›→ { 010， 011， 100}，101›→{001， 010， 011}，110{ 000， 001， 010}和111›→ { 000， 001}。图1示出了图1和图2。 因此，函数的离散表示可以是-是多值的而不是单值的还请注意，{01， 10}和{011， 100}分别是f1和f2的几乎不动点的集合我们现在需要更明确地了解这些表征中涉及的离散结构（事实上，正如在开场白中已经暗示的那样在这些表示图之一中，顶点是单元，两个顶点相邻，以防万一，作为单元，它们有一个共同的面。由于细胞有一个共同的面，当且仅当它们重叠为欧几里得空间的子集，这些图是由欧几里得空间的覆盖（由闭集）产生的相交因此，示例所示的情况可以示意如下：连续空间覆盖的交图 离散空间−−−−−−−−−−−−−−−−−−−−→离散空间限制过程 连续空间−−−−−−−−−−→空间上的连续映射和图上的（多值）图同态之间存在类似的双向联系，导致了R. Tsaur，M.B.Smyth/Electronic Notes in Theoretical Computer Science 161（2006）1511532连续函数的不动点←→（多值）图同态的几乎不动点[ 11 ]中详细研究了上述例子提出的离散结构的几乎不动点性质与空间的不动点性质之间的这种在这些表示中，我们必须关注哪些图形显然，我们（至少）有路径的强积：路径、8连通网格以及它们在更高维度中的类似物。我们也许可以将注意力限制在这些方面（就像有时在数字拓扑学中所做的那样）。然而，由于许多原因，将各种图形作为研究对象是方便的。包含简单路径的最小簇实际上包括路径的强积的收缩：一类重要的图，在图论中称为Helly图[6]。精确的定义在第2节中给出，在那里我们还考虑证明了当图G是Helly时，G的容许集构成图的凸性.此外，一个图是Helly当且仅当它的容许集集合具有（2-）Helly性质。尽管它的简单性，这个概念的凸性（我们称之为邻域凸性），据我们所知，没有出现在以前的图论文献。我们将在本文中广泛地研究它，集中在几乎不动点性质（AFPPs），选择函数的存在性和（简单）固定团性质。对于任何非负整数k，p，如果它将任何相邻顶点映射到具有等于或小于k的“集距离”的子集，则称该多功能函数为k-弱;并且如果存在顶点使得顶点与其图像之间的集距离相等，则称该多功能函数具有p -几乎不动点或小于P。我们称一个图对给定的M类多值函数具有p-AFPP，如果任意M类多值函数都有一个p-几乎不动点.我们的主要结果包括：（1）每个Helly图都有邻域凸性[p|-AFPP;（2）对任意邻域凸的强多值函数-从任意有限图到Helly图，存在一个图同态fstec（x）∈ f（x），则fstec（x）∈f（x）.虽然对容许集的考虑在图论中似乎是新的，但等价的概念长期以来一直是超凸度量空间研究的基本工具[1]。Helly图和超凸空间之间的相似性已经被一两个作者指出;我们对此进行了仔细的研究，并在[10]中提出了这两个概念的共同推广。这篇论文以及目前的一个（在意图）是一个大型的正在进行的研究计划的一部分，试图表明，离散和连续的空间模型可以被处理在一个统一的方式，这两个类被近似程序连接。根据人们的观点，人们可能认为离散结构是连续结构的近似，或者相反，分析的连续结构是“真实”离散世界的近似表示。关于本论文，离散/连续逼近主要作为背景动机;然而，我们作为一个例子（第5节）表明，布劳威尔154R. Tsaur，M.B.Smyth/Electronic Notes in Theoretical Computer Science 161（2006）151面对图缺乏精确的不动点性质，图论家倾向于寻找固定团（特别是固定边）性质[5]。问题来了，我们是否可以在我们的多功能设置中获得固定的集团结果这涉及到一些在单值设置中不会出现的复杂情况。我们将在第6节中对这一主题进行简要介绍。虽然我们所有的结果都是组合的，但我们不得不依靠欧氏空间的拓扑来证明其中一个结果;（到目前为止）我们还没有得到一个纯粹的组合证明2Helly图与邻域凸性在本文中，我们只考虑有限循环（自反）无向图。一个图G称为完全图，如果任意两个顶点x，y∈V（G）由一条边连接，即， （x，y）∈E（G）. 图的团是完全子图。设G是一个图。连接x，y∈V（G）的一条路是一列a0a1···ann，它满足a0=x，an=y，且对每个i，0≤in，（ai，ai+1）∈E（G）. 的路径的长度r =a0···an是n。对x，y∈V（G），x与y之间的（图）距离dG（x，y）是从x到y的路径的最小长度（如果存在）。一个图称为连通的，如果每对顶点都由一条路连接。 一个集合X被称为满足（2-）交集性质，如果F的任何两个元素是交集非空的（也称为成对非不相交的）。F满足（2-）Helly性质，如果对于F的每个满足交性质的子族FJ，FJ是交叉点非空。对于任意k∈N，中心在图G的顶点x∈V（G）上的k -球（或k -闭球）是集BG（x，k）={y∈V（G）|dG（x，y）≤k}。 我们称有限连通图G是Helly，如果球族BG（x，k），n ∈x∈V（G），n ∈k∈N满足Helly性质[8].Helly图的简单例子是非空的树，也是树的一部分，也是树的一部分。Helly图在文献中也以圆盘-Helly图（与C-Helly图相反）、绝对收缩和单射对象等形式出现再-称图G的一个（诱导）子图H是G的收缩子图，如果存在一个称为收缩子图的图同态r：G→H，使得对H的每个顶点x，r（x）=x。图G的任何收缩都是等距的，如果对任意x，y∈V（H），dH（x，y）=dG（x，y），则G的子图H是等距的图G1和G2的强积是指图G1 <$G2的顶点集V（G1）×V（G2）是图G1和G2的顶点集的笛卡尔积，且边集E（G1<$G2）使得（（x1，x2），（y1，y2））∈E（G1<$G2）当且仅当（x1，y1）∈E（G1）且（x2，y2）∈E（G2）.我们有Helly图的以下众所周知的（和有用的）性质[6，7]：(1) 一个图是Helly当且仅当它是有限路的有限强积的收缩;(2) 每个图都等距嵌入到一个Helly图中。有限连通图G上的图凸性[3，4]是V（G）的子集的集合，称为G的凸集，使得（c1）集合V（G）是凸的，（c2）凸集的交集是凸的，并且（c3）任何凸集诱导一个连通的R. Tsaur，M.B.Smyth/Electronic Notes in Theoretical Computer Science 161（2006）151155图二、H（G）是一个图凸性，但G不是Helly图图G设G是有限连通图，M是G的球族，M ={BG（x，k）|x∈V（G），k∈N}.则V（G）的子集族（称为容许子集），记为H（G），它包含M和M的元素的所有有限交，具有以下性质：定理2.1若G是Helly图，则H（G）是图凸的.证据条件（c1）和（c2）清楚地成立。对于（c ~ 3），设G的由C诱导的子图G [C]对某个C ∈ H（G）是不连通的，其中C是有限个球族B ={B1，.，Bk}，其中k > 1。请注意，B满足满足条件C/=π 的2 -输入选择性。如果G[C]是连通的（并且G是有限连通的），则存在属于G[C]使得dG（x，y）是最小的（关于所有这样的顶点对）。设dG（x，y）=k≥ 2，由G的某条路l=v0···vk，v0=x，vk=y导出.则存在顶点vi∈BG（x，[k/2|）nl和vj∈BG（y，[k/2|使得球族B J= B ∈ {BG（vi，[k/2|），BG（vj，[k/2|）}满足了2-i的要求;但是，它可以轻松地检查BJ=0。ThusGisnotHelly：矛盾。Q我们称H（G）为图G的邻域凸性。注意，定理2.1的逆命题不成立，见图2。二是反例。著名的定理Helly指出，如果在一个有限族的凸集在Rn，每n+ 1集有一个共同点，那么有一个共同点的所有集。关于图的Helly定理的对于G是H（G）：定理2.2 G是Helly当且仅当H（G）满足Helly性质。证据（只有当）。设B是H（G）的一个满足2-交性质的子集. B的每个元素都是一个球，或者是G的一些球的交集。 设BJ为a所有可能的球族，它诱导B的元素（BJ不是唯一的）。 然后很明显，BJ满足2-输入选择性，并且BJ=Bn。（如果）。这很简单，因为每个球都是H（G）的元素Q156R. Tsaur，M.B.Smyth/Electronic Notes in Theoretical Computer Science 161（2006）151MMMMMMMMnMM3P~ n的邻域凸性AFPs如果V（G）={a0，.，am}且E（G）={（ai，ai+1）|0 ≤i< m}（除了循环）;我们用Pm表示m-路。m-路的强积（n次）路径Pm记为Pn。Pn的最大团有2n个顶点，称为M mPn的初等n-立方。 设C是Pn的初等n-立方，S∈CaM mC的子集。 则S是C的填充子集，如果(1) S的基数，#S=n+1，(2) S不包含在C的任何方面中。Pn的每个顶点x可以用n个坐标（x1，. ，xn），所有整数我不知道。L：V（Pn）→1阶的一个函数到M mn-produectof1stec={0，1}，1stecn，isalabelinggofPnif.Li（x）=0，xi = 01，xi =m对于所有i，1 ≤i≤n，其中x =（x1，.，xn）和L（x）=（L1（x），.，Ln（x））。命题3.1对Pn的任意给定标号L，存在基本n-立方体C，D和填充子集SC，S jD，使得(1) （0，. ，0）∈ L（S），对任意坐标i，1 ≤ i ≤ n，存在一个独立的顶点x∈S，使得Li（x）= 1，(2) （1，.，1）∈L（SJ），且对任意坐标j，1 ≤j≤n，存在一个使Lj（y）= 0的i_n_iv_i_u_v_v_t_x_y∈SJ_u_c.证据 类似于[14]中Q设G是一个图。 对于任意两个非空子集A，B∈V（G），我们记为通过distG（A，B），连接A和B的最短路径的长度，即，dist G（A，B）= inf {dG（x，y）|<$x∈A，y∈B}。注意，dist是一个半伪度量。我们用Pr j表示Pn在其第j个因子上的投影。 对于任何子集A，B对于Pn，我们定义distj， 1≤j≤n，通过distj（A，B）≠distP（Prj（A），Prj（B））。它证明了Pn的所有非空邻域凸集是长方形的blocks（但反之为false）：引理3.2设A，B∈ H（Pn）是任意两个非空邻域凸集则有dist Pn（A，B）= max 1≤j≤ndist j（A，B）.证据在A、B是单例的情况下，该方程是明显的。也就是我们要dPn（a，b）=maxdPm（Prj（a），Prj（b））（1）M（因为Pn是强积）。1≤j≤nMR. Tsaur，M.B.Smyth/Electronic Notes in Theoretical Computer Science 161（2006）151157MM2m+1m+1m+1MMMMn对于任意非空邻域凸集A和B，选择a（j）∈Prj（A）andb（j）∈Prj（B），1≤j≤n，suchhatdPm（a（j），b（j））=distj（A，B）.（2）我们主张，对于a =（a（1），.，a（n）），b =（b（1），..，b（n））（因此显然a∈ A且b∈B），则我们有dPn（a，b）= dist Pn（A，B）.M m设存在AJ∈A，BJ∈B使得dPn（AJ，BJ）dPn（a，b），则由（1）y容易检查Q（x）=（Q1（x），.，Qn（x））是一个标号。 因此存在一个初等n-立方体C和子集S∈C，满足命题3.1的假设. 注意，C 的 每个顶点被标记为（0，. ，0）或与-至少有一个坐标为1。还注意，对于任何顶点x=（x1， . . ，xj， . . ，xn）满足xj=m+1，对于所有的w∈g（x），都有Prj（x）>Prj（w）设z是C的顶点，其被标记为（0，...，0）。显然，z在V（Pn）中。我们证明z是g的一个不动点，因此根据我们前面的讨论，z是a[p]|f的几乎不动点：设不存在，则存在a j ∈ N，1 ≤ j ≤ n，且满足atdis j（{z}，g（z））≥1。 如果Prj（z）>P rj（w），则对于所有w∈g（z），z的j-协方差为1：常数。对于所有的w∈g（z），如果Prj（z）Prj（w）我们有distPn（g（z），g（t））≥1：矛盾。Q3.2P~ n的邻域凸性选择性质设A，B∈V（G）是图G的任意非空子集.则称A和B在G中强相邻，记为（A，B）∈E（Ps（G）），如果下列条件成立：<$x ∈ A，<$y ∈ B，（x，y）∈ E（G）&<$y ∈ B，<$x ∈ A，（x，y）∈ E（G）.定义3.6设G和H是图。 从G到H的函数f，f：G→H，是强的，如果对每对相邻顶点x，y∈V（G），（f（x），f（y））∈E（Ps（H定义3.7（1）设f：H→G是一个多函数。f的一个选择是一个具有任意v∈x∈V（H），fstec（x）∈f（x）的自同构图f stec：H → G.(2)称图G具有邻域凸强集值选择性质，如果对任意邻域凸强集值f：H→G，其中H是任意有限图，f有选择.请注意，对于拓扑空间上连续选择的定义，我们参考[2]。定理3.8Pn具有强邻域凸选择性质多功能160R. Tsaur，M.B.Smyth/Electronic Notes in Theoretical Computer Science 161（2006）151MMMMMMMMMMMMMM一MM证据 设H是任意有限图，f：H→Pn邻域凸性保存多个功能。Deftec：H→Pn，fstec（x）=inf（f（x）），对于一个yx∈V（H）. 其中，fstec（x）=（inf（Pr1（f（x），. . ，i nf（Prn（f（x）∈V（Pn）. 这一点很清楚，对于一个x∈V（H），f_stec（x）是P_n的一个可微定界的。 我们证明了fstec（x）∈f（x）：对任意一个点，我们都有一个fstec（x）/∈f（x）. 3.我的朋友2、最小值x是一个协方差i，1≤i≤n，满足disti（fstec（x）， f（x））= distPm（Pri（fstec（x）），Pri（f（x）=distPm（inf（Pri（f（x），Pri（f（x）≥1。他是他是我-因为Pn是一个有限图。我们证明了Fstecisagrandaphomomorphism.我想，为了一个没有-没有-没有的人P ~n的邻域凸集A和B，如果（A，B） ∈E（Ps（Pn）），则M m（ inf （ A ） ， inf （ B ） ） ∈E （ Pn） ： 如 果 w∈A （ 特 别 地 ， 如 果 w = inf（A）），则<$z∈B满足atPrj （z）−Prj （w）≤1，对于所有llj∈N，1≤j≤n.Henceinf （Prj （B ））−i nf （Prj （A））≤1。 因为对称，我们有|i nf （Prj（A））−i nf（Prj（B））| ≤1。Q4Helly图命题4.1设r：Pn→A是一个收缩。 对于任何非空的邻居-A的罩凸集C，记为C在Pn中的凸包（即，满足C ∈ KC）最小邻域凸集。 然后我们有，对于任何A的非空邻域凸集B、C(1) C = KC A。(2) 如果KB= KC，则B = C。(3) r（KC）≠ C.(4) 若（B，C）∈E（Ps（A）），则（KB，KC）∈E（Ps（Pn））.证据（1）由于A是Pn的一个收缩核，所以对任意的顶点x∈A，有BA（x，i）=BPn（x，i）<$A（x在A中的每一个i球等于x在Pn中的i球与A的交）.结果立即出现。(2) 直接从（1）得出。(3)注意，对于任何顶点x∈A，i∈N，我们有r（BPn（x，i））<$B（x，i），因为r（x）=x，并且r是非距离增加的。 现在我们知道C=j∈JBA（x（j），i（j）），对合适的指标集J<$N，x（j）∈A，i（j）∈N.因此集合K =j∈JBPn（x（j），i（j））通过r映射到C. 但K是（邻域-）在Pn中是凸的，且包含C.因此r（KC）<$C。(4) 这里把KC看作是包含C的最小矩形块是有帮助的。因此，如果b是K B的任何顶点，我们有，对于范围1中的每个i，.，n，Pri（b）= Pri（z（i）），其中z（i）R. Tsaur，M.B.Smyth/Electronic Notes in Theoretical Computer Science 161（2006）151161∈B.由于（B，C）∈E（Ps（A）），每个z（i）都与C的某个元素相邻，比如w（i）.因此，b与w =（Pr 1（w（1）），.，Prn（w（n））），且w∈KC. 类似地，KC中的每个元素都与KB中的某个元素相邻。Q如上所述（第2节），G是Helly图当且仅当G是收缩图162R. Tsaur，M.B.Smyth/Electronic Notes in Theoretical Computer Science 161（2006）151M2MMMM对于m和n，定理4.2每个Helly图都有[p|-邻域凸性的AFPPp-弱多值函数证据我们可以认为G是Pn的一个收缩（即r：Pn→G是收缩）.M m设f：G→G是任意邻域凸p-弱泛函. 定义多函数g：Pn→Pn，M mg（x）={C|（f <$r）（x）<$C，C ∈ H（Pn）}= K（f<$r）（x），对任意x∈V（Pn）. 显然，如果（x，y）∈E（Pn），则distG（（f <$r）（x），（f<$r）（x），（f<$rM mnr）（y））≤p。 因此，distPn（g（x），g（y））≤p，因为（f<$r）（z）<$g（z）对所有z∈PmmnpG是Pm的等距子图. 因此，根据定理3.5，g具有a [2|-几乎不动点，设x∈V（Pn）. 我们证明了r（x）是a [p|- 几乎不动点M事实上，由于distPn（{x}，g（x））≤[p2|, there exists a y ∈ g (x) such thatpm2dPn（x，y）≤ [|. 然后通过命题4.1（3），显然我们有distG（{r（x）}，（f））m2pr）（x））≤dG（r（x），r（y））≤[2|.Q定理4.3每个Helly图都具有邻域凸强集值的选择性质.证据考虑G是Pn的收缩核，其中r：Pn→G是收缩核.设HM m是任意图，且f：H→G是任意邻域凸强多功能图.我们定义多功能g：H→Pn为：g（x）= {C |f（x）<$C，C ∈ H（Pn）}= Kf（x），对任意x∈V（H）。显然，如果（x，y）∈E（H），由命题4.1（4），g（x）和g（y）在Pn中强相关（因为f（x）和f（y）在G中强相关）.这是我们的，从第三个。8，gh asas election，s aygte c.Letfstec=rgste c 。例如，f是一个图同态。进一步，对任意x∈V（H），由命题4.1（3），我们有一个fstec（x）=（rgstec ）（x）<$（rg）（x）=f（x）. 他必须参加选举。Q5应用：Brouwer不动点定理的一种新证明正如在我们以前的工作中[11]一样，我们要声明我们的“离散”结果不仅是经典“连续”定理的类似物，而且它们之间存在演绎关系。我们不讨论这个主题广泛在本文件中，但只是说明它与布劳威尔的不动点定理的例子事实上，这是定理4.2的一个简单推论：定理5.1每个闭n-（拓扑）球都有不动点性质。证据 在不失一般性的情况下，我们可以对单位n-立方体In证明它. 让f：In→ In是从In到In的任何连续函数。 将In除以mn闭合R. Tsaur，M.B.Smyth/Electronic Notes in Theoretical Computer Science 161（2006）151163M−M1m−1MM单元格（立方体），1边长，并表示此集合的相交图细胞的Pn。由于In的胞元与Pn的顶点之间存在一一对应关系，因此我们使用逆符号m−1−1nA，P，nm−1. 定义多函数g：Pnm−1 →Pn由m−1g（x）=K{y∈V（Pn）|y−1<$f（x−1）/=<$}。因为f是连续的，所以很容易检验g是弱邻域凸性多值函数。根据定理4.2，g有几乎不动点。显然，如果z∈V（Pnm−1）是g的几乎不动点，则存在点（顶点）t∈z−1√苏志达|t，f（t）|≤2·n。如果单元n-cubeI是一个紧凑型，则m→∞因为f的一致连续性，所以f有一个不动点。Q6Helly图的邻域凸性FCP（略）在图论中，讨论固定团性质（FCP）比讨论AFPP更常见。当然，这样的讨论通常限于单值函数，很明显，在这种情况下，FCP比AFPP更强：如果对于每个自映射单值图同态f，存在团C，则称图G具有固定团性质（FCP），其中C=f（C）。作为一个例子，Nowakowski和Rival [5]证明了任何有限非空树T对于单值图同态都具有FCP（当然，固定边性质）。定义6.1G是一个图：(1) 设f：G→G是一个集函数，则称团C是一个固定团f，如果C≠f（C）。(2) 称G具有邻域凸弱集值的固定团性质（FCP），如果G的每个邻域凸弱集值都有固定团.回想一下，弱泛函f：H→G是单纯的，如果它将H的任何团C映射到G的子集的集合f（C），满足条件：存在一个集合n（ba）a∈C的v值s，其中h ba∈f（a），|a∈C}是一个G. 通过适应证明类似的结果（参考AFPP的图形，而不是比图的FCP）形式[11]（定理5.4），我们可以证明：定理6.2Pn对邻域凸单纯弱多功能协调发展的定理6.2（或[11]中定理5.4）的证明除了长度之外，还有一个令人不快的特征，即它依赖于经典拓扑学;我们目前还不能给出一个纯粹的组合证明。然而，从任何有限图到Helly图的邻域凸弱多值函数必然是单纯的：关系例如是是I对于给定子集164R. Tsaur，M.B.Smyth/Electronic Notes in Theoretical Computer Science 161（2006）151MXMMMMMMMMM引理6.3设H是有限图，且f：H→Pn邻域凸性弱多功能f是单纯的。证据 让 C是 任何 H.为 任何 x∈C，设C是y∈C\xBPn（f（y），1）<$f（x）. 很明显，对于每个x ∈ C，C x ∈ C，通过以下性质，的Helly（和Pn的邻域凸性）。此外，对任意z∈Cx，z与f（w）的某个顶点相邻，对任意w∈C\x.我们声称存在Cx的选择（zx）x∈C（因此f（x））使得{zx|x ∈C}是Pn的团.实际上，由于Cx∈ H（Pn）和（Cx，Cy）∈E（Ps（Pn）），对任意x，y∈C，因此，M m从Theorrem4. 3.由于存在着一个选择性的步骤（C），所以它是一个选择性的步骤：C→Pn， x→Cx满足我们的要求。Q命题6.4设H是有限图，G是Helly图。 则任何邻域凸弱泛函f：H→ G是单纯的.证据由于G是Helly的，因此我们可以认为G是Pn（说，r：Pn→G是收缩）。 定义多函数g：H→Pn为：M mg（x）=Kf（x）∈H（Pn），对任意x∈V（H）。显然g是邻域凸弱集值函数，由引理6.3可知g是单纯的.设Δ是H的任意团。由于g是单纯的，存在Λ =（zx）x∈Δ，zx∈g（x）使得Λ是Pn的团.由命题4.1（3），我们有r（zx）∈r（g（x））<$f（x），对于每个zx。 则（r（zx））x∈Δ是G的团. 所以f是单纯的。Q设Δ是函数f的一个固定团。 则Δ被称为极小(or在[12]中不可约），如果没有Δ的真子集ΔJ满足ΔJ<$f（ΔJ）：引理6.5（引理21 [12]）设G是一个图，f：G→G是一个自映射多值集.若Δ∈V（G）是f的极小固定团，则对任意x∈Δ，存在且仅存在一个y ∈ Δ使得x ∈ f（y）.证据 定义一个有向图H=（Δ，R），uRv<$v∈f（u）对所有的u，v∈Δ。显然，H中的任何圈都确定f的一个固定集（团）;由于Δ是最小的，所以每个圈都是哈密尔顿的。这样就很容易看出H的每个顶点都有一个唯一的前身。实际上，Δ由单个周期组成，并且函数通过限制和余限制f到Δ而得到的f→ Δ是一个双射。Q定理6.6对于邻域凸弱集值函数，每个Helly图都有FCP。证据 从定理6.2和引理6.3（或命题6.4）可以清楚地看出，具有邻域凸弱集值函数的FCP。设G是一个Helly图，f：G→G是任意邻域凸弱集函数. 由于G是Helly，我们可以认为G是Pn的收缩核，其中R. Tsaur，M.B.Smyth/Electronic Notes in Theoretical Computer Science 161（2006）151165MMr：Pn→G是收缩。定义函数g：Pn→Pn，嗯嗯g（x）={C|（f <$r）（x）<$C，C ∈ H（Pn）}= K（f<$r）（x），对任意x∈V（Pn）.如定理4.2所示，g是邻域凸弱泛函。有一个固定的集团，比如说Δ。我们证明f有一个固定团：不失一般性，我们可以假设Δ是最小的。根据引理6.5，对于任何x∈r（Δ），使得x=r（y），对于某个y∈Δ，（对于所有y）存在唯一的z∈Δ使得y∈g（z）. 因此，根据命题4.1（3），我们有r（y）∈f<$r（z）。然后，由于所有的r（z）都在r（Δ）中，因此我们有r（Δ）<$f（r（Δ））（这意味着r（Δ）是f在G中的固定团）。Q引用[1] Aronszajn，N.，和P. Panitchpakdi，Extensions of uniformly continuous transformations andhyperconvex metric spaces，Paci fic J. Math.6（1956），405[2] 边境，K。C.的方法，[3] 但是，P. 和H。 M eyni el，Ensembleconexesd anslesgra he remesdeHellyetdeRadonpour graphes etsurfaces，European J. Combin. 4（1983），127[4] Duchet，P.，图中的凸集II，最小路径凸性，J. Combin。Theory Ser. B44（1988），307-316.[5] 诺瓦科夫斯基河，和I. Rival，Fixed-edge theorem for graphs with loops，J. Graph Theory3（1979），339-350.[6] 诺瓦科夫斯基河， 和I. Rival，包含所有路径的最小图簇，离散数学。43（1983），223[7] 奎利奥特，A.，“Homomomomorphismes，pointsfixes，rotractionsettjeuxeporsuitedanslesgraphes，lesensemblesordonnoesesetlesss“，Th`esede3acycle，UniversitedeParisVI，1978.[8] Quilliot，A.，关于Helly性质作为图的紧性准则，J. Combin。Theory Ser. A40（1985），186[9] 奎利奥特，A.，不确定性的不确定性取决于不确定性，因为不确定性是一个复杂的问题，因此，DiscreteMath。111（1993），435[10] 史密斯，M.B、和R.Tsaur，超凸半度量空间，拓扑程序。26（2001[11]史密斯，M. B、和R. Tsaur，AFPP vs FPP：the link between almost fixed point properties of discretestructures and fixed point properties of spaces，Appl. Categ. Structures11（2003），95[12] 曹尔河和M.B. Smyth，Sci. 2243（2001），75[13] 曹尔河和M. B.史密斯，不动点在数字拓扑（通过Helly偏序集），电子。笔记理论。Comput. Sci. 74（2003）。[14] 曹尔河The Baillon-Simons Theorms，To appear in DiscreteMath.293（2005），251-261.