Connectivity and Reducibility of Graphs
Connectivity and Reducibility of Graphs
复制标题
图的连通性和可归约性
DOI：
10.4153/cjm-1962-044-0
复制
发表时间：
1962
期刊：
影响因子：
--
通讯作者：
N. S. Mendelsohn
中科院分区：
文献类型：
--
作者：
Diane M. Johnson;A. Dulmage;N. S. Mendelsohn
对应于每一个图，二部图，或有向二部图，存在一个有向图，当且仅当原始图是连通的。本文证明了对任何有向图，都存在某个二部图，使得该有向图连通当且仅当该二部图不可约。建立了约简和连通性之间的其他联系。
Corresponding to every graph, bipartite graph, or directed bipartite graph there exists a directed graph which is connected if and only if the original graph is connected. In this paper, it is shown that for every directed graph there exists a certain bipartite graph such that the directed graph is connected if and only if the bipartite graph is irreducible. Other connections between reducibility and connectivity are established.