二部图的因子覆盖与因子消去 | |

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. |

All comments
(0)

[Comments/Objections/Suggestion]
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.