Coverings of Bipartite Graphs
Coverings of Bipartite Graphs
复制标题
DOI：
10.4153/cjm-1958-052-0
复制
发表时间：
1958
期刊：
影响因子：
--
通讯作者：
A. Dulmage;N. S. Mendelsohn
中科院分区：
文献类型：
--
作者：
A. Dulmage;N. S. Mendelsohn
为了分析二部图（以下简称图），引入了外覆盖的概念。根据这个概念，可以自然地将任何图分解为两部分，一个不可接受的部分和一个核心。也可以将核心分解为不可约的部分，从而获得图的规范约化。不可约性的概念很容易和自然地用外部覆盖来表达。图的不可接受边的作用是阻碍图的某些自然覆盖。
For the purpose of analysing bipartite graphs (hereinafter called simply graphs) the concept of an exterior covering is introduced. In terms of this concept it is possible in a natural way to decompose any graph into two parts, an inadmissible part and a core. It is also possible to decompose the core into irreducible parts and thus obtain a canonical reduction of the graph. The concept of irreducibility is very easily and naturally expressed in terms of exterior coverings. The role of the inadmissible edges of a graph is to obstruct certain natural coverings of the graph.