| 【中文题名】 | 组合星图中的点不交路问题 |
| 【英文题名】 | |
| 【学科专业】 | 基础数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2002-1-14 |
| 【中关键词】 | 网络拓扑,组合星图,一对多点不交路,t-对点不交路,圈, |
| 【英关键词】 | network topology,Corn-Star graph,one-to-many node-disjoint paths,,,t-pairwise node-disjoint paths,cycle, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 本文解决了组合星图上一对多点不交路问题和t-对点不交路问题。对于第一个问题，
我们使用两种不同的方法。第一种方法是归纳法，证明了在n维组合星图上，从给定的一
点到给定的其它n-1 点，可以构造n-1条点不交路。另一种方法则利用组合星图的一些性
质，得到从给定的一点到给定的其它n-1点的n-1 条点不交路。对于第二个问题，我们证
明了在组合星图上，对于任意给定的t≤[(n-1)/2]对点，可以建立t条点不交路，每一条路
连接一对给定的点。这两个结果都是最优的。 |
| 【论文题纲】 |
|
组合星图中的点不交路问题 |
3 |
|
<中文摘要> |
3 |
|
<中文关键词> |
3-15 |
|
1 介绍 |
5-6 |
|
2 预备知识 |
6-7 |
|
3 方法一(归纳法) |
7-10 |
|
4 方法二 |
10-14 |
|
5 组合星图中t对点不交路 |
14-15 |
|
6 结论 |
15 |
|
<参考文献> |
15-17 |
|
Node-Disjoint Paths Problem in Corn-Star Networks |
17 |
|
<英文摘要> |
17 |
|
<英文关键词> |
17-19 |
|
-A- One-to-Many Node-Disjoint Paths Problem in Corn-Star Interconnection Networks |
19 |
|
<英文摘要> |
19 |
|
<英文关键词> |
19-25 |
|
<参考文献> |
25-26 |
|
-B- One-to-Many Node-Disjoint Paths Problem in Com-Star Interconnection Networks |
26 |
|
<英文摘要> |
26 |
|
<英文关键词> |
26-34 |
|
-C- t-pairwise Node-Disjoint Paths Problem in Com-Star Networks |
32-34 |
|
<参考文献> |
34-35 |
|
固定连接网络上的不交路问题 |
35 |
|
<中文关键词> |
35 |
|
<中文关键词> |
35-54 |
|
1 定义 |
37-38 |
|
2 一些网络的基本性质─超立方体,星图,组合星图 |
38-42 |
|
3 最短路问题 |
42-43 |
|
4 点不交路问题 |
43-51 |
|
5 CFT(Cluster Fault-Tolerant)路由 |
51-54 |
|
6 结论 |
54 |
|
<参考文献> |
54-57 |
|
Node-Disjoint paths Problem in Fixed-Connection Networks:A Survey |
57 |
|
<英文摘要> |
57 |
|
<英文关键词> |
57-80 |
|
1. Definitions |
59-61 |
|
2. Properties of some networks-hypercube,star,com-star,and so on |
61-66 |
|
3. Shortest Paths Problem |
66-67 |
|
4. Node-Disjoint Paths Problem |
67-76 |
|
5. CFT Routing |
76-80 |
|
6. Conclusion |
80 |
|
| 【DOI】 | LunWen.ID:2.2008.11312 |
