| 【中文题名】 | 图的升分解问题 |
| 【英文题名】 | The Ascending Subgraph Decomposition Problem |
| 【学科专业】 | 应用数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2005-1-31 |
| 【中关键词】 | 图,升分解,二部图,循环图,正则图,混合积 |
| 【英关键词】 | graph,ascending subgraph decomposition,bipartite graph,circular graph,regular graph,mixed product,tensor product, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 升分解(ascending subgraph decomposition，简记为ASD)是1987年闻名世界的数学家Alavi与其他几位著名数学家给出的一种在真子图同构意义下的图的新分解，并且在同一论文中他们还提出了一个升分解猜想(Alavi猜想)：任意有正数条边的图都可升分解。升分解猜想自提出以后引起了世界上许多数学家的极大兴趣，但至今也只解决了很少的一部分，并且为了证明这个猜想，一个修改了的猜想更引人关注，本论文所证明的所有结论都是有关这个修改后的猜想的。
在本论文中我们主要讨论了几类特殊图的升分解，虽然对特殊图的升分解的讨论不能最终解决升分解猜想，但它可以缩小升分解猜想不成立的反例的寻找范围。而且本文还首次引进了矩阵的理论，结合矩阵的性质讨论了可升分解图的运算，这也为解决升分解猜想提供了一个新的研究方向。
对于二部图，因为它可以看作是从完全二部图K_(n_1n_2)中减去一个子图H所得的图，在此我们证明了当H满足一定的条件时，二部图K_(n_1n_2)-H可以升分解：并且还证明了当二部图G=(V_1，V_2)的一个顶点集中的顶点数，满足一定的条件时，G可以升分解。另外我们证明了循... |
| 【论文题纲】 |
|
摘要 |
6-7 |
|
ABSTRACT |
7-8 |
|
第一章 预备知识 |
8-13 |
|
§1．1 基本图论知识 |
8-10 |
|
§1．2 图的运算 |
10 |
|
§1．3 组异分解 |
10-13 |
|
第二章 升分解简介 |
13-19 |
|
§2．1 引言 |
13 |
|
§2．2 基本概念和发展概述 |
13-16 |
|
§2．3 研究方向 |
16-19 |
|
第三章 二部图的升分解 |
19-29 |
|
§3．1 主要引理 |
19-20 |
|
§3．2 二部图的升分解 |
20-25 |
|
§3．3 限制顶点数的二部图的升分解 |
25-29 |
|
第四章 正则图的升分解 |
29-39 |
|
§4．1 引理 |
29-30 |
|
§4．2 循环图的升分解 |
30-33 |
|
§4．3 正则图的升分解 |
33-39 |
|
第五章 升分解的运算 |
39-49 |
|
§5．1 定义 |
39-40 |
|
§5．2 循环图的混合积的升分解 |
40-43 |
|
§5．3 张量积的升分解 |
43-49 |
|
总结 |
49-50 |
|
致谢 |
50-51 |
|
参考文献 |
51-53 |
|
附录 发表论文情况 |
53 |
|
| 【DOI】 | LunWen.ID:2.2008.11491 |
