兰州大学机构库 >数学与统计学院
n条路的笛卡儿积图的匹配排除和条件匹配排除
Alternative TitleMacthing preclusion and conditional matching preclusion for Cartesian product of n paths
丁奇
Thesis Advisor张和平
2014-05-27
Degree Grantor兰州大学
Place of Conferral兰州
Degree Name硕士
Keyword匹配排除数 匹配排除集 条件匹配排除数 条件匹配排除集 n-grid图
Abstract本文主要考虑了 n 条路做笛卡尔积之后得到的 n-grid 图的匹配排除和条件匹配排除. 本文主要分为三章。第一章主要介绍了有关匹配排除集和条件匹配排除集的研究背景与研究现状. 第二章主要研究了 n-grid 图的匹配排除数和最优匹配排除集,当 n-grid 图的阶数为偶数的时候, n-grid 图的匹配排除数为 n 且每一个最优排除集都是平凡的; 当 n-grid 图的阶数为奇数的时候,n-grid 图的匹配排除数为 n+1且每一个最优匹配排除集在同构意义下是唯一的. 第三章主要研究了 n-grid 图的条件匹配排除数和最优条件匹配排除集, 当 n-grid 图的阶数为偶数的时候, n-grid图的条件匹配排除数为 2n-1 或者 2n-2 且每一个最优条件匹配排除集都是平凡的; 当 n-grid 图的阶数为奇数的时候, n-grid 图的条件匹配排除数为 2n 且每一个最优条件匹配排除集在同构意义下是唯一的。
Other AbstractIn this thesis, we discuss about the matching preclusion and conditional matching preclusion of the n-grid graph which is formed by Cartesian product of n paths. This thesis is divided into three chapters. We mainly introduce the background and research status of matching preclusion and conditional matching preclusion in the first chapter. We research matching preclusion number and optimal matching preclusion set of an n-grid graph in the second chapter. If an n-grid graph has an even order, then the matching preclusion number of the n-grid graph is n and every optimal matching preclusion set of the n-grid is trivial. If an n-grid graph has an odd order, then the matching preclusion number of the n-grid graph is n + 1 and every optimal matching preclusion set of the n-grid graph is unique up to isomorphism. We study conditional matching preclusion number and optimal conditional matching preclusion set of an n-grid graph in the third chapter. If an n-grid graph has an even order, then the conditional matching preclusion number of the n-grid graph is 2n-1 or 2n-2 and every optimal conditional matching preclusion set of the n-grid graph is trivial. If an n-grid graph has an odd order, then the conditional matching preclusion number of the n-grid graph is 2n and every optimal conditional matching preclusion set of the n-grid graph is unique up to isomorphism.
URL查看原文
Language中文
Document Type学位论文
Identifierhttps://ir.lzu.edu.cn/handle/262010/225674
Collection数学与统计学院
Recommended Citation
GB/T 7714
丁奇. n条路的笛卡儿积图的匹配排除和条件匹配排除[D]. 兰州. 兰州大学,2014.
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.