论文标题
双方移植物的紧密切割I：资本距离组件
Tight Cuts in Bipartite Grafts I: Capital Distance Components
论文作者
论文摘要
本文是一系列论文中的第一篇论文，这些论文提供了$ t $ cuts in两部分图的最大包装的特征。给定连接的图，一组$ t $偶数的顶点和最小$ t $ -join，可以定义边缘权重，可以从该距离定义顶点之间的距离。此外，给定指定的顶点称为root，可以根据其距离根的距离进行分类，并且该顶点的这种分类可用于定义一个称为{\ em距离组件}的子图系列。 Sebö提供了一个定理，该定理揭示了距离组件，最低$ t $ -joins和$ t $ cuts之间的关系。在本文中，我们进一步研究了两分图中距离分量的结构。特别是，我们专注于{\ em Capital}距离组件，即包含根的距离。我们根据Kotzig-Lovász将军的规范分解的$ T $ JOIN类似物揭示了资本距离组件的结构。
This paper is the first from a series of papers that provide a characterization of maximum packings of $T$-cuts in bipartite graphs. Given a connected graph, a set $T$ of an even number of vertices, and a minimum $T$-join, an edge weighting can be defined, from which distances between vertices can be defined. Furthermore, given a specified vertex called root, vertices can be classified according to their distances from the root, and this classification of vertices can be used to define a family of subgraphs called {\em distance components}. Sebö provided a theorem that revealed a relationship between distance components, minimum $T$-joins, and $T$-cuts. In this paper, we further investigate the structure of distance components in bipartite graphs. Particularly, we focus on {\em capital} distance components, that is, those that include the root. We reveal the structure of capital distance components in terms of the $T$-join analogue of the general Kotzig-Lovász canonical decomposition.
