Notes on equitable partitions into matching forests in mixed graphs and b-branchings in digraphs
Notes on equitable partitions into matching forests in mixed graphs and b-branchings in digraphs
复制标题
关于混合图中的匹配森林和有向图中的 b 分支的公平划分的注释
DOI：
10.1007/978-3-030-53262-8_18
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Kenjiro Takazawa
中科院分区：
文献类型：
--
作者：
Nicolas Bousquet;Takehiro Ito;Yusuke Kobayashi;Haruka Mizuta;Paul Ouvrard;Akira Suzuki and Kunihiro Wasa;Kenjiro Takazawa
有向图中分支的平均划分是弧集到分支的划分，使得任意两个分支的大小至多相差一。对于一个弧集可以分成分支的有向图，总是存在一个到分支的公平划分。在这篇文章中，我们给出了有向图中等分枝的两个推广：混合图中的匹配林和有向图中的Intob-分支。对于匹配林，Király和Yokoi(2018)根据匹配林的大小及其匹配和分枝考虑了三标准均衡性。与此不同的是，我们引入了一个基于覆盖顶点数量的单准则均衡性。Forb-分支，我们基于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 intokbranchings, there always exists an equitable partition intokbranchings. In this paper, we present two extensions of equitable partitions into branchings in digraphs: those into matching forests in mixed graphs; and intob-branchings in digraphs. For matching forests, Király and Yokoi (2018) 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 the covered vertices. Forb-branchings, we define an equitability based on the size of theb-branching and the indegrees of all vertices. For both matching forests andb-branchings, we prove that equitable partitions always exist.