循环矩阵论证及其在集合填充和覆盖问题中的应用

可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）147-158www.elsevier.com/locate/entcs巡回和巡回未成年人Silvia Bianchi西尔维娅·比安奇，1，2 Graciela Nasini，1，3Paola Tolomei保拉·托洛梅1，3Dep artamentodeMatem'atica-ECENFCEIA-罗萨里奥国立大学CONICET阿根廷罗萨里奥Luis Torres路易斯·托雷斯1，4CentrodeModelizaci'onMatem'atica-ModeMatEscuelaPolit'ecnicaNacional厄瓜多尔基多摘要循环收缩子式对于用极小非理想结构刻画理想循环矩阵起着关键作用。本文证明了循环矩阵A具有循环压缩子式的充要条件，即A在有向图中具有循环压缩子式。在特定的情况下，当A本身是一个循环矩阵，我们的结果提供了一个替代的表征以前已知的文献。保留字：循环矩阵，循环子式，回路，理想性。1介绍给定集合E={1，2，...，n}和E的子集族F，F的填充或覆盖被定义为集合S ∈ E，该集合S ∈E分别与F的每个成员至多或至少在一个元素中相交。如果E的每个元素都有一个权重，那么集合包装问题（SPP）要求找到一个最大权重的包装，而集合覆盖问题（SCP）要求找到一个最小权重的覆盖。组合学和图论中的许多问题都可以用公式表示为集合填充或集合覆盖问题。1本研究部分由EPN PIJ-16-06，ANPCyT PICT-2016-0410和PID-UNR ING 538资助。2电子邮件地址：sbianchi@fceia.unr.edu.ar3电子邮件：{nasini，ptolomei}@ fceia.unr.edu.ar4电子邮件：luis. epn.edu.echttps://doi.org/10.1016/j.entcs.2019.08.0141571-0661/© 2019作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。148S. Bianchi等人/理论计算机科学电子笔记346（2019）147+这两个问题一般都是NP难的。一个共同的方法，他们的研究包括制定他们作为整数线性规划。 设M（F）是一个0， 1-矩阵，其行是F中成员的关联向量，w∈Zn.那么问题可以公式化为：(SPP)max{wT x：M（F）x≤1，x∈{0， 1}n}(SCP)min{wT x：M（F）x≥1，x∈ {0， 1}n}，其中1∈Zm是所有元素都等于1的向量。尽管这两个问题看起来很相似，但人们指出，它们在集合包装问题已经被证明是等价于最大权重稳定集合问题（参见，例如，[4]的第2.4.1节），这种等价性可用于获得表征、加强公式和设计求解算法。相比之下，集合覆盖问题似乎没有一个等价的表示作为一个图优化问题，即使覆盖在制定几个重要的图形问题，如连通性，着色，和控制集，引用一些例子中发挥了重要作用。因此，集合覆盖问题的研究远远少于集合包装问题。一个重要的问题是刻画这样的族F，其中整数规划公式SPP和SCP是完美公式，即，线性系统M（F）x≤1，0≤x≤1和M（F）x≥1，0≤x≤1给出了相应问题所有可行解的凸包的完全线性描述。lems。这个问题在[3]中对于集合包装的情况使用来自（弱）完美图定理的结果解决了：公式SPP是完美公式当且仅当F是完美图的极大团族。因此，完美图的最大顶点关联矩阵称为完美矩阵。另一方面，SCP是集合覆盖问题的完美公式的0，1-矩阵M（F）被称为理想矩阵，但它们尚未被完全刻画。完美性是图的一个遗传性质，它意味着完美图的任何顶点类似地，理想性可以被证明是矩阵的性质，其被转移到矩阵的子式。在第一种情况下，这种观察导致了完美图的特征在于最小非完美子图。极小非理想矩阵的相应刻画然而，已经获得了几个结果，为特定类别的矩阵。Cornu′ejols和Novick[5]刻画了所有理想和极小非理想循环矩阵.给定循环矩阵的循环子式在这种刻画中起着重要的这一事实促使提交人研究这种未成年人存在的条件。他们提供了一个充分的条件，即在与矩阵相关的特定有向图中存在一个简单的有向回路。后来，Aguilera[1]推广了这个结果，得到了必要和充分的结果。S. Bianchi等人/理论计算机科学电子笔记346（2019）147149≈×在同一个辅助有向图中存在一族不相交有向回路的条件。循环矩阵是循环矩阵的推广。Eisenbrand等人[6]得到了当M（F）是循环矩阵时SPP的完美公式在这个公式中所涉及的不等式与矩阵相关的另一个辅助有向图中的有向回路有关。最近，我们得到了SCP的完美公式[2]。再一次，有向回路与线性描述中出现的不等式有关。此外，这些有向回路诱导循环矩阵的循环子式。因此，非理想循环子式是循环矩阵理想性的最小禁止结构在同样的工作中，我们还提出了循环矩阵的一个必要条件有一个循环辅修。在本文中，我们进一步发展了这一结果。这一贡献的主要结果在定理4.7中陈述，其中我们根据其相关联的有向图中的有向回路完全当仅限于循环矩阵的子类时，我们的结果给出了循环子式的另一种刻画，而不是[1]中给出的刻画。2注释和初步结果对于n∈N，[n]表示定义在集合{1，.，n}，具有整数加法模n。给定a，b∈[n]，设b−a是满足a+t=b modn的最小非负整数t。我们用[a，b]n表示由集合{a+s：0≤s≤b−a}定义的循环区间。类似地，（a，b）n、[a，b）n和（a，b）n分别对应于[a，b]n\{a}、[a，b]n\{b}和d[a，b]n\{a，b}。除非另有说明，在本文中，A表示{0， 1}-矩阵的阶m n。此外，我们考虑列（resp.行）的索引[2019 - 01 - 19 00：00：00][2019 - 01：00][m]）。 两个矩阵A和AJ是同构的，记为A AJ，如果通过行和列的排列，可以从A得到AJ在本文的上下文中，矩阵A称为循环矩阵，如果对于每一行i ∈ [m]，存在两个不同的整数li，ui∈ [n]，使得A的第i行是集合[li，ui]n的关联向量. 若f，对任意i∈[m]，y，1≤liui≤n成立，则A是区间矩阵.因此，区间矩阵是循环矩阵的一种特殊情况;已经证明它们是理想的。如果集合[lj，uj]n<$[li，ui]n，则称循环矩阵A的行i支配A的行j i = i。更进一步说，如果一条路支配另一条路，那么它就是支配的。在下文中，我们将注意力限制在没有支配行和没有零行或零列的矩阵150S. Bianchi等人/理论计算机科学电子笔记346（2019）147⎜⎜⎟⎟⎛⎜⎞⎟⎜⎜⎝⎟⎟nn⊂n下面是一个6× 12循环矩阵的例子。1 1 1 1 1 0 0 0 0 0 0 00 1 1 1 1 1 1 1 0 0 0 0A=0 0 0 1 1 1 1 1 0 0 00 0 0 0 0 0 1 1 1 1 0 00 0 0 0 0 0 0 0 0 1 1 11 1 0 0 0 0 0 0 0 0 0 1⎠（一）n阶的正方形循环矩阵称为循环矩阵。注意，在这种情况下，集合[li，ui]n必须具有相同的基数y，sayk，对于所有i∈[n]，k≥2。这样的矩阵将由Ck和w.l.o.g.表示。我们可以假定，对于每个i∈[n]，Ck的第i行是集合[i，i+k）n的关联向量。给定N[n]，通过N的收缩获得的A的子矩阵，记为A/N，是A的子矩阵，该子矩阵是在去除N中索引的所有列之后得到的，并且都是占优势的行。此外，通过删除N获得的A的子矩阵是在删除索引为N的所有列和索引为N的某列中条目等于1的所有行之后得到的A的子矩阵。 由此不难看出，用消去法得到的循环矩阵的每一个真子式都是区间矩阵，因而它是理想的。由于我们对循环矩阵的非理想子式感兴趣，因此在本文中我们只关注通过收缩获得的子式，并将其简单地称为子式。此外，矩阵A的子式被称为循环子式，如果它同构于循环矩阵。循环矩阵的循环子式在特定的有向图中以圈的形式事实上，给定一个循环矩阵Ck，作者在[5]中定义了一个有向辅助图G（Ck），其中[n]为其n n对于每个i∈[n]，形式为（i，i+k）和（i，i+k+1）的顶点和弧的集合，即，所有弧的长度分别为k和k+1。他们证明，如果N[n]诱导一个G（Ck）中的简单回路，则矩阵Ck/N同构于循环子式。n nAguilera[1]在随后的工作中证明了Ck/N同构于循环Ck的子式当且仅当N在G（Ck）中导出一族不相交的简单回路n n每个具有相同数量的长度为k的弧和相同数量的弧长度为k+1。研究循环矩阵的集合覆盖问题[2]，我们找到了循环矩阵有循环子式的一个充分条件，该条件也用与该矩阵相关的以下有向图中的圈定义2.1[2]给定一个循环矩阵A，设F（A）是一个有向图，其顶点集为[n]，其弧的形式为（li−1，ui），对于每个i∈[m]（称为行弧）和（j，j−1），（j−1，j），其中j∈[n]（分别称为反向短弧和前向短弧我们说F（A）中的一条行弧（u，v）跳过一个顶点j∈[n]，如果j∈（u，v）n.S. Bianchi等人/理论计算机科学电子笔记346（2019）147151112211 3958⊗⊗67此外，唯一的前锋（resp。反向）跨越j的短弧是弧（j-1，j）（resp.（j，j-1））。给定F（A）的行弧a=（u，v），a的长度，用l（a）表示，等于v−u。 如果a是一个短弧，那么l（a）= 1，如果它是一个向前的弧，l（a）=-1，如果它是一个反弧。定义了F（A）中有向回路Γ的绕数p（Γ）通过（a）p（Γ）=a∈E（Γ） ，n其中E（r）表示r的弧的集合F（A）中的任何圈Γ诱导F（A）的顶点划分为以下三类：(i)圆<$（Γ）：={j∈[n]：（j−1，j）∈E（Γ）}，(ii)交叉点（r）：={j∈[n]：（j，j−1）∈E（r）}，以及(iii) bullets·（r）：=[n]\（n（r）n（r））。图1示出了（1）中矩阵A的有向图F（A）为了说明，电路r：={ 2， 3， 4，9， 12， 1， 8， 7， 6， 10， 11， 2}用粗线表示。它有五排弧和绕组数2。而且导出了F（A）的顶点的如下划分：（Γ）={ 1， 3， 4， 11}，（Γ）={7， 8}和·（r）={ 2， 5， 6， 9， 10， 12}。10 4图1.一、辅助有向图F（A）与一个圈Γ.观察这个圆圈（相应地）。十字）顶点是头（分别为前（forward），后（forward）。 逆）的短弧。 一个项目符号顶点要么是一个在Γ之外的顶点，要么它是行弧的尾部或头部。 我们说子弹是必要的子弹，它由r达到。在图1中，除了顶点5之外，·（Γ）中的所有顶点都是基本项目符号。下面我们用p表示环的绕数，并假定环有若干个本质子弹{bj：j∈[s]}，其中h1≤b1

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