论文标题
关键图的双向类似物的建设性表征I：径向和半质体的主要类别
Constructive Characterization for Bidirected Analogue of Critical Graphs I: Principal Classes of Radials and Semiradials
论文作者
论文摘要
本文是第一个来自串行纸，为被称为radials和半偏移量的双向图提供了建设性特征。在本文中，我们为五个原则类别的径向和半质体提供了建设性的特征，用于表征一般的径向和半偏径。双向图是一个图形，其中每个边缘的每个端都有一个符号$+$或$ - $。双向图是Digraphs和签名图的常见概括。我们将径向的新概念定义为匹配理论中的经典概念的概括，即关键图。径向也是一类被称为流程图的挖掘物的概括。我们还定义了半径，这是放松的径向概念。我们进一步定义了径向和半质体的特殊类别，即绝对半ial，强大而几乎强的径向，线性半毛和sublinear radials。我们为这五类的双向图提供了建设性的特征。我们的串行论文是一系列作品的一部分，这些作品建立了针对双向图的强组件分解。
This paper is the first from serial papers that provide constructive characterizations for classes of bidirected graphs known as radials and semiradials. In this paper, we provide constructive characterizations for five principle classes of radials and semiradials to be used for characterizing general radials and semiradials. A bidirected graph is a graph in which each end of each edge has a sign $+$ or $-$. Bidirected graphs are a common generalization of digraphs and signed graphs. We define a new concept of radials as a generalization of a classical concept in matching theory, critical graphs. Radials are also a generalization of a class of digraphs known as flowgraphs. We also define semiradials, which are a relaxed concept of radials. We further define special classes of radials and semiradials, that is, absolute semiradials, strong and almost strong radials, linear semiradials, and sublinear radials. We provide constructive characterizations for these five classes of bidirected graphs. Our serial papers are a part of a series of works that establish the strong component decomposition for bidirected graphs.
