基于有向图的逆M矩阵完备的判定及其算法的设计与实现

摘要

M矩阵是一类具有非正非对角元和非负对角元的矩阵，逆M矩阵是一类逆为M矩阵的非负矩阵。逆M矩阵在许多领域中都具有广泛的应用。本文利用图论理论研究逆M矩阵的完备问题，根据部分矩阵对应图形的不同特点，具体讨论了一些特殊图形所对应的部分矩阵的逆M矩阵完备性，寻求其各自的完备方法。 1.研究了路径n-弦图的逆M矩阵完备问题。在回路，n-弦图的基础上定义路径n-弦图，在回路，n-弦图完备定理的基础上，将图形中的简单有向回路扩展为简单有向路径，给出简单有向路径、路径1-弦图、路径2-弦图以及路径3-弦图的完备条件及严格的理论证明，并对路径n-弦图(n为任意自然数)的完备性进行探讨，并给以完备条件。同时，给出具体的完备算法，利用这些完备算法可以很容易得到与各图形相对应的部分逆M矩阵的完备式。 2.研究了几种特殊的逆M矩阵模型的完备，包括环路径模型和回路，n-弦图，给出了相应的完备定理及严格的理论证明，并进一步给出具体的完备算法。 3.用Java程序设计语言，实现了文中所提出的简单有向路径、路径1-弦图和路径2-弦图的完备算法，且经过对算法的时间复杂性分析，验证了算法的可行性和有效性。 本文结合矩阵论、图论和算法设计分析的相关知识，研究了一些特殊有向图的逆M矩阵完备问题，取得了一定的成果，为后续逆M矩阵的进一步研究起到了借鉴的作用。

目录

文摘

英文文摘

声明

第1章绪论

1.1矩阵的发展与应用

1.2 M矩阵研究的历史与现状

1.3逆M矩阵研究的历史和现状

1.4逆M矩阵完备问题的研究现状

1.5本文的研究内容和结构安排

第2章逆M矩阵理论基础

2.1逆M矩阵的基本知识

2.2图论的相关知识

2.3逆M矩阵完备基础

2.4本章小结

第3章路径n-弦图的逆M矩阵完备

3.1基本概念

3.2路径1-弦图的逆M矩阵完备

3.2.1简单有向路径的逆M矩阵完备

3.2.2路径1-弦图的逆M矩阵完备

3.3路径2-弦图的逆M矩阵完备

3.4路径3-弦图的逆M矩阵完备

3.5路径n-弦图的逆M矩阵完备

3.6算法设计及实例

3.6.1块团图的完备算法

3.6.2简单有向路径的完备算法

3.6.3路径1-弦图的完备算法

3.6.4路径2-弦图的完备算法

3.6.5路径3-弦图的完备算法

3.6.6路径n-弦图的完备算法

3.6.7完备算例

3.7本章小结

第4章逆M矩阵模型的完备

4.1基本概念

4.2环路径的逆M矩阵完备

4.2.1完备定理

4.2.2完备算法

4.2.3完备算例

4.3回路n-弦图的逆M矩阵完备

4.3.1完备定理

4.3.2完备算法

4.4本章小结

第5章算法的实现与分析

5.1算法实现的环境配置

5.2简单路径完备算法的实现与分析

5.2.1算法实现

5.2.2算法分析

5.3路径1-弦图完备算法的实现与分析

5.3.1算法实现

5.3.2算法分析

5.4路径2-弦图完备算法的实现与分析

5.4.1算法实现

5.4.2算法分析

5.5本章小结

结论

参考文献

攻读硕士学位期间承担的科研任务与主要成果

致谢

作者简介