门槛图和拟门槛图中的一些优化问题

摘要

本文主要研究门槛图和拟门槛图的结构特点，并在此基础上解决了这两类图中的一些优化问题。 第一章中首先研究了门槛图的结构，得出这类图实质上是由一些单点的和或积得到的。认清这一结构性质后，本章设计了多项式时间算法构造出了反映门槛图结构性质的两种图一门槛图的中心树Tc和树形代表Td。然后，利用中心树和树形代表所反映的门槛图的性质，本章解决了门槛图中的以下优化问题：(1)设计多项式时间算法识别门槛图；(2)利用中心树找出门槛图的最大团，得到门槛图的最小边割集是平凡的；(3)构造树形代表，然后证明了树形代表的叶子节点构成原图的最大独立子集；(4)给出门槛图是哈密尔顿图的充要条件；(5)设计多项式时间算法计算出门槛图的带宽。 第二章首先构造了拟门槛图的树形代表，同时由构造树形代表的算法来识别拟门槛图，因为一个图是拟门槛图当且仅当它是某个树形图的导出图，而这个树形图就是该门槛图的树形代表。然后，出树形代表出发来构造其中心树，并在此基础上解决了拟门槛图中的以下优化问题：(1)找出拟门槛图的染色数、最大独立子集和最小团覆盖；(2)计算拟门槛图的带宽；(3)分析拟门槛图的哈密尔顿性；(4)设计多项式时间算法解决拟门槛图的边控问题。

目录

文摘

英文文摘

声明

引言

第一章门槛图中的优化问题

1.1门槛图的识别

1.2门槛图中的一些优化问题

1.2.1门槛图的最大团问题和最小边割集问题

1.2.2门槛图的最大独立子集问题和正常染色问题

1.2.3门槛图的哈密尔顿性

1.2.4门槛图的带宽问题

1.2.5门槛图的染色指数

1.2.6门槛图的拉普拉斯谱和支撑树数目

第二章拟门槛图中的优化问题

2.1拟门槛图的识别

2.2拟门槛图中的优化问题

2.2.1拟门槛图的染色数、最大独立子集和团覆盖

2.2.2拟门槛图的带宽

2.2.3拟门槛图的哈密尔顿性

2.2.4拟门槛图的边控问题

结论

参考文献

攻读学位期间的研究成果

致谢