图的结构性质、参数及参数化复杂性问题研究

结题报告

项目介绍

AI项目解读

基本信息

批准号：
11171097
项目类别：
面上项目
资助金额：
40.0万
负责人：
刘慧清
依托单位：
湖北大学
学科分类：
A0409.图论及其应用
结题年份：
2015
批准年份：
2011
项目状态：
已结题
起止时间：
2012-01-01 至2015-12-31

项目参与者：
陆玫；潘向峰；余看；章舜哲；胡小兰；殷丹；张馨元；徐寿林；
关键词：
图的结构图的性质图的参数参数化复杂性

项目摘要

结构图论、极值图论是图论及其应用中重要的研究方向，对图的结构问题的研究不但有重要的理论意义，而且在计算机科学、生命科学、管理科学和运筹学等学科中有很强的应用背景。本项目拟在我们长期从事结构图论、极值图论研究的基础上，对图中某些特定结构子图的存在性以及与之相关的有实际应用背景的问题进行研究，探讨图G在满足一定条件下周长和差数diff的下界和具有某些"稀有"性质的图，如含禁用minor图或者有界度的连通图的周长和差数；通过研究参数和图的结构性质之间的关系，发现一些新的结构性定理；通过研究具有某些特定结构子图的图的性质，获得某些具有应用背景的参数的极值；研究图的参数化复杂性（parameterized complexity）问题及其在网络中的应用。本项目是对图论问题及其应用之间的交叉研究,该项目的研究将推动这些领域理论研究的发展和加深对一些NP-完全问题的理解和实现。

结项摘要

本项目研究了图的结构性质，图的若干参数及相关的极值问题和构造性问题。通过对图的结构性质的刻画，运用图谱分析的方法，给出一个图具有Hamilton圈的谱条件；结合研究图的圈结构和路系统的方法, 给出了一个连通图包含支撑扫帚的度条件；针对网络编码图的结构的关系，研究了无向图的线性guessing number的性质以及某些具有应用背景的网络的容错性和匹配性；结合极值图论和代数图论的方法，研究图谱与图的结构参数之间的关系，在图的邻接谱以及（无符号）拉普拉斯谱与图的边连通度、围长、直径、半径、独立数以及控制数等参数之间建立了联系，进而给出了图的谱参数和图论的一些经典参数的关系；也刻画了一些图类中图的邻接矩阵或无符号拉普拉斯矩阵的特征值达到最大或最小时的极图。通过引进一些新的图类运算，探讨了图的结构的变化对参数以及参数之间的变化影响，结合代数方法，给出了赋权图和一致超图的谱参数和一些有应用背景的参数的新的界；提出一种一致性方法来处理不同格图的渐进拓扑指标问题，证明了格图的点拓扑指标、点平均关联能量的大小和点平均拟拉普拉斯能量的大小都是独立于它们的环形、柱形、自由边界条件的。这些研究推动了结构图论和极值图论以及与其他学科的交叉研究的发展。