学位论文 > 优秀研究生学位论文题录展示

关于图的最大匹配问题的若干结果

作　者: 刘岩
导　师: 林诒勋
学　校: 郑州大学
专　业: 基础数学
关键词: 最大匹配图最大匹配问题导出匹配可扩完美匹配二部图 starting consists only 当且仅当 numb
分类号: O157.5
类　型: 博士论文
年　份: 2000年
下　载: 361次
引　用: 1次
阅　读: 论文下载

内容摘要

The study on the maximum matchings (as well as perfect matchings) of a graph plays a central role in matching theory. In addition to the algorithnis of finding maximum matchings, the structural properties of all maximum matchings are significant in theory or application aspect. Roughly speaking, the properties we are concerned in this thesis are mainly as follows:1.How many maximum matchings are there in a graph?2.How are they transformed from each other?3.How are they growing from smaller matchings?In other words, we shall concentrate ourselves on the enumeration, the transformation graph and the extendability of maximum matchings. The organization of the thesis is as follows.In the first chapter, we list some terminologies, notations and introduce some topics about matching theory. In the second chapter, some results about the number of maximum matchings are presented. In the third chapter, the maximum matching graph of a graph is characterized. In the fourth chapter, we give degree conditions of induced matchingextendable graphs and conditions of a matching and a maximum matching being an induced one, respectively, and obtain some results about matching extendability.Number of Maximum MatchingsThe research on the number of perfect matchings can be found in many articles [11-14]. But not many results about the number of maximum matchings are known( even in bipartite graphs). In this part, some1results about this topic are presented. Firstly, We give some good lower bounds of the number.Theorem 1. Let G = (A, B) be a connected bipartite graph with positive surplus( as viewed from A). Then G has at least IE(G)I + (jAj ?1) * (def(G) ?2) maximum matchings.Theorem 2. Let G = (A, B) be a bipartite graph with positive surplus( as viewed from A), deficiency 1 and minimum degree at least 2. Then G contains at least 2jE(G)j ?21B1 near-perfect matchings.Theorem 3. Let G be a factor-critical graph. Then G has at least IE(G)I ?c)~near-perfect matchings, where c is the number of utverticesof C.~?bLocksThe enumeration problems for maximum matchings on some special graphs are solved.Theorem 4. Let C = (A, B) is a bipartite graph with positive surplus( as viewed from A) and deficiency 1. Then the following are equivalent:(i)Every vertex of A has degree 2;(ii)G is a tree;(iii) Every vertex of A is a barrier of G;(iv) C kas exactly IAI + 1 near-perfect matchings;(v)C ?v has a unique perfect matching for any vertex v C B.Theorem 5. Let C = (A, B) be a bipartite graph with positive surplus( as viewed from A), deficiency 1 and minimum degree 1. Then G has exactly ~E(G)j ?IAI + 1 near-perfect matchings if and only if there exists a vertex in NG(u) with degree 1 for any vertex u in A with degree at least 3.Theorem 6. Let G = (A, B) be a bipartite graph with positive surplus( as viewed from A), deficiency 1 and dG(v) = 2 for each vertex v in B. Then G has exactly 2jBI + 2m near-perfect matchings, where m is the number of cut vertices in B.Theorem 7. Let C be a 2-connected factor-critical graph. Then2G has precisely IE(G) near-perfect matchings if and only if there existsan ear decomposition of G starting with a nice odd cycle C; that is,G = C + P1 + ... ?Pk satisfying that P~ is open and two ends of P1 areconnected in G~1 by a pending path with length 2 of G for 1 <i < kwhereGo=CandG1=C盤i?..盤iforl<i<k.Theorem 8. Let G be a factor-critical graph. Then C has precisely IE(G)I ?c~iear-perfect matchings if and only if there exists an-4-Iear decomposition of C starting with a nice odd cycle C; that is, C =C + P1 + ... + Pk satisfying that two ends of P~ are connected in G~.1 by a pending path with length 2 of C for any open ear P,, where c is the nuniberof~r~j~ic~jofGandG1 = C+P1+...盤1,wherel <i< k.Maximum Matching GraphIn articles [25-27], authors defined the maximum matching graph as follows. The

全文目录

英文摘要  12-19
1 Introduction and Notations  19-29
  1．1 Introduction to Matching Theory  20-23
  1．2 Concepts and Terminology  23-26
  1．3 Some Results on Maximum Matchings  26-29
2 Number of Maximum Matchings  29-50
  2．1 Introduction and Preliminaries  30-34
  2．2 Lower Bounds of the Number  34-38
  2．3 Enumeration of Maximum Matchings on Special Bipartite Graphs  38-44
  2．4 Enumeration of Maximum Matchings on Factor-critical Graphs  44-50
3 Maximum Matching Graph  50-83
  3．1 Introduction and Preliminaries  51-55
  3．2 Girth and Path of Maximum Matching Graph  55-65
  3．3 Subgraphs of Maximum Matching Graph  65-70
  3．4 Connectivity of Maximum Matching Graph  70-76
  3．5 Conditions of the Graph Being a Specified Graph  76-83
4 Matching Extendability  83-103
  4．1 Introduction and Preliminaries  84-85
  4．2 Condition of a Matching Being an Induced Matching  85-87
  4．3 Degree Condition of IM-extendable Bipartite Graphs  87-92
  4．4 Degree Condition of IM-extendable Non-bipartite Graphs  92-100
  4．5 Problems and Results of Matching Extendability  100-103
Reference  103-107

关于图的最大匹配问题的若干结果

内容摘要

全文目录

相似论文