图的分解与连通性：不可数基数边不交子图的结构

理论计算机科学电子札记87（2004）205-224www.elsevier.com/locate/entcs不可数图的可数特征FranccoisLaviolette1，2D'epartementdQu'ebec，Canada摘要本文证明了一个图总是可以分解成具有可数基数的边不交子图，其中原图的边连通度和边分离度直到可数基数为止都保持不变。我们还证明了任何图的顶点集都可以被赋予一个良序，这个良序在边分离方面具有一定的紧性。关键词：图，分解，连通性，不可数基数。1介绍对物理系统建模的过程分析在计算机科学中，例如在控制系统理论中越来越受到关注一个物理系统，如一个运动的粒子或一个房间的温度，涉及到连续的参数，因此可能需要一个具有无数状态的模型。混合系统理论（参见[2]）和标记马尔可夫过程理论（[4]）都涉及到它们的分析。即使在实践中，人们通常希望在使用系统之前将其离散化，甚至在对其进行推理之前，连续系统的理论允许人们争辩说，实际上是一个过程的忠实模型。在组合学中已经发展了许多分析有限系统的技术，1由NSERC部分支持的研究2电子邮件：francois. ift.ulaval.ca1571-0661 © 2004由Elsevier B. V.出版，CC BY-NC-ND许可下开放获取。doi：10.1016/j.entcs.2004.09.019206F. Laviolette /理论计算机科学中的电子笔记87（2004）205-224≤都是在有限的情况下进行研究的。本文件可被视为朝此方向迈出的一步。在混合系统理论中，物理系统的分析是用有限过渡系统进行的，其中一个状态可以编码不可数数量的参数值，这些参数值与系统的观察行为是等价的另一方面，在[4]中表明，有一些标记马尔可夫过程具有不可数多个状态，但不能被还原为有限个甚至可数个状态空间过程。在后一种情况下，我们认为，有一个基本因素可以防止这种减少。马尔可夫过程的无限性与不确定性和非决定性的表现方式，即与概率分布密切相关;连续概率论的丰富性确保了我们不可能在不损失某种信息的情况下摆脱不可数性对于非概率过程，通常的直觉是，考虑具有不可数多个状态的过渡系统没有实质性的收益。本文使这一思想更加精确，证明了不可数迁移系统的底层图总是可以分解成可数的片段，每个片段保持原图的边连通性。这个结果是关于无向图的，它的推广到有向图的情况似乎更加困难，仍然是开放的。我们的约定是，分解是E（G）上的等价关系，使得每个片段（即，由等价类的边导出的子图）是连通的。我们感兴趣的是找到分解，其片段尽可能地继承原始图的边连通性，在这个意义上，对于给定的无限基数α，分解的片段都是最多α的顺序，并且没有键（即上循环）。基数α的分解被分成属于不同片段的片段：这样的分解将被称为键忠实α-分解。本文的主要结果（定理4.6）是：对任何图G，总可以构造一个键忠实的ω-分解。有趣的是，本文的结果在有限情形下没有悬垂性。事实上，在有限的情况下，以下仍然是一个猜想（见DeVos，Johnson和Seymour [5]），即使在无限的情况下（即，a和b是无穷大的情况），这是命题4.8的一个弱化。设G是（a + b +2）-边连通图。是否存在分区{A，B}使得（V，A）是a-边连通的，（V，B）是b-边连通的？定理4.6在[9]中被用来对可数情形进行简化，这种情形相当容易处理。这一应用是第一个动机-F. Laviolette /理论计算机科学中的电子笔记87（2004）205-224207⊆为引入概念和证明本文的主要结果作了必要的说明。在本文的最后一节中，我们证明了任何图的顶点集都可以被赋予一个良序，该良序具有关于边分离的某种紧性，在这个意义上，给定任何（序）有界子集X V（G）和任何上界u，如果X不能通过去除有限条边而与u分离，则对于X的某个有限子集也是如此。从这个结果可以得出，在有限图中，总是可以构造一个接一个的顶点，以这样的方式，在每一步中，总是有一个有限的边集，将新添加的顶点与所有先前的不是无限边连接到它的顶点分开。一般来说，总是存在一个有限的边集，将顶点x与任何其他不是无限边的顶点y分开。这种构造的特别之处在于，它保证了一个有限的边集将同时对所有y均匀地完成这项工作。这个结果提供了一个有趣的工具，如果一个人希望在无限图上进行递归构造，并且不希望构造的第一步与其他步骤干扰“太多”。特别是，这可能会打开自动结构理论的新视角。本文中的所有结果都依赖于分解成可数片段，但在广义连续统假设下，它们可以扩展到任何不可数基数，参见[8]中的一般情况下的所有证明，以及其他相关结果。2定义和分类为了本文的目的，我们假设所有的图都是无向的，没有循环或多个边，除非另有说明。符号G总是表示一个图。一个回路是一个2-正则连通图，一个圈是一个有限回路。图G的块是图G的极大2-点连通子图关于包含;特别是由桥或环组成的子图是块。如果L∈E（G），则G\L表示从G中去掉L中的所有边（保留所有顶点）得到的图。若X<$V（G），则G[X]表示G在X上的导出子图.设x∈V（G），A，B表示G的子图，记G−x=G[V（G）\x]，G−A=G[V（G）\V（A）]，G\A=G\E（A），[A，B]G表示G的顶点相连的边集到B的顶点。当不可能发生混淆时，我们将G-A写成A。G的割是形式为[A，A]G的一组边。 除非另有说明，A是G的导出子图。 一个奇怪的（resp。 even）cut是一种208F. Laviolette /理论计算机科学中的电子笔记87（2004）205-224一一基数是奇数（分别为偶数）。一个键是非空的切割，这是最小的关于包含。观察连通图G的割[A，A]G是一个键当且仅当A和A都是连通的。注2.1（连通或不连通）图的割[A，A] G是一族边不相交键的并。很容易看出，如果A或A是连通的，则族是唯一的。如果A和A都是不连通的，那么唯一性就不成立，如图1的例子所示，其中[A，A]G是三个键的并集，这三个键分别由与A的每个顶点关联的边的集合组成，也是键关于A的三个顶点对称定义。一般而言，鉴于对于G的一个割[A，A]G，我们可以很容易地构造出一个合适的键族F：设（Ai）i∈I是G的诱导子图hA的所有键族的集合，对于每个i∈I，设Fi是G的唯一键族，其并是[Ai，Ai]G，然后把F：=i ∈IFi.图1.一、注2.2 G的每个键都包含在G的某个块中。为了证明这一点，假设x是G的一个截点，[A，A]G是G的一个键。如果x∈V（A），则G−x的连通子图A必须包含在G−x的单个分支中，因此x不能分离[A，A]G的边;如果x∈V（A），则类似的论证也适用。对于任意两个不同的顶点x，y∈V（G），我们用γG（x，y）表示x和y之间的边连通度.根据门格尔定理的弱形式因此，γG（x，y）= 0当且仅当x，y属于G的不同连通分支.注意，假设每个顶点与κ-顶点连通性不同，κ-边连通性在V（G）上导出一个等价关系，因为对于每个基数κ，γG（x，y）≥ κ和γG（y，z）≥ κ =<$γG（x，z）≥ κ。这种关系的等价类称为κ-边连通类F. Laviolette /理论计算机科学中的电子笔记87（2004）205-224209或者简单的G的κ类。 只有一个κ-类的图称为κ-边连通图。本文只考虑基数ω以下的边连通性。因此，我们将主要使用边连通性的截断定义：定义2.3设x和y是G的两个顶点，我们定义γ∈G（x，y）如下• 当γG（x，y）≥ω时，γ<$G（x，y）=∞;• γ<$G（x，y）=γG（x，y） 。在第一种情况下，我们说x和y是无限边连通的。G的分解是E（G）上的一个等价关系，使得由任一等价类的边导出的子图是连通的。以这种方式导出的子图称为分解的片段。因此，G的分解可以被认为是G的一族边不相交的连通子图，其并集是图G减去其孤立点。最常研究的分解是其片段是循环的分解（即，循环分解）和其片段是循环、射线或双射线的分解。关于无限图存在这样的分解的结果，参见Nash-Williams [10]，Sabidussi [11]，Lassen [13]或Laviolette [7]和[9]。本论文的主要定理依赖于我们将称为纳什-威廉姆斯定理（Nash-Williams [10]）一个图有圈分解当且仅当它不包含任何奇割。对于某个（有限或无限）基数κ，其碎片都是κ-边连通的分解称为κ-边连通的，对于某个无限基数α，其碎片的基数都小于或等于α的分解称为α-分解。本文寻找ω-分解，特别是其片段继承原图的边连通性的ω-分解更确切地说，我们考虑以下类型的分解：定义2.4称G的ω-分解是键忠实的，如果(i) G的任何可数键都包含在G的某个片段中;(ii) G的一个片段的任何有限键也是G中的一个键。在G的键忠实ω-分解中，G的任意可数键B是由（i），包含在某个片段H中，因此是H的一个截集。此外，委员会认为，210F. Laviolette /理论计算机科学中的电子笔记87（2004）205-224∞如果B是有限的，那么这个切割总是H的一个键，因为否则有一个H的键BJ严格包含在B中，由于（ii），它也必须是G的一个键，这与B是G的一个键的事实相矛盾。因此，对于任何边集B∈E（G），总是满足以下性质：(1) 如果B是有限的，则B是G的键当且仅当它是G的某个片段的键;(2) 若B是G的可数键，则B是G的某个片段的割(3) 如果B是不可数的，且B是G的一个键，则在任何含有B的边的片段H中，B∈E（H）是H的一个可数割.此外，请注意，由于割是键的边不相交的联合，并且由于键忠实性定义的条件（i），我们可以等价地将该定义的条件（ii）替换为：(iiJ）G的一个片断的基数的任何有限割也是G中的一个割。键忠实ω-分解的一个基本性质，将G的局部边连通性与分解的片段的局部边连通性联系起来，在下面的命题中表达。命题2.5如果H是G的键忠实ω-分解且x，y是H的任意两个顶点，则γ<$H（x，y）=γ<$G（x，y）.我的律师。 由于H∈G，则有γ∈H（x，y）≤γ∈G（x，y）. HenceifγH（x，y）=这没什么可说的。另一方面，如果γ∈H（x，y）=kω，则存在一个基数为k的H键将x和y分开。按财产分列（二）这意味着，γ<$G（x，y）≤k=γ<$H（x，y）≤γ<$G（x，y）.Q注2.6从命题2.5可以得出，如果G是β-边连通的，其中β≤ω，则G的键忠实ω-分解的每个片段同样是β-边连通的。由于图G的分解是E（G）上的等价关系，我们有关于图G的分解的以下自然偏序。定义2.7分解2比1粗（表示为2≥1）如果每个片段的1，包含在一些片段的1，2。F. Laviolette /理论计算机科学中的电子笔记87（2004）205-224211≤关于这个顺序，任何（有限或无限）分解族都有上确界和下确因为片段必须连接，所以在所有等价的集合中，下确界并不总是与下确界一致关系然而，对于suprem（用d表示i∈ I<$i），则引理Lemma2. 8Let（i）i∈I是群G的一族分解. Theni∈I i是等价关系式i的并集的逆闭包。证据由于E（G）上所有等价关系的集合中的所有等价类的并的传递闭包都已经是所有等价类的上确这很简单，留给读者。Q可数上确界尊重ω-分解，甚至以强的方式保持键忠实性。Lemma2. 9Let（i）i∈I是G的ω-分解的可数族. Then=i∈Ii是一个ω-分解，若族中至少有一个键忠实的ω-分解，则I也是键忠实的.证据第一个断言来自于这样的事实，即任何一个π的片段至多是所有基数至多为ω的片段的并集。现在假设这个族包含一个键忠实的ω-分解ω0。那么，从<$0 <$起，G的任何可数键都包含在<$0的一个片段中。此外，如果B是一个H的片段H的有限键，则对任何边e∈B，B与包含e的H0的片段H0是H0的割集. 因此，B包含H0的键B0。由于B0是键忠实的，B0是G的一个键。由于B0是G的一个键，B0<$B<$E（H），因此B0是包含在H的键B中的H的非空切割，因此B=B0，它是G的一个键。Q3 ω-覆盖与2-边连通分解G_ivenacardinalκ，g_iG的κ-c上是G的子图的族（Hi）i∈I使得G的每条边恰好属于这个族的κ个成员因此分解是所有成员都连通的1-覆盖最受关注的情况是κ= 2的Seymour双覆 盖 猜 想 ， 即 每 个 2- 边 连 通 图 允 许 一 个 [2][3][4][5][6][7][8][10][11][12][13][14][15][16][17][18][19][下面的结果是（实质上）削弱了这个猜想。定理3.1每个2-边连通图都有圈ω-覆盖。212F. Laviolette /理论计算机科学中的电子笔记87（2004）205-224JJ我∈我JJ我我FFj∈JiBi j）。Givenj∈Ji，fixtwoarbitrary我J我JJ我我证据设x0∈V（G），对于每个i >0，设Di是2-边连通图G的边集，G的一个端点距离x0为i−1，另一个端点距离i。设D0是G的边的集合，其端点是与x0的距离相同。注意，DiD i=[A i，A i]，其中A i={y ∈ V（G）：dist G（x0，y）≤ i − 1}.我们现在将对每个i≥0构造G的一个圈族Fi，使得Di的每条边至少属于Fi的一个圈，并且G的任何边都不属于Fi的多于ω个圈。为了得到F0（最简单的情况），我们按如下进行.将G\D0中的每条边替换为具有相同端点的ω边，构成重图G0注意G0是ω-边连通的，因为对于任何x∈V（G0）（=V（G）），x0x-测地线的任何边都不属于D0;换句话说，测地线的所有边都将被复制ω次。因此G0没有有限割，因此也没有奇割，这意味着第2节中的纳什-威廉姆斯任何一个G0的圈正则地诱导G中的一个圈或E（G）\D0中的一个边，后一种情况仅在循环的长度为2时发生设F0为G的所有圈的族，这些圈是由G的圈正则诱导的。那么F0将具有所需的性质，因为D0中的任何边都必须恰好属于F0中的一个圈，并且最多有ω个F0的圈可以包含给定的边。现在让我们构造Fi，其中i>0。因为Di是G的一个截集，所以它是键的不相交并（例如Di=不同的边缘e1B ij（注意，|B ij|≥ 2，因为假设G和e2是2边连通的）。与G的构造相同，让我们构造Gk，k=1，2，通过在G中替换E（G）\Di的每个边和每个ek（j J i）通过具有相同端点的ω边。 注意，G k，i > 0，k = 1，2，都是ω -边连通的，因为V（G k）= V（G），并且G的边是ω -复制的（即， （E（G）\D i）<${ek：j ∈ J i}中的边E（G）\n i∈ {Ek：j∈Ji}）构成G的一个连通生成子图.因此，正如我们对0所做的那样，我们可以构造两个循环族k（k=1， 2），使得G的任意边至多属于Fk的ω个圈，且Di的任意边\{ek：j∈Ji}I j属于Fk的至少一个圈。 由于{e1：j ∈ J i}与{e2：j∈Ji}，Fi：=F1<$F2将具有所需的两个性质（循环是在家庭中出现不止一次）。最后很容易看出，由i≥0Fi中每个圈的ω拷贝组成的族是G的ω-覆盖。Q在这个证明中使用的Nash-Williams定理是基于一个高度F. Laviolette /理论计算机科学中的电子笔记87（2004）205-224213∈∈ni=1βHββ非平凡transfinite归纳法然而，正如后面将看到的，定理3.1蕴涵推论4.2，它允许将纳什-威廉斯定理的证明简化因此，定理3.1的任何直接证明都将引起纳什-威廉斯定理的直接证明.此外，定理3.1在无限情形下给出了圈2-覆盖猜想的部分答案。推论3.2每个无桥图都有2-边连通ω-分解。证据 设G是这样一个图。 我们可以清楚地假设G是连通的，即2边连接。 设Φ是定理3.1给出的G的圈ω-覆盖等价关系定义为关系Θ在E（G）上的传递闭包，其中eΘeJ当且仅当Φ包含一个既包含e又包含eJ的圈.断言：n是一个 2-边连通ω-分解。设H是H的一个片断。(1) H是连通的，因为对于任意两条边e，eJ∈E（H），存在e1，.，en∈E（H）使得e=e1，EJ=en且对任意i=1，2，.，n−(2) H是平凡2-边连通的，因为任意边eE（H）包含在Φ的一个属于H的圈中.(3) H至多是可数的，因为任何边eE（H）至多与ω条其它边Θ-相关，且θ是Θ的传递闭包。Q4键忠实ω-分解本节的目的是证明每个图都有一个键忠实的ω-分解。引理4.1设G的ω -分解是G的一个ω-分解。则存在一个比G的ω-分解G，它比G的ω-分解更粗，并且具有这样的性质：对于G的任意片段H，H的可数键中唯一是G的键的是G的相应片段的键。因此，G证据 对于φ0的每个片段H，设（BH）β∈γ是H的所有可数键不是G的键的集合。然后对于每个β∈ γ H，固定BH 中的一条边eH. 以来|E（H）|≤ ω，H至 多 具有ω键，基数ω< 因此，在不失一般性的情况下，我们可以假设，∈1 .一、 设C iΦ是包含e i和e i+1的圈，注意：H的一个连通子图，包含e和EJ。Ci是214F. Laviolette /理论计算机科学中的电子笔记87（2004）205-224ββ\≤βββ≤ββββββββββββββ每个H，序数γH要么是有限的，要么是序数ω。让Gβ：=G\{BH\eH：H是γ0的片段且γH> β}对于任何β ω。 给定任意β0的碎片K和任意β γK，eK是一Gβ的边，因为G β0的片段是两两边不相交的。然而，我们认为eK不是Gβ的桥。否则，eK仍将是一座桥梁，β βG\（BK\eK），因为G\（BK\eK）可以从Gβ通过将每个BH\eH除了BK\eK本身，因为H\（BH\eH）是连通的图G的子图。 因此，BK将是G的一个截集，并且因为它是K的键，所以它也是G的键，矛盾。现在，对于每个β ω，应用推论3.2并选择Gβ\{e∈E（Gβ）：e是Gβ的桥}的2-边连通ω-分解Γβ。然后设Φβ是G的ω-分解，它是由Gβ的每一个桥和Gβ的每一条边作为一个元素的等价类相加而得到的. 此外，对于每个边eH，fix一个包含eH的圈CH，并且包含在β β βΦβ包含eH。因此，BHE（CH）={eH}，对于任意的H {\displaystyle H}，β和任何β γH。β β β让我们证明，ω：= ω0ω（β ωΦβ）是所需的ω-分解。显然，0，从引理2.9可以得出是一个ω-分解。用LH表示包含H（因此也包含所有的eH由于对于任何H，CH包含在LH中，因此CH\eH是一条路径（边-边）。（2）两个人的交往，是两个人的交往，是两个人的交往。由BH在H中评级。 因此没有BH可以是LH的键。Qβ β应用前面的引理ω次，我们将得到满足键忠诚定义的条件（ii）的ω这就是下面的推论的内容。推论4.2设ω 0是G的一个ω-分解。则存在一个ω-分解<$0 ，使得<$0≤<$0，且在G中，π也是一个键。证据通过引理2.9，我们可以归纳地构造一个ω-分解的递增序列（ωβ）β ω如下：• - -• <$β+1是一个ω-分解，使得<$β≤ <$β+1，并且具有引理4.1的性质，其中<$0，<$0分别被<$β，<$β+1代替。我们认为ω =β ωβ是一个具有所需性质的ω首先注意到，由引理2.9可知，ω 0是ω-分解。现在，通过矛盾的方式，设B是片段的任何有限键，F. Laviolette /理论计算机科学中的电子笔记87（2004）205-224215--−∪ ⊆−如果K是G的包含H的分支，则K\B仍然是连通图，因此B的子集不能是G的键。固定一条边e∈B，对于任意序数β ω，用Hβ表示包含e的ββ的片段。很容易看出，（Hβ）β ω是G的一个嵌套的子图序列，它的并集是H，B∈E（Hβ）是Hβ的一个割。割是键的边不相交并，存在Hβ 的键[Aβ，Aβ]Hβ，该键包含在B中。由于BβE（Hβ）中没有一个子集是G的键，因此[Aβ，Aβ]Hβ不是Hβ+1的键。这和Hβ\[Aβ，Aβ]Hβ是由两个连通分量（即Aβ和Aβ）组成，意味着Hβ+1\[Aβ，Aβ]Hβ是连通的.因此，存在完全包含在Hβ+1\Hβ中的Aβ Aβ-路径，因此，B<$（E（H β+1）\E（H β））<$对于任何β<ω。由此可见，B是无限的，是矛盾的。Q注4.3设G是一个无奇割的图.显然，由推论4.2给出的G的任何分解都只包含可数个没有奇割的片断（其中，分解的所有因此，如前所述，推论4.2允许将纳什-威廉定理的证明简化在继续我们的主要定理之前，我们需要最后一个结果，它表明不可数图中的“高”度顶点定理4.4设G是连通图（可能有和重边），x ∈ V（G），μ是正则不可数基数. 如果deg G（x）≥ μ，则x是G的割点或μ-点连通到某个点y/= x。证据设x不是G的割点。因此G x仍然是连通的;选择G x的一个生成树T，设J是T A的所有圈的并集，其中A是G的由与x关联的所有边导出的子图。因为T是一棵树，所以T的任何圈都必须包含x。J是连接的。此外，委员会认为，因为T是连通的，G的任何两条与x相关联的边e1，e2必须是包含在T A的某个循环中，这意味着AJ1= JX是一棵树我们证明了某个y∈V（J1）在J1中的度至少为μ.通过矛盾的方式，假设情况并非如此。设u是J1的任意顶点.通过一个简单的归纳论证，我们可以证明，Di：={v∈V（J1）：distJ1（u，v）=i}所有的红衣主教都比我们少，|Di| ≤v∈Di−1degJ1（v）216F. Laviolette /理论计算机科学中的电子笔记87（2004）205-224联系我们^对于nyi>0. 这是一个关于V（J1）∈ωDi的一致性传统，|是一个规则的基数。|≥ µ and µ is a regular cardinal.注意，J−y是连通的，因为如前所述，不A必须包含x。 由于J1=Jx是一棵树，Jx，y将分解成至少μ个分量，每个分量与x和y一起构成xy-路，这样我们至少得到μ个内部顶点不相交的xy-路。Q推论4.5如果连通图G（可能有圈和重边）不包含两个不同的ω1-边连通点，则G的每个块都是可数的。证据通过矛盾的方式，假设B是G的不可数块。由于ω1是正则不可数基数，B中的某个顶点的度必须至少为ω1，因此，根据定理4.4，要么B有一个割点（与块的定义相矛盾），要么两个不同的顶点在B中是ω1-点连通的，因此在G中是ω1-边连通的（与假设相矛盾）。Q下面是我们的主要定理。定理4.6每个图都有一个键忠实ω-分解。证据设G是一个图，通过推论4.2，我们只需证明G有一个满足键忠实性定义的性质（i）的ω-分解。显然，我们可以考虑一个连通图G，而且我们还可以假设G是不可数的，因为否则我们可以把G作为它的唯一片段的分解。设σ是V（G）上由ω1-边连通性诱导的等价关系，即，xσy当且仅当x=y或γG（x，y）> ω.设G/σ是模σ的商图，也就是说，是由G通过识别每个σ-类的顶点而不识别任何边而得到的图。因此，G/σ可以有环和多条边。由于在E（G）和E（G/σ）之间存在一个典范双射，为了方便起见，我们假设E（G）=E（G/σ）.我们还将使用以下符号：给定G/σ的子图H，我们用H表示对应于H的G的提升子图（即， 由H的边形成的子图，被认为是G的边，连同它们的关联顶点）。根据推论4.5，G/σ的块是可数的。 备注2.2G/σ键也是如此。因为这些键也是G的键，G的一个可数键不能分离两个ω1-边连通点，它F. Laviolette /理论计算机科学中的电子笔记87（2004）205-224217G/σ的键恰好是G的可数键。设G/σ的分解是G/σ的分块分解，其分块是G/σ的分块. 很明显，图1是G/σ的一个键忠实ω-分解，但不幸的是不一定是G的一个分解，因为由G/σ的一个块的边导出的G的子图不一定是连通的。G的这种分解的存在是以下的结果：类：从G/σ的所有块的集合（Hi）i∈I中，任何一个可构造一族（Ki）i∈I是G_n的连续子群，(1) H^i<$Ki，对任意i∈I;(2) 对于任意i∈I，Ki是可数的;(3) 每个边e ∈ E（G）至多属于有限个不同的Ki's。事实上，假设这个要求是真的，很容易看出G的一个合适的ω-分解是等价关系，定义为关系Θ的传递闭包，由下式给出：eΘ eJ∈e，eJ∈ E（Ki），其中i ∈ I.证明：假设0∈I，考虑G/σ的块割点树在索引集I上的偏序≤，即，iji/=j和G/σ中连接H0的一个顶点的某条（因而也是任意一条）路到H的一个顶点，j包含Hi的一条边。(See图2为示例。）HJHiH0图二. 在这个例子中，i j。我们选择定义关于I的严格不等式，因为在Hi是循环的情况下，连接H0的顶点到Hi的顶点的G/σ的任何路径都不包含Hi的边，并且即使Hi不是循环，那么这些路径中的一些但不是全部218F. Laviolette /理论计算机科学中的电子笔记87（2004）205-224^^^^^ ^您的位置：^∈^− −^^^^ ^您的位置：^我^^ ^您的位置：^ ^您的位置：包含这样的边缘。对于每个i∈I，令L i=H j。J I由于任何i∈I只有有限个以上定义的顺序≤ i的先行者，因此任何边e E（G/σ）属于至多有限个L j，即j ≤ ie的那些边，其中ie是包含e的唯一H i的下标。显然，Li是连通的;让我们证明Li也是连通的。如果i= 0，则Li=G，它通过假设连接。如果Hi是一个循环，那么i≤-极大，这意味着Hi=Li，因此Li是连通的（实际上是一条边）。若i= 0且Hi不是环，则设qi是G/σ的唯一割点，它是Hi的边与H0的边的分界点.设G的任意两个σ-等价点x，y∈V（Li）<$V（G），如果不属于G的σ-类Qi，则它们在G中通过ω1边不交连通路径。这些路径中至多有ω条能与Qi相交，因为否则x和y将属于Qi。因此，x和y在Li中连通（实际上是ω1-边连通）。这与L i−q i连通的事实一起，意味着L iQ i（对应于L iq i的提升图）是连通的。 如果Li不连通，它的所有分支（即包含Li−Qi的分支）的顶点都在Qi中。任何这样的分量在Li中对应于qi处的环的并集。作为包含在L i中的块，这些环在H j中，j ≥ i.但是根据阶的定义，在qi处的任何循环要么是Hi本身（这被假设排除在外），要么有一个下标，和我没法比。因此，我们遇到了一个矛盾，即，i连接。不难看出（但在其余的证明中并不需要）Li然而，它们的基数可能是不可数的。为了克服这个困难，选择Li（i∈I）的生成树Ti，并定义Ki为Hi和Ti中连接Hi两个顶点的所有路径的并集。显然，Ki是Li的连通子图（因此也是G的连通子图）。 为了完成该权利要求的证明，我们表明族（ Ki ） i∈I具有要求的性质（1），（2），（3）。(1) 对于任何i ∈ I，H i<$K i平凡为真，因为H i= K0。(2) |对于任何i ∈ I，≤ ω，因为|E（H i）|其等于|which is equal to|，并且因为Ki是Hi与Ti的至多ω 2条路的并.|, and because K iis the union of H iand at mostω2paths of T i.(3) 这是因为任何边e∈E（G）都可以属于因为如前所述，e（被视为G/σ的边）可以属于至多有限个LjQF. Laviolette /理论计算机科学中的电子笔记87（2004）205-224219≤ββ定理4.6暗示了下面的明显更强的结果。TheoreM4. 7Let（Hi）i∈Ie是G的边不交的可计数子图族. 则G有一个键忠实的ω-分解，使得每个H i和G中的每个ω度的非孤立点包含在一个且仅一个G的片段中。证据设ω1是G的任意键忠实ω-分解，ω2是G的ω-分解，其碎片是Hi和e，e，J都入射到x，G中某个度≤ω点x。根据引理2.9，分解是期望QBond-faithfulω-分解提供了一种将图分裂成边不相交子图的方法，每个子图都保持 在本节中，我们将展示一个图可以 也可以被分成边不相交的子图，这些子图保持原始图的命题4.8每个图G是两个（不一定连通的）生成子图的边不交并，比如K和L，使得γK（x，y）=γL（x，y）=γG（x，y）对于G的每一对无限边连通顶点x，y.证据我们留给读者去证明这对可数图是正确的。假设G不可数。 根据定理4.6，存在一个键忠实G的ω-decompositionn=（Hi）i∈I. 既然我们都是我的亲，证明在可数的情况下，每个Hi是可数的，Hi是两本文给出了边不交子图Ki和Li，使得任意一对顶点x，y ∈ V（H i）在H i中是无限边连通的，也在bothKi和Li中是无限边连通的. LetK：=i∈IKi和L：=i∈ILi，且假设它们对于任何α≥ω，都保持α-边连通性，或者换句话说，对任意x，y∈V（G），若γG（x，y）=α，则有γK（x，y）=α和γL（x，y）=α.注意，通过对称性，我们只需证明γK（x，y）=α。取G的一组边不相交的xy-路P=（Pβ）β α，P分解为边不相交的连续子路径P1，P2，.，Pjβ 使得ββ β β• x是P1的端点，y是Pjβ的端点;220F. Laviolette /理论计算机科学中的电子笔记87（2004）205-224JβJββββ我β≥β≥≥Hiβ• 每个Pβ的端边属于同一个P β片段j+1j+2jβ• Pβ无边界Pβ无边界β-淀粉样蛋白属于β-淀粉样蛋白的一个片段，Pj的端边，对于任何j。为了完成证明，我们将证明存在K的边不相交xy-路的集合Q=（Qβ）β α，使得对于每个β α，Qβ可以被细分进入第一季度第二季度 Qjβ使得β β βJ J• Pβ和Qβ具有相同的端点;• Qβ包含在Kl中，其中Hl是包含Pj的两个端边的C1的片段。存在这样一个族Q，如果对于每个片段H i，其端边属于Hi的所有Pj的集合Pi与Ki的某个边不相交路径集合一一对应，使得每个Pj对应于具有相同端顶点的路径。因为Hi和Pi是可数的，我们只需要证明Pi中每条子路的两个端点是无限边连通的在Ki。通过矛盾的方式，假设存在P i中的某个Pj，其端点u，v满足γK（u，v）<ω，并假设j是对于存在这样一个Pj。 通过选择Ki，我们得到γ（u，v）<ω，以及所以Hi中的某个有限键B将Hi中的u和v分开。因为他是忠诚的，B也是G的一个键。此外，由于P j+1的... Pjβ与H i，它与B是边不相交的，这意味着B不仅将G中的u与v分开，而且将u与y分开。 因此，γG（u，y）<ω. 另一方面，γG（x，u）ω由j的极小性决定，因此x和y不能无限边连通在G中，矛盾。Q5图的顶点的一种特殊良序定理4.4有以下结果：定理5.1设G是一个图（可能有圈和重边），α是一个不可数正则基数. 则对G的任意α类X，[X，X] G是 基数小于α的键的并集。证据考虑G/X，通过识别X的顶点而从G获得的图，并用x表示这样获得的新顶点。如果[X，X]G包含G的基数为α的键，则G/X包含一个块，其中x的度为α，这与应用于该块的定理4.4相Q这个结果本身就很有趣，它也有一个惊人的结果，即总是可以用这种方式对图的ωF. Laviolette /理论计算机科学中的电子笔记87（2004）205-224221- 是的 .˜˜˜{∈}˜˜˜˜案例2.G是一个不可连通图. LetGbeequotient从<[1][2][3][4][5][6][7][8][9][9][10][10][11][10][11][12][在任何给定类之前的所有ω-类的并集都可以通过有限割与它分离由于总是可以将有限的ω-类集合与任何其他的ω-类分开，所以当至多有可数个ω-类时，构造这样的良序是很容易真正的问题发生在有无数个。这种良序的存在对于无限图的构造是一个非常下一个定理建立了这个结果，并将其推广到任何无限正则基数。定理5.2设W是G的所有ω-类的集合。则存在W上的良序（例如W =（[xδ]）δ< β）使得每个[x μ] ∈W可分离证据案例1. G是可数的。我们认为在这种情况下，W的任意良序（[xδ]）δβ）（其中β≤ω）都具有所需的性质。设[xµ]∈ W，对于每个δ µ，设[Aδ，Aδ]G是有限割，使得[xδ]<$V（Aδ）和[xµ]<$V（Aδ）。现在观察一下B：==Aδ，AδδG是把[xµ]和所有[xδ]<|≤ [ A δ，A δ ] G .| ≤ [A δ, A δ]G.δ µG模的图是ω-类。一般情况下，会有多个操作和多个边缘。It很清楚，V（G）上的任何良序≤Θ，使得每个x∈V（G）都可以从yV（G）：y<Θx”““当G被解释为G时，G是具有所需性质的良序。由于G中没有两个顶点是无限边连通的，并且ω1是正则的和不可数的，因此定理5.1得出G中没有块包含不可数度的顶点。所以所有的块都是可数的。 设G是G的所有块的集合。请注意，f是G的分解。固定H0∈ H并定义一个偏序≤1的双线性：H≤1K⇐⇒H=K或H=H0或G中连接H0到K的一个顶点包含H的一条边。换句话说，如在定理4.6的权利要求的证明中那样，≤1是由G的根在H 0处的block-cut点导出的偏序。我们一起去吧δ µδ µ222F. Laviolette /理论计算机科学中的电子笔记87（2004）205-224˜˜˜˜∈{∈}ט≤˜ ˜˜R是G唯一导出子图hB，它满足A∈B，A∈B，˜读者可以证明，由于这种树结构，≤1可以被定义为良序，比如≤1。对于x∈V（G），δ（x）表示G中包含x的≤λ-最小元，φ：λ→λ是上域为序数且满足H≤λK惠φ（H）≤φ（K）的内射函数，对任意H，K∈λ。 对任意H∈H\{0}，存在唯一的顶点xH∈V（H），使得δ（xH）/=H.设xH0是V（H0）的任意顶点.对于每个H∈ H，定义一个枚举数H：V（H）→V（H）的ω，使得xH是第一个元素（即：H（xH）= 0）。最后定义θ：V（G）→λ×ωx<$→（φ（δ（x）），φδ（x）（x）），其中λ ω是由卡氏积上的字典序得到的良序集。显然θ是单射的，V（G）上的良序≤Θ定义为：x≤Θy惠θ（x）≤ θ（y）。我们将证明≤Θ具有所需的分离性质。由于导出≤ Θ的词典结构和由于x H的选择，限制于任何V（H）的≤ Θ与≤ H一致。由于每个H都是可数的，根据情形1的要求，H必须具有以下性质：在命题中说。设xV（G）和S：=yV（G）：y<Θx，并通过矛盾的方式假设所有从S分离x的割都是无限的。 前一段中的注释意味着x/∈V（H0），因为否则S={y∈V（H0）;yH0x}.<设K：=δ（x）和SK：=S<$V（K）。 注意H0

下载后可阅读完整内容，剩余1页未读，立即下载