欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
没有完美匹配的二部图G,若给它任意增加一条新的边,结果得到的二部图有完美匹配,则称图G是饱和的.设X包含于V（G）,Γ（X）表示V（G）中与X中至少一个顶点相邻的所有顶点组成的集合.本文证明了一个二部图G=（U,W）是饱和的当且仅当（a）存在唯一X包含于U,使得X〉Γ（X）,X-1〉Γ（X）且G的导出子图G[X∪Γ（X）]是完全二部图;（b）G的导出子图G[（U-X）∪（W-Γ（X））]是完全二部图,且满足U-X＋1=W-Γ（X）;（c）U-X中每个顶点与W中的每个顶点都相邻,且X∪（W-Γ（X））是图G的一个独立集.
英文摘要：
A bipartite graph G without a perfect matching is said to be saturated if any new line is added,the resulting bipartitegraph having a perfect matching. For Xlohtai in V（G）,Γ（X）denotes all points in V（G）which are adjacent to at least one point of X. It isobtained that a bipartite graph G=（U,W）is saturated if and only if （a）there is only one Xlohtai in U such that X Γ（X） with X -1=Γ（X） and the induced subgraph G[X∪Γ（X）]is a complete bipartite graph;（b）G[（U-X）∪（W-Γ（X））]with U-X ＋1= W-Γ（X）is a complete bipartite graph;（c）every point of U-X is adjacent to every point of W and X∪（W-Γ（X））is an independent set.
同期刊论文项目
同项目期刊论文
期刊信息
位置：