| 【中文题名】 | 基于有向图的逆M矩阵完备的判定及其算法的设计与实现 |
| 【英文题名】 | The Judgment of Inverse M-Matrix Completion Based on Digraph and Its Algorithm Design & Realization |
| 【学科专业】 | 计算机软件与理论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-7-30 |
| 【中关键词】 | 逆M矩阵,完备,路径n-弦图,回路n-弦图,模型, |
| 【英关键词】 | Inverse M-matrix,Completion,Path n-chordal digraph,Cyclic n-chordal digraph,Pattern, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>计算技术、计算机技术>一般性问题>理论、方法>算法理论 |
| 【论文摘要】 |
M矩阵是一类具有非正非对角元和非负对角元的矩阵,逆M矩阵是一类逆为M矩阵的非负矩阵。逆M矩阵在许多领域中都具有广泛的应用。本文利用图论理论研究逆M矩阵的完备问题,根据部分矩阵对应图形的不同特点,具体讨论了一些特殊图形所对应的部分矩阵的逆M矩阵完备性,寻求其各自的完备方法。
首先,研究了路径n-弦图的逆M矩阵完备问题。在回路n-弦图基础上定义路径n-弦图,在回路n-弦图完备定理的基础上,将图形中的简单回路扩展为简单路径,给出简单有向路径、路径1-弦图、路径2-弦图以及路径3-弦图的完备条件,并对路径n-弦图(n为任意自然数)的完备性进行探讨,并给以完备条件。同时,给出具体的完备算法,利用这些算法可以很容易得到与各图形相对应的部分逆M矩阵的完备式。
其次,研究了几种特殊的逆M矩阵模型的完备,包括环路径模型和回路n-弦图,给出了相应的完备定理和具体的完备算法。
最后,用Java程序设计语言实现了本文中所提出的简单路径、路径1-弦图和路径2-弦图的完备算法,且经过对算法的复杂性分析,验证了算法的可行性和有效性。
本文结合矩阵论、图论和算法设计的相关知识,研究了一些特殊有向图的... |
| 【论文题纲】 |
|
摘要 |
5-6 |
|
Abstract |
6-10 |
|
第1章 绪论 |
10-18 |
|
1.1 矩阵的发展与应用 |
10-11 |
|
1.2 M 矩阵研究的历史与现状 |
11-13 |
|
1.3 逆M 矩阵研究的历史和现状 |
13-14 |
|
1.4 逆M 矩阵完备问题的研究现状 |
14-16 |
|
1.5 本文的研究内容和结构安排 |
16-18 |
|
第2章 逆M 矩阵理论基础 |
18-22 |
|
2.1 逆M 矩阵的基本知识 |
18-19 |
|
2.2 图论的相关知识 |
19-20 |
|
2.3 逆M 矩阵完备基础 |
20-21 |
|
2.4 本章小结 |
21-22 |
|
第3章 路径n-弦图的逆M 矩阵完备 |
22-50 |
|
3.1 基本概念 |
22-23 |
|
3.2 路径1-弦图的逆M 矩阵完备 |
23-26 |
|
3.2.1 简单有向路径的逆M 矩阵完备 |
23-25 |
|
3.2.2 路径1-弦图的逆M 矩阵完备 |
25-26 |
|
3.3 路径2-弦图的逆M 矩阵完备 |
26-31 |
|
3.4 路径3-弦图的逆M 矩阵完备 |
31-35 |
|
3.5 路径n-弦图的逆M 矩阵完备 |
35-39 |
|
3.6 算法设计及实例 |
39-49 |
|
3.6.1 块团图的完备算法 |
39-40 |
|
3.6.2 简单有向路径的完备算法 |
40-41 |
|
3.6.3 路径1-弦图的完备算法 |
41-42 |
|
3.6.4 路径2-弦图的完备算法 |
42 |
|
3.6.5 路径3-弦图的完备算法 |
42-43 |
|
3.6.6 路径n-弦图的完备算法 |
43-44 |
|
3.6.7 完备算例 |
44-49 |
|
3.7 本章小结 |
49-50 |
|
第4章 逆M 矩阵模型的完备 |
50-62 |
|
4.1 基本概念 |
50-51 |
|
4.2 环路径的逆M 矩阵完备 |
51-56 |
|
4.2.1 完备定理 |
51-53 |
|
4.2.2 完备算法 |
53-54 |
|
4.2.3 完备算例 |
54-56 |
|
4.3 回路n-弦图的逆M 矩阵完备 |
56-61 |
|
4.3.1 完备定理 |
56-60 |
|
4.3.2 完备算法 |
60-61 |
|
4.4 本章小结 |
61-62 |
|
第5章 算法的实现与分析 |
62-71 |
|
5.1 算法实现的环境配置 |
62 |
|
5.2 简单路径完备算法的实现与分析 |
62-64 |
|
5.2.1 算法实现 |
62-63 |
|
5.2.2 算法分析 |
63-64 |
|
5.3 路径1-弦图完备算法的实现与分析 |
64-67 |
|
5.3.1 算法实现 |
64-65 |
|
5.3.2 算法分析 |
65-67 |
|
5.4 路径2-弦图完备算法的实现与分析 |
67-70 |
|
5.4.1 算法实现 |
67-68 |
|
5.4.2 算法分析 |
68-70 |
|
5.5 本章小结 |
70-71 |
|
结论 |
71-72 |
|
参考文献 |
72-76 |
|
攻读硕士学位期间承担的科研任务与主要成果 |
76-77 |
|
致谢 |
77-78 |
|
作者简介 |
78 |
|
| 【DOI】 | LunWen.ID:2.2008.359005 |
