二部图的因子覆盖与因子消去 Alternative Title Factor-covered and Factor-deleted Bipartite Graphs 陈京荣 Thesis Advisor 张和平 2004-05-10 Degree Grantor 兰州大学 Place of Conferral 兰州 Degree Name 硕士 Keyword 二部图 完美匹配 因子覆盖图 因子消去图 Abstract 图$G$称为$(g, f)$-因子覆盖的, 如果$G$的任何边都属于$G$的某个$(g,f)$-因子. $G$称为$(g, f)$-因子消去的, 若对图$G$的任何边$e$, $G-e$含有$(g, f)$-因子. 特别地, 当对所有顶点$x$, 都有$f(x)\equiv g(x)$时, $G$相应地称为$f$-因子覆盖图和$f$-因子消去图. 本文讨论了$G$是二部图的情形. 通过证明二部图的$(g,f)$-因子和$f$-因子存在性定理的等价形式, 得到了二部图是$(g,f)$-因子覆盖、 $(g, f)$-因子消去、$f$-因子覆盖和$f$-因子消去的四个充分必要条件. 称图$G$是基本的,如果其允许边构成$G$的连通子图. 当对所有顶点$x$, $f(x)$不恒为$1$时,$f$-基本图它不同于关于完美匹配的基本图, 我们得到$f$-基本二部图不仅可以有割边, 并且所有的割边都是固定双边.在此基础上, 我们证明了: 平面二部图$G$既是$f$-因子覆盖的又是$f$-因子消去的当且仅当$G$的每个面都是共振的,即$G$每个面的边界是关于某个$f$-因子的交错圈. Other Abstract A graph $G$ is called $(g, f)$-factor-covered if each edge of $G$ is contained in some $(g, f)$-factor. A graph $G$ is called $(g,f)$-factor-deleted if $G-e$ contains a $(g, f)$-factor for every edge $e$ of $G$. In particular, $G$ is called $f$-factor-covered or $f$-factor-deleted, if $f(x)\equiv g(x)$ for all $x\in V(G)$. In this paper, we discuss bipartite graphs $G$. By showing equivalent forms of Heinrich's existent theorem for $(g,f)$-factor and Ore's existent theorem for $f$-factor of bipartite graph, we obtain sufficient and necessary conditions for a bipartite graph to be $(g, f)$-factor-covered、$(g, f)$-factor-deleted、$f$-factor-covered and $f$-factor-deleted. A graph $G$ is called elementary, if all its allowed edges form a connected subgraph of $G$. If $f(x)$ is not always $1$ for every vertex $x$ of $G$, $f$-elementary graphs are different from elementary graphs. We obtain that $f$-elementary bipartite graphs may have a cut-edge, and such cut-edges are fixed-double-edges. From this, we prove that: a plane bipartite graph $G$ is both $f$-factor-covered and $f$-factor-deleted if and only if each face of $G$ is resonant, that is , the boundary of each face in $G$ is a $F$-alternate cycle, where $F$ is a $f$-factor of $G$. URL 查看原文 Language 中文 Document Type 学位论文 Identifier https://ir.lzu.edu.cn/handle/262010/225492 Collection 数学与统计学院 Recommended CitationGB/T 7714 陈京荣. 二部图的因子覆盖与因子消去[D]. 兰州. 兰州大学,2004.
 Files in This Item: There are no files associated with this item.
 Related Services Recommend this item Bookmark Usage statistics Export to Endnote Altmetrics Score Google Scholar Similar articles in Google Scholar [陈京荣]'s Articles Baidu academic Similar articles in Baidu academic [陈京荣]'s Articles Bing Scholar Similar articles in Bing Scholar [陈京荣]'s Articles Terms of Use No data! Social Bookmark/Share
No comment.
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.