简单图的结构度量与算法应用

∪∪−∪∪可在www.sciencedirect.com在线获取理论计算机科学电子笔记319（2015）121-136www.elsevier.com/locate/entcs合成图论ApiwatChanntawibulandPawe-lSobocin'skiECS，南安普敦大学致力于R.F.C.的记忆沃特斯摘要将图分解成更简单的图是图论的核心问题之一。 研究揭示了一些深层次的概念，如模块化分解，树宽或秩宽，它们以不同的方式测量图的拓扑结构的复杂性。Courcelle和其他人已经证明，这些概念可以用来获得有效的算法，适用于分解的图族（例如，那些有界树宽度的图）。反过来，这些算法在计算机科学中也有应用，因为在计算机科学中，图形无处不在。 在本文中，我们采取了第一步理解概念分解在图论中的组成，更一般地说，在一个范畴的设置：范畴论，毕竟，是组合性的数学我们的概念引入矩阵（杯矩阵）。 像普通的矩阵一样，- 矩阵是箭头的一个道具：我们给出一个演示文稿，延长拉丰的工作，和Bonchi，Zanasi和第二作者。的变体- 矩阵，然后用于发展一种新的简单图代数，语言图论的弗兰卡。代数是一个特定的对称monoidal理论：-矩阵-类似于邻接矩阵-编码图关键词：图分解，简单图，模分解，（秩）宽，杯矩阵1介绍当范畴理论家谈论图的范畴时，他们通常指的是前层范畴Graph=Set·Set·。然而，这个图的边不是图论家通常所说的图，而是有向多重图论中最基本也是最重要的研究对象是简单图：这些图是无向的，任意两个顶点之间最多只有一条边，并且没有自环。本文主要研究简单图。图的结构度量是一种将数值（通常是自然数）分配给图的方法。 目的是让数字以某种方式表明图图论中一些著名的结构度量包括路宽、树宽、枝宽、簇宽和秩宽。树宽的概念可能是计算机科学中最著名的，通过Courcelle的工作[6]，他表明一元二阶http://dx.doi.org/10.1016/j.entcs.2015.12.0091571-0661/© 2015由Elsevier B. V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。122A. Chantawibul，P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience319（2015）121逻辑可以决定在线性时间的图族与有界树宽度。Courcelle[13]）。由于Oum和Seymour提出的结构度量秩宽，在过去的十年里一直是图论中的一个热门话题，对我们来说特别重要。我们参考[17，18]了解技术细节，这里我们给出直观的描述。一个顶点集为V的简单图的秩分解可以被认为是一棵二叉树，其中树的节点用V的非空子集标记，树的边用自然数标记，使得：• 任何树节点w的子节点w1，w2的标签（顶点集W 1，W2）是父树节点的标签（顶点集W）的（二进制）分区：即，W=W1<$W2且W1<$W2=W，• 根标记为V，• 用单元素标记叶子，• 从父节点到标记有顶点集W的子节点的树边标记有|V\W| × |W|邻接Z2-将从W到图的其余部分的边制表的矩阵。 注意，矩阵代数是在域Z2上进行的，即1 + 1 =0。特定秩分解的宽度是其最大边标签。图的秩宽度是最优秩分解的宽度：具有最小宽度的一个。离散图和团都享有1的秩宽度秩宽度和其他结构度量的概念在图论和相关领域中被证明是非常重要的。然而，有两个缺点，范畴理论可以帮助：• 一般性。如上所述，该定义专门用于简单图。然而，基本的概念是相当强大的，可以说是对其他类型的图形结构作必要的修改：多重图，有向图（双秩宽度），hypergraphs，Petri网等，这表明，基本理论应该在一个更一般的设置。• 组合性。秩分解的概念（以及其他结构度量的等效概念）在知道如何分解图G可能无助于构造具有G作为子分量的图H的分解的意义上不是固有的组合。直观地说，秩分解忘记了太多：只有秩被记录-那么，什么是一种富有成效的方法来分类处理简单的图，以一种引导我们从总体上和组成上理解结构度量的图作为对象和同态作为箭头是传统的方法，但它并不能立即产生一个图的代数Cospans是将对象转换为箭头的标准技术，并且在[9]中考虑了有向图的cospans代数，这在精神上与我们的工作接近，尽管我们没有考虑cospans。类似于Fiore和CamposA. Chantawibul，P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience319（2015）121123IJ（m1+m2）×（n1+n2）矩阵a0级0字. 如果A是一个m×n矩阵，则AT表示其我们的方法是使用对称monoidal理论，我们的意思是与发电机和方程的PROPs本文的高潮与对称monoidal理论ABUV，我们认为这是一个代数的简单的图形。矩阵代数的作用是核心：我们建立在Lafont为了理解ABUV的语义对应物，我们引入了广义矩阵代数的矩阵-矩阵（“杯”矩阵）的概念，并在一定程度上放松了普通矩阵中方向性的束缚。本文的主要技术贡献是提出了一种新的矩阵。最后，我们的结构度量，monoidal宽度，对称monoidal理论的一些意见。使用monoidal范畴的代数来建模各种系统是由R.F.C.开创的。沃尔特斯和合作者[11，12]。虽然我们在本文中不专注于应用，但我们相信我们的理论将在几个环境中相关，因为最近对称monoidal理论的应用激增：在其他作品中，我们提到信号流图[1，4]，Petri网[19论文的结构在§2中，我们回顾了矩阵的PROP的表示在§3中，我们介绍矩阵并发展它们的代数。在§4中，我们给出了一个介绍，在§5中，我们使用早期的技术发展来引入简单图的代数。符号和背景。给出一个nm1×n1矩阵A.和矩阵B，我们将A∈B，转置，一个n×m矩阵，其中AT=Aji。矩阵A是上三角矩阵，当它在主对角线下方只有0个条目，即如果i> j，则Aij = 0。PROP [14，16]是一个对称的严格monoidal范畴，它以自然数为对象，以加法为对象上的monoidal积：mn=m+n。PROP同态是对象上同一的严格对称monoidal函子：也就是说，它们在鼻子上保持对象，组合，monoidal乘积和对称性。我们保留术语对称monoidal理论的PROP是自由产生的表示：一对（E，E），其中E是一组发电机，E是一组方程（有些作者称之为关系）。2矩阵作为一种对称么半群理论本节中的结果可以在[3]中找到，基于[15]的工作固定一个环R（例如整数）;这是我们矩阵的元素的来源，为了减少下标的数量，我们在开发过程中不会显式引用它我们用r，s来表示R上的值域。定义2.1PROPMat有m×n个矩阵，如箭头n→m;合成是矩阵乘法B <$A =BA。对称是置换矩阵。124A. Chantawibul，P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience319（2015）121×定义2.2（HA）对称么半群理论HA是生成元{Δ：1 → 2，Δ：1 → 0，Δ：2→ 1，T：0 → 1}<${r：1 → 1}r∈R和图1中列出的方程上的自由PROP。在字符串图中，生成器呈现为：Δ ==T=r=定理2.3（[3，15]）HA = Mat.Q3n-矩阵矩阵在图论中很常见：例如，它是一种方便的工具以记录图（邻接矩阵）内的连通性信息。他们享有丰富和广泛使用的代数上的几个技术和结果依赖。在我们的图的范畴代数中，在§5中引入，箭头G：m→n结合了三个要素：• 一个k个顶点的简单图G• 一个m×k矩阵，• n×k矩阵。我们的想法是，这两个矩阵告诉我们G的顶点如何与其他图连接，这些图可以通过合成连接在任何一端。由于G本身可以表示为一个k×k邻接矩阵，我们处理的是三个矩阵。我们将看到，放松矩阵的3.1匝在介绍n-矩阵之前，我们首先需要一个重要的组成部分，即圈的概念--n × n矩阵的等价类，它与图论中邻接矩阵的概念密切相关：当两 个矩阵编码相同的连通性信息时（在无向设置中），它们是完全圈等价的定义3.1（圈等价，圈）我们说当K+KT=L+LT时，两个平方kk矩阵K和L是圈等价的，记为KdaL。 显然da是一个等价关系。如果K等于L，则K和L的大小相等。所谓（k-）圈是指某个k × k矩阵的da等价类。我们使用M，N在匝数范围内，给定平方K，我们用[ K ]表示诱导匝数。在某些情况下，一个转弯有一个明显的代表：上三角矩阵。引理3.2给定一个圈[K]，存在一个上三角矩阵KJ使得[K] = [KJ]。又设r，s∈R，我们有2 r = 2 s蕴涵r = s1。如果K和L是上三角方阵，且[K] =[L]，则K = L。证据 第一个主张很容易从R中的加法是阿贝尔这一事实得出例如，对于整数或任何特征不等于2的域，情况就是这样。RA. Chantawibul，P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience319（2015）121125=（id）=（id）（A1）=ID（A2）=ID（A2）=∇◦tw=∇(A3)=（Δ id）Δ =（id Δ）Δ（A4）=（id）Δ = id（A5）=twΔ = Δ（A6）==（A7）=ΔΔ T=T Δ T（A8）=Δ=（）（idtwid）（ΔΔ）（A9）T=id0（A10）Rr=r=（rr）（A11）Rr=rT=T（A12）Rr=Δr=（rr）Δ（A13）Rr=100r=100（A14）R=r+s（rs）Δ =r+s（A15）S0=0 =1000 T（A16）rs=srsr=sr（A17）1=1 =id（A18）Fig. 1. HA的方程。126A. Chantawibul，P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience319（2015）121∪组其次，如果[K] = [L]，则K+KT=L+LT。由于K和L是上三角形，它们在所有非对角项中显然一致K+KT=L+LT的第i个对角线项是2Kii=2Lii。使用关于R的附加假设，Kii=Lii。Q引理3.2中关于R的附加假设排除了R=Z2的情况，其中我们有[（1）] = [（0）]，因此第二个陈述不成立。事实上，Z2的情形对我们的应用特别重要，我们将在第5节中回到它。3.2n-矩阵一个m×n阶矩阵由一个普通的m×n阶矩阵和一个n-圈组成.定义3.3（n-矩阵）一个m × n的n-矩阵U是一个对（A，M），其中A是一个m×n的矩阵，M是一个n-圈。我们将把A称为U的基础矩阵，把M称为它的轮。我们将使用U，V来在矩阵上进行范围。事实证明，有一个非常自然的矩阵代数，它扩展了普通矩阵的代数。我们在下面展开这个代数给定一个m×n阶方阵V=（B，[L]）和n×p阶方阵U=（A，[K]），乘法，写为V U，定义为m×p矩阵：（BA，[K+AT LA]）引理3.4 λ-矩阵的乘法定义良好。证据 设K da KJ和L da LJ。我们需要K+AT LA da KJ+AT LJA。K+AT LA+（K+AT LA）T=K+KT+AT LA+AT LT A=K+KT+AT（L+LT）A=KJ+KJT+AT（LJ+LJT）A=KJ+AT LJA+（KJ+AT LJA）TQ引理3.5矩阵的乘法是结合的。证据这对于底层矩阵是正确的，因此它可以检查圈上的结合设W=（C，[M]），V=（B，[L]），U=（A，[K]）是- 定义WV和VU的矩阵。然后，它们的匝数分别是[L+BT MB]和[K+AT LA]。 故（WV）UK+AT（L+BT MB）A=K+AT LA+AT BT MBA=K+AT LA+（BA）TM（BA）这是导致W（V U）转向的矩阵。Qn×n单位矩阵是（In，[0n]），其中In是单位矩阵，0n是零矩阵.我们滥用符号，也将单位矩阵称为In。引理3.6假设U是一个m × n的矩阵。 那么I m U = U I n= U。A. Chantawibul，P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience319（2015）121127nJJk，l（1）n+InIn，[0n]）。证据 假设U =（A，[K]）。 显然，它表面上的重点转向。 Im U[K+AT0mA] = [K]的匝数。 UIn的圈数是[0n +IT KIn]=[K]。Q定义3.7（矩阵的类别，UMat）UMat具有：• 作为它的对象集合，自然数的集合，• 如从n到m的箭头所示，m × n阶矩阵。组成是矩阵乘法：UVd=ef单位矩阵UV，带有标识箭头，给定一个m1×n1的n阶矩阵U=（A，[K]）和m2×n2的n阶矩阵V=（B，[L]），它们的直和记作U<$V，是（m1+m2）×（n1+n2）的n阶矩阵（AB，[KL]）。这是很好定义的-如果K Da KJ和L Da LJ，那么显然KL Da KJLJ。直接和在UMat上产生严格的monoidal积。有一个忠实的对象上同一性幺半群函子U：Mat→UMat定义为U（A）=（A，[0n]）。我们已经看到，Mat是一个PROP（定义2.1）;事实上，UMat也是一个PROP，通过U从Mat继承了它的排列。引理3.8 Umat是一个PROP。证据它表明对称性是自然的，即下图对任意MJ×m阶矩阵U=（A，[K]）和NJ×n阶矩阵V=（B，[L]）是可交换的。m+nσm，n<$n+mUVMJ C+nσm′，n′nVUC+m在底层矩阵上，我们清楚地有σm′，n′（A<$B）=（B<$A）σm，n。通知对任意k，l∈ N，σT=σl，k。我们可以用这个来证明这些圈是一致的：不m，n（L<$K）σm，n=σn，m（L<$K）σm，n=K<$LQ事实上，函子U：Mat→UMat是一个PROP同态。我们用一个简单但有用的方法来分解矩阵来结束这一节。 通过一个纯转向，我们指的是UMat中的m→ 0型箭头，即0 ×m矩阵。通过一个无转向矩阵，我们指的是U：Mat → UMat的图像中的一个箭头，即，的一个矩阵。对于m（A，[0]）。在下面的翼，让Δn表示无转向引理3.9假设U是一个m×n的矩阵。然后U=（AP）Δn其中P是纯转弯，A是无转弯Jσ128A. Chantawibul，P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience319（2015）121→===∪◦ （id⊕ ∇) = ∪◦(id ⊕∪⊕id) ◦(Δ∪◦(id ⊕ T) = ⊥∪◦tw= ∪⊕ id2） （B1）（B2）（B3）R=R∪◦(id ⊕r) = ∪◦(r ⊕id)（B4）图二. HAU的附加方程。证据 简单计算：（A，[K]）=（（A，[0]）<$（！，[K]））Δn.Q4作为对称Monoidal理论的本节的目的是介绍UMAT，扩展§2中提到的MAT介绍。我们介绍了对称monoidal理论，HAU，假设H AU = UMat作为P ROP。定义4.1（HAU）对称么半群理论HAU是生成元{Δ：1 → 2，τ：1 → 0，τ：2→ 1，τ：0 → 1，τ：2 → 0} τ {r：1 → 1}r∈R上的自由PROP和图1中列出的方程组以及图1中列出的关于τ（发音为“杯”）的附加方程。二、 在字符串图中，.本节的主要目的是证明以下内容。定理4.2假设R满足条件2r = 2s，则r =s，对所有r，s∈R. THENH AU = UMat。本节的其余部分由上述结果的证明组成;因此，我们假设R满足本节其余部分的必要条件。我们首先递归地定义一个PROP态射Θ：HAUUmatΔ<$−→..1，[（0）]<$−→. .11分钟00−→。！，J.01ΣΣΣ10 0 0 0›−→（！，[（0）]）T <$−→（<$，[（）]）请注意，我们是有点草率的符号，因为我们表示！所有独特的箭头到0和由…所有独特的箭头从0在材料。因为我们定义的是一个对称的monoidal函子，所以递归是强A. Chantawibul，P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience319（2015）121129制的，例如：Θ（q<$p）= Θ（q）<$Θ（p）Θ（p<$q）= Θ（p）<$Θ（q）130A. Chantawibul，P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience319（2015）121∼IJ这个过程是很好定义的：因为HAU和UMat都是对称的monoidal，它表明HAU中的所有方程在UMat中也成立。 这是HA和Mat的情况（如[ 3 ]中所示）-它可以检查涉及Δ的方程。引理4.3（i）（Θ）（θid）=（θ）（idθid）（id2θΔ）(ii) （θ）（idθT）= θ(iii) （θ）（Θtw）=θ(iv) （θ）Θ（id r）=（Θ）Θ（r id）。证据简 单的计算。Q引理4.4下图是对易图。下口Φ Θ（一）C c¸MatU Umat证据由于该图由PROP同态组成，因此可以验证HA的生成元也是如此。Q上述观察使我们能够得出结论，HAU相对于HA中的方程是保守的。引理4.5假设t，u∈HA. 那么t = HAuit = HAUu。证据“只有当”的方向是显而易见的。 至于“如果”，请注意，gram（1），Φ是同构，U是忠实的，所以它们的合成是忠实的.因为图是对易的，所以同态HA→HAU是忠实的。Q由于Θ是对象上的恒等式，为了表明它是同构，它表面上表明它是完整的和忠实的。第4.6章满了证据设U =（A，[K]）是一个m×n阶矩阵.我们必须构造HAU的项t U，使得Θ（tU）= U。使用引理3.9的因式分解，我们有U=（（A，[0n]）<$（！，[K]））Δn.我们可以把这个问题分成两部分：构造t A：n→m使得Θ（t A）=（A，[0 n]）和t K：n→n使得Θ（t K）=（idn，[K]）。 由于HA = Mat，因此可以直接获得t A。我们只剩下（！，[K]），其中w.l.o.g.我们假设K是上三角形。问题变成：给定一个上三角形n×n K，构造一个关于tK的项，使得Θ（tK）=（idn，[K]）。我们可以通过在HAU中构造两个项来做到这一点：• 给定p q≤n，有一项p，q：n→n，满足，对任意（B，[L]）Θ（inc）（B，[L]）=（B，[LJ]），其中LJ=.Lij+ 1 ifi=p且j=qp，qLij否则，请执行以下操作。A. Chantawibul，P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience319（2015）121131.ΔpIJ• 给定p≤n，包括i：n→n，满足，Θ（inc）（B，[L]）=（B，[L，J]），其中L，J=.Lij+ 1ifi=j=p为了简单起见，我们只给出下面合适的字符串图，让读者验证Θ（incp，q）和Θ（incp）是否如广告所宣传的那样工作.p.pQ..Incp，q Incp然后，很明显，tK可以通过这两个项族的适当组合来构造，最后与nn组合得到tK。 Q证明Θ是忠实的要稍微复杂一些。我们首先展示如何轮流引理4.7=引理4.8=证明的关键是HAU中纯圈表示的某种基本上，人们可以不使用T或T来写任何这样的术语。引理4.9假设在HAU中t：k→ 0。那么t可以写成ttΔ，其中tΔ仅使用生成器Δ、，t仅使用生成器。证据 我们使用一个重写参数：以一个字符串图表表示开始-站T。 接下来，我们可以写t=t1<$t1，其中t1并不使用数据流生成器11阿哈哈并且只控制发电机。 现在，tHA可以以矩阵形式放置（参见[3]）：位置t1∇ ◦ t1 所有的comm结构都在么半群结构之前。以下是我们将应用的重写规则⇒ ⇒俄.西R+sRSR+sLij否则，请执行以下操作。132A. Chantawibul，P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience319（2015）121...k+1k +1k+1∼⇒ ⇒在每一点上获得步长tktktk+1tJ不知道结果在哪里∪HA∪J哈哈哈哈从HA中分离出来。唯一棘手的问题是证明终止性：我们可以使用幺半群深度的概念来证明它。 给定一项tHA：k→l，我们令右端口的幺半群深度1，l通过一圈连接，前两个重写规则中的每一个都减少了k端口的幺半群深度，并增加了另一个深度为l的端口。最后两个规则只是删除乘法深度为0的端口（换句话说，从矩阵中删除零行）。通过总是在具有最高幺半群深度的端口处重写，并取消任何深度为0的端口，显然最终得到具有幺半群深度为1的所有端口的项Q引理4.10（转矩阵形式）任何t：k→0都可以写成以下形式：2016 - 05 -2500：00：00ri，j）Δk+11≤i≤k1≤j≤k+11≤i≤k其中，当j=k+1或i > j时，ri，j = 1，并且通过连接来构造k：k（k+ 1）→0，对于每个1≤i≤k：• 第（i-1）（k+1）+i个端口和第（（i-1）（k+1）+k+1）个端口，以及• 对于每个j> i，第（i-1）（k+ 1）+j个端口与第（j-1）（k+ 1）+i个端口杯子。可以给出一个递归定义，但它没有启发性：下面的图表更好地说明了Brack的结构。k+1{k+1{k+1{.设K是上三角矩阵，其中j，第i个元素ri j，当i ≤ j时，否则为0。则Θ（t）=（！，[K]）。证据 使用引理4.9的过程，我们可以将任何项k → 0写成以下形式：t≠tΔ，然后使用引理4.8和4.7的等式将系数相加。 QA. Chantawibul，P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience319（2015）1211330011年。⎝⎠⎛⎞例4.11的转弯矩阵形式计算如下：=在那里我们没有画出零系数转弯。很容易检查，这给出了上三角矩阵0 0 110 0 0 00 0 0 0命题4.12 Θ是可信的。证据设t，u：n→m使得Θ（t）= Θ（u）。利用HA定律，我们可以写出t=（tHA<$tJ）<$Δn和u=（uHA<$uJ）<$Δn，其中tHA，uHA：n→m和tJ，uJ：n→0。现在Θ（Δn）是单声道的，因此Θ（t）= Θ（u）意味着Θ（tHA<$tJ）= Θ（uHA<$uJ）。通过UMAT中的直接和定义，我们有Θ（tHA）= Θ（uHA）Θ（tJ）= Θ（uJ）由于HA= Mat且U：Mat→UMat是忠实的，我们得到HA=uHA。本文旨在表明，Θ（t，J）= Θ（u，J）意味着t，J= u，J。将tJ和uJ变换为旋转矩阵形式。自从（！，[K]）= Θ（tJ）= Θ（uJ）=（！，[L]），则必须有[K] = [L]。因为K和L是上三角形，所以引理3.2的结论得出K=L。因此tJ=uJ。Q我们已经证明了在命题4.6中Θ是满的，并且在命题4.12中它是忠实的。这就完成了定理4.2的证明所需的要素。5简单图的合成理论：ABUV在本节中，我们将重点讨论R=Z2的情况.我们给出了一个演示UMATZ2，并展示了如何使用它来获得一个简单的图代数5.1Z~ 2上的n-矩阵定义5.1（AB和ABU）对称幺半群理论AB是生成元{Δ：1→ 2，Δ：1→ 0，Δ：2→ 1，T：0→ 1}上的自由PROP，并且2134A. Chantawibul，P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience319（2015）121为∇◦Δ =T◦⊥(C1)=（C2）图三. ABU和ABUV特有的方程。式（A1）-（A10）在图1中列出1和（C1）在图。3 .第三章。对称幺半群理论ABU是生成元{Δ：1 → 2，T：1 → 0，T：2 → 1，T：0 →1，T：2 → 0}上的自由PROP，AB的方程，图1的方程（B1）-（B3）. 2和（C2）在图。3 .第三章。第一次回忆[2，15]thatAB=MatZ2。从逻辑上讲，UMatZ2的存在比一般情况更简单1 + 1 = 0由图中的“反可分”定律-方程（C1）捕获3[2]。方程（C2）似乎令人惊讶，因为它在一般情况下不成立。事实上，在简单图中“无自循环”的要求引理5.2Θ（πΔ）= Θ（T）证据 对于Z2-矩阵，我们有（0）da（1），所以[（0）]=[（1）]。Q定理5.3ABU = UMa tZ2.证据沿着定理4.2的证明路线进行：唯一的区别是，我们使用对角线为0的上三角矩阵，而不是使用上三角矩阵作为圈的代表。 我们省略细节。Q5.2简单图本文利用ABU（λ=UmatZ2）理论，给出了一个简单图的邻接代数。唯一缺少的是顶点。定义5.4（ABUV）对称么半群理论ABUV是生成元{Δ：1 → 2，λ：1 → 0，λ：2→ 1，T：0 → 1，λ：2 → 0，v：0 → 1}上的自由PROP，以及ABU的方程。 在字符串图中，我们将绘制v：0 → 1如下：由于没有涉及v的额外方程，ABUV是ABU和生成元v上的自由PROP的余积（在PROP范畴中），没有方程。定义5.5令CGn为具有箭头n→m对（k，U）的2-PROP，其中• k∈N且• U是一个m×（n + k）的n-矩阵。A. Chantawibul，P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience319（2015）121135不n组合物（V，l）n（U，k）为（k+1，V（U1<$Ik））对于2-胞腔，给定一个双射σ：k→k，设I σ表示由σ导出的置换矩阵。则σ：（U，k）<$（UJ，k）：n→m是2-胞腔，如果UJ（I n<$I σ）= U。请注意，所有112-cel都是可逆的。 表示通过识别CG中的同构1-胞腔而获得的c。定理5.6ABUVh= CGrap h=.证据 省略Q推论5.7ABUV [0，0]与简单图（的同构类）之间存在1-1对应.证据一个k阶简单图G可以用一个上三角k×kZ2矩阵MG来标识，其中0在其对角邻接矩阵上。当存在双射σ：k→KJS.T.时，两个简单图G，GJ MG′=Iσ MG Iσ。因此，这个命题直接由定理5.6推出。Q最后，我们总结了一个说明性的，但简单的例子，如何代数ABUV可以用来分解图。众所周知，团具有无限的树宽，但从秩宽的角度来看非常简单：它们的秩宽为1。这很容易观察到：假设{V1，V2}是一个团的顶点集V的任何划分。则|V2| × |V1|描述V1的顶点如何连接到V2的顶点的邻接矩阵是每个元素为1的矩阵，并且该矩阵的秩为1。集团在ABUV中也有一个非常简单的描述，如下所示例5.8[团]n个顶点上的团可以构造如下⊥◦c◦T其中c是以下项：.在这里，我们不定义“简单性”，它是用一个称为monoidal宽度的结构度量来衡量的;它将在本文的续集中介绍。 那个...其思想如下：monoidal分解仅仅是一个二叉树，其内部节点标记为“”或“”，并留下生成元、恒等式和扭曲。与绑定到最大对象的分解相关联的宽度，136A. Chantawibul，P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience319（2015）121当将树作为环境对称monoidal理论的项进行评估时，项的Monoidal宽度则是最优分解的宽度，即，宽度最小正如我们将在续集中展示的那样，ABUV中的monoidal宽度与秩宽度密切相关，并且通过限制ABUV的子PROPs，可以以类似的自然方式来表征树宽度等概念。还要注意的是，monoidal宽度的定义与ABUV无关，在任何monoidal理论中都有意义，这解决了引言中概述的一般性问题我们声称(i) ABUV是一个典型的，简单的图组成代数，和（ii）monoidal宽度是一个强大的概念，我们相信将是有用的在一些不同的应用领域[1，4，7，10，19] monoidal理论被使用。引用[1] F. 你好，P。 因此，博钦斯基和F。扎纳西 信号流图的范畴语义。 在CONCUR'14，2014。[2] F. 你好，P。 因此，博钦斯基和F。扎纳西互作用双代数是Fro benius。 在FOSSaCS'14 ， LNCS 的 第8412 卷，第351-365 页中。Springer，2014.[3] F. 你好，P。 因此，博钦斯基和F。扎纳西相互作用的Hopf代数。 意见书d，可于http：//arxiv. org/abs/1403。 7048，2014年。[4] F. 你好，P。 因此，博钦斯基和F。扎纳西信号流图的完全抽象。在编程语言的原则，POPL'15。，2015年。[5] B. Coecke和R.邓肯相互作用的量子观测。在ICALP[6] B. Courcelle和J. Engelfriet。图结构和一元二阶逻辑-语言理论方法。数学及其应用百科全书第138CUP，2012年。[7] R.邓肯基于测量的量子计算的图形方法。 量子物理学和语言学：一个组成，图解话语，第3章。牛津大学出版社，2013年。[8] M. P. Fiore和M. D.坎波斯有向无环图的代数。在计算，逻辑，游戏和量子基础。Samson Abramsky的许多方面，LNCS的第7860卷，2013年。[9] F. Gadducci和R.海克尔图变换的归纳观点。在最近的趋势在代数发展技术，卷1376LNCS。Springer，1998年。[10] D. R.吉卡延迟不敏感异步电路的图解推理。在计算，逻辑，游戏和量子基础。Samson Abramsky的许多方面，第52-68页。Springer，2013.[11] P. Katis，N.Sabadini和R.F. C. 沃特斯过程的两个类别 J. 纯应用 代数，115：141- 178，1997年。[12] P. Katis，N. Sabadini和R. F. C.沃特斯Span（Graph）：一个转换系统的代数。在AlgeopathologyMethodology and Software Technology （ AMAST '97 ） ， LNCS 的 第 1349 卷 ， 第 322-336 页 中 。Springer，1997年。[13] S. La Torre和G. Parlato.作用域有界的多栈下推系统：定点、序列化和树宽。在FSTTCS 2012，2012。[14] S. 缺乏。组成道具。Theor App Categories，13（9）：147[15] Y. 拉丰布尔电路的代数理论J Pure Appl Alg，184：257[16] S. 麦克·莱恩范畴代数Bull Amer Math Soc，71：40[17] S.- I.嗯。有界秩宽的图。博士论文，普林斯顿，2005年。[18] S.- I.乌姆和P·西摩。近似枝宽和枝宽。Journal of Combinatorial Theory，Series B，96（4）：514A. Chantawibul，P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience319（2015）121137[19] J. Rath ke，P. 所以，波辛斯基和O。 斯蒂芬斯 Petri网中的计算能力。在可重复性问题中，LNCS 的第8762卷，第230-243页。Springer，2014.[20] P. 所以，波奇因斯基。Petri网交互的表示。一致性理论（CONCUR'10 ），LNCS 中的第6269号，第554-568 页。Springer，2010.[21] P. 所以波辛斯基。网络、关系和连接图。在计算机科学中的代数和代数（CALCO '13 ），LNCS 的第8089卷，第282-298 页，2013 年。