论文标题
关于在混合图中与$ B $分支中匹配森林相匹配的公平分区的注释
Notes on Equitable Partitions into Matching Forests in Mixed Graphs and into $b$-branchings in Digraphs
论文作者
论文摘要
分支中的分支的公平分区是将弧设置为分支中的分区，以使任何两个分支的大小最大都不同。对于可以将其弧形集分为$ k $分支的Digraph，总是将公平的分区存在于$ K $分支中。在本文中，我们将公平分区的两种扩展分解为挖掘物中的分支：混合图中匹配森林的分支；并进入$ b $ digraphs的分支。对于匹配的森林，基拉利（Király）和洋子（2022）（2022）认为基于匹配森林的大小以及其中的匹配和分支的三个刻度公平性。与此相反，我们基于覆盖的顶点的数量引入了单一准则公平性，鉴于匹配森林的三角洲 - 皇家结构，这是合理的。尽管这种公平分区的存在可以来自基拉利和洋子的引理，但我们提出了其直接，更简单的证据。对于$ b $ - 分支机构，我们根据$ b $分支的大小和所有顶点的居民定义一个公平性概念，并证明始终存在公平分区。然后，我们得出相关多型的整数分解属性。
An equitable partition into branchings in a digraph is a partition of the arc set into branchings such that the sizes of any two branchings differ at most by one. For a digraph whose arc set can be partitioned into $k$ branchings, there always exists an equitable partition into $k$ branchings. In this paper, we present two extensions of equitable partitions into branchings in digraphs: those into matching forests in mixed graphs; and into $b$-branchings in digraphs. For matching forests, Király and Yokoi (2022) considered a tricriteria equitability based on the sizes of the matching forest, and the matching and branching therein. In contrast to this, we introduce a single-criterion equitability based on the number of covered vertices, which is plausible in the light of the delta-matroid structure of matching forests. While the existence of this equitable partition can be derived from a lemma in Király and Yokoi, we present its direct and simpler proof. For $b$-branchings, we define an equitability notion based on the size of the $b$-branching and the indegrees of all vertices, and prove that an equitable partition always exists. We then derive the integer decomposition property of the associated polytopes.
