| 二部图的因子覆盖与因子消去 |
| 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 Citation
GB/T 7714 |
陈京荣. 二部图的因子覆盖与因子消去[D]. 兰州. 兰州大学,2004.
|
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
