n条路的笛卡儿积图的匹配排除和条件匹配排除

兰州大学机构库 >数学与统计学院

	n条路的笛卡儿积图的匹配排除和条件匹配排除
Alternative Title	Macthing 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 Abstract	In 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	学位论文
Identifier	https://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.

If you have any objections to this item, please fill out the form below and the administrator will contact you as soon as possible.
Content:
Email：	*
Institution:
Verification Code:	Refresh

Any comments and suggestions are welcomed.
Title:	*
Content:
Email：	*
Verification Code:	Refresh

数学与统计学院知识库