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

图的导出匹配可扩性

作　者: 周菊
导　师: 原晋江
学　校: 郑州大学
专　业: 运筹学与控制论
关键词: 导出匹配可扩可扩性完美匹配无爪图结合图直径为奇分支导出子图连通图乘积图
分类号: O157.5
类　型: 硕士论文
年　份: 2004年
下　载: 49次
引　用: 0次
阅　读: 论文下载

内容摘要

本文所涉及到的图均是有限的，无向的，简单图。本文主要以下几部分组成： 1．直径为2的无爪图的导出匹配可扩性 2．结合图的导出匹配可扩性 3．2n个点3n-1条边的导出匹配可扩性的刻划 4．2n个点3n条边的导出匹配可扩性的刻划 5．树的平方图的导出匹配可扩性的刻划如果边集M（?）E（G）中的任意两条边都没有公共的端点，那么就称边集M是图G的一个匹配。如果图G的一个匹配M覆盖了它的所有的顶点，那么称这个匹配为图G的一个完美匹配。如果G的匹配M中的任两条边不相邻，则称M为导出的。如果一个图G的任一个导出匹配都包含在它的一个完美匹配里，我们称图G为导出匹配可扩的。 1．直径为2的无爪图的导出匹配可扩性如果图G不包含K_1，3这样的导出子图，则称它为无爪图。如果点u和v在G中是连通的，则u和v的距离d_G（u，v）定义为u和v之间最短路的长度。如果图G中任意两点间的最大距离为r，就称图G的直径为r。在这一部分首先刻划了直径为2的无爪图是导出匹配可扩的充分必要条件，进而，给出了判定一个直径为2的无爪图是导出匹配可扩的的一个多项式时间算法。定理1．1 假设G是一个直径为2的无爪图，M={u₁v₁，u₂v₂，…，u_mv_m}是G的一个导出匹配且满足G-V（M）不连通，则|M|≤3。定理1．2 直径为2的无爪图G是导出处匹配可扩的充分必要条件是对任意的G的导出匹配|M|≤3，G-V（M）没有奇分支。算法1．3 直径为2的无爪图的导出匹配可扩性的判定第一步：任取满足|M|≤3的边集M（?）E（G），判断M是否是G的导出匹配并生成集合M={M（?）E（G）|M是G的一个满足|M|≤3的导出匹配}。第二步：如果M=φ，则终止；G是导出匹配可扩性的。否则，转第三步。第三步：任取M∈M并生成G-V（M）。第四步：如果G-V（M）有奇分支，则终止；G是导出匹配不可扩的。否则，G-V（M）没有奇分支，令 M：=M＼{M}，转第二步。定理1.4对于给定的直径为2的无爪图G，上述算法能在o（二“）时间内判断出G是否为导出匹配可扩的.2。结合图的导出匹配可扩性图G和H的结合图侧川的点集为v（G） x v（H），其中（。，。）和矿，汉相邻的充分必要条件是眺，E侧G)或者。二了并且二，任E(川. 在这一部分，刻划了结合图的导出匹配可扩性.证明了结合图剑川是导出匹配可扩的如果图G和H都是平凡的，G连通并且G和H满足下列条件之一: （l）G和H中有一个是导出匹配可扩的; （2）G和H都有完美匹配; （3）G和H中一个是非平凡的并且有几乎完美匹配，另一个有完美匹配. 定理2.1如果G和H中有一个是导出匹配可扩的，那么酬川是导出匹配可扩的。定理”如果‘和H都有完美匹配，那么引州是导出匹配可扩的。定理肠如果G有完美匹配，H是非平凡的并且有几乎完美匹配，那么a[川是导出匹配可扩的. 定理2.4如果G是非平凡的并且有几乎完美匹配，H有完美匹配，那么剑川是导出匹配可扩的.3.Zn个点3n一1条边的导出匹配可扩性的刻划图T和H的乘积图Tx刀的点集为V（劝x州H），其中(二，司和丫，了相邻的充分必要条件是。一x如果H二KZ，叩任E（H）或者二二夕，二任E(刀。TxK:定义为v（T‘兀2）={x，:x任V（T），:=l，2}并卫刀（T“KZ）=斑二lx::x任V（T）}日{x*岁，:x岁〔E（T），泛=1，2}.对于乞=l，2，由{x，:x〔V(劝}导出的图T/场的子图，记为界，称为T的第乞个拷贝.二，表示只中的点，它对应于T中的点二. 具有2。个点3，:一1条边的图厅被称为是（2n，3二一i）一优的，如果万同构于Tx从十。，其中T是任意一棵有。个顶点的树，。是Tx从中的一条连接T的两个不同拷贝且距离为3的边。兀反3表示从K3，3删去一边得到的图。在{331中，原晋江老师证明了2n个点的连通的导出匹配可扩图至少有3n一2条边，并且具有抓个点3、一2条边的导出匹配可扩图只能是了x从，其中T是任意一个n顶点的树.在这一部分，证明了2。全6个点3。一2条边的导出匹配可扩图只能是T xK:+。，其中T是任意一个有。全3个顶点的树，e是Tx从中一条连接T的两个不同拷贝且距离为3的边. 命题3.1每一个有6个点，8条边的导出匹配可扩图都同构于从3· 命题3.2如果G是一个有2。全6个顶点3。一1条边的连通的导出匹配可扩图，那么‘是(2。，3n一l卜优的. 命题3.3假设G是（2。，3n一l）一优的，那么G是导出匹配可扩的. 定理3.4假设G是一个有2。个顶点3n一1条边的连通图，那么G导出匹配可扩的充分必要条件是G是（2。，3。一l）一优的.4 Zn个点3n亲边的导出匹配可扩性的刻划假设G是一个连通图，Q是G的一个导出子图，召1，仇，…，G:是G一v（Q）的连通分支.如果召满足以下两条件，则我们称G是一个q关节图: （l）G一v（动的每一个分支‘、是一棵树，不妨设为及，和凡的乘积图，也就是说，G、=及火兀2· （z）对G一v（Q）的任一个分支G、，有两个相邻的顶点x（“），尹）‘v(动和:（*）〔v（八）（二{无’:岁。E（‘*））满足二‘哟:{‘’，。(“，:;无’。E（引连接。、和Q的所有的边进一步，我们用吼表示有点集v（‘、）u恤（^），幼无）}导出的图G的一个导出子图，也就是说，以=侧V

全文目录

Chinese Abstract  5-9
English Abstract  9-14
1 Introduction and Notations  14-20
  1.1 Introduction to Matching Theory  15-16
  1.2 Concepts and Terminology  16-17
  1.3 Some Known Results on Induced Matching Extendable Graphs  17-19
  1.4 The Main Results of the Thesis  19-20
2 Induced Matching Extendability of Claw-free Graphs of Diameter 2  20-26
  2.1 Main Results  21-25
  2.2 Algorithm and its Correctness  25-26
3 Induced Matching Extendability of the Composition of Two Graphs  26-31
4 Characterization of the Induced Matching Extendable Graphs with 2n Vertices and 3n-1 Edges  31-41
  4.1 Preliminaries  32-33
  4.2 Main Results and Proofs  33-41
5 Characterization of the Induced Matching Extendable Graphs with 2n Vertices and 3n Edges  41-65
  5.1 Preliminaries  42-43
  5.2 Main Results and Proofs  43-65
6 Characterization of the Induced Matching Extendability of the Square of Trees  65-69
  6.1 Proof of the theorem  66-69
Acknowledgement  69-70
References  70-72

图的导出匹配可扩性

内容摘要

全文目录

相似论文