兰州大学机构库 >数学与统计学院
二部图的因子覆盖与因子消去
Alternative TitleFactor-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 AbstractA 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学位论文
Identifierhttps://ir.lzu.edu.cn/handle/262010/225492
Collection数学与统计学院
Recommended Citation
GB/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.