| 饱和二部图 |
| |
| 引用本文： | 张国志,王世英.饱和二部图[J].晋中师范高等专科学校学报,2010(3):19-20. |
| |
| 作者姓名： | 张国志 王世英 |
| |
| 作者单位： | [1]晋中学院数学学院,山西晋中030600 [2]山西大学数学科学学院,太原030006 |
| |
| 基金项目： | 山西省自然科学基金资助项目（20041002）; 国家自然科学基金资助项目（60773131） |
| |
| 摘 要： | 没有完美匹配的二部图G,若给它任意增加一条新的边,结果得到的二部图有完美匹配,则称图G是饱和的.设X包含于V（G）,Γ（X）表示V（G）中与X中至少一个顶点相邻的所有顶点组成的集合.本文证明了一个二部图G=（U,W）是饱和的当且仅当（a）存在唯一X包含于U,使得X〉Γ（X）,X-1〉Γ（X）且G的导出子图GX∪Γ（X）]是完全二部图;（b）G的导出子图G（U-X）∪（W-Γ（X））]是完全二部图,且满足U-X＋1=W-Γ（X）;（c）U-X中每个顶点与W中的每个顶点都相邻,且X∪（W-Γ（X））是图G的一个独立集.
|
| 关 键 词： | 饱和二部图 完美匹配 集合 |
Saturated Bipartite Graphs |
| |
| ZHANG Guozhi,WANG Shiying.Saturated Bipartite Graphs[J].Journal of Jinzhong Teachers College,2010(3):19-20. |
| |
| Authors: | ZHANG Guozhi WANG Shiying |
| |
| Institution: | 1. School of Mathematics,Jinzhong Univetsity,Jinzhong,Shsnxi 030600;2.School of Mathematical Sciences,Shanxi University,Taiyuan 030006) |
| |
| Abstract: | 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 GX∪Γ（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. |
| |
| Keywords: | saturated bipartite graphs perfect matching Assembly |
| 本文献已被 维普 等数据库收录！ |
|
