基于图中度序列的性质研究

发布时间：2022-01-23 20:58

　　设G=（V,E）是一个有限的简单无向图,V表示点集,E表示边集.对于一个给定的点x,与其相邻的所有点的个数称为点x的度（degree）,记为degG（x）.对于一个n阶的图G,由度等于i（0≤i≤n-1）的点构成的点子集Vi导出的子图称为度图（degree graph）,记为G[i].特别地,当图G为树时,称Gi为度森林（degree forest）.将一个n阶的图G中每个点的度按非增的顺序排列起来,得到的序列称为度序列（degree seguence）,记为d（G）.如果由非负整数构成的一个有限序列d是某个图G的度序列,那么称d为可图序列（graphic sequence）,图G则称为序列d的一个实现（realization）.首先,本文给出了有限制条件的三部可图序列的充要条件.其次,本文基于对非空度图的个数做归纳进行了度图可图性的研究,分别给出了非空度图个数为1,2,3以及k时度图可图的充要条件.然后本文给出了度森林可图的一个充分条件,即当叶子点足够多满足n1=∑i=2 n-1（ini-Si）-2（∑i=2 n-1 li-1）时,度森林是可图的,这里n1表示点子集V1中点的个数.最... 

【文章来源】：兰州大学甘肃省 211工程院校 985工程院校 教育部直属院校

【文章页数】：39 页

【学位级别】：硕士

【文章目录】：
中文摘要
Abstract
第一章 绪论
    1.1 基本概念及问题研究背景
    1.2 本文主要研究结果
第二章 三部可图序列
第三章 度图
    3.1 度图的性质
    3.2 度图的可图性
    3.3 有关可图性的转换操作
    3.4 度森林的可图性
第四章 点划分的性质研究
    4.1 基本的点划分性质
    4.2 不同标准的点划分性质
    4.3 Pantypical图
第五章 总结及展望
参考文献
致谢



本文编号：3605140