Let be a bidirected multigraph with signing , let be a set of vertices in , and let be a non-negative integer. For any pair of vertex sets satisfying , we denote by the multigraph with the same vertex set as and with edge set consisting of those edges of each of whose endvertices satisfies or , or , . We prove that admits a set of pairwise disjoint -paths if and only if for any with , the inequality holds where the sum is indexed by the components of . This result is a generalization of a result of Gallai from undirected graphs to bidirected ones. Furthermore, we will deduce from this a kind of an Erdős-Pósa property for -paths in bidirected multigraphs.

生成讲解博客的中文版本

生成AI智能校验的中文版本