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

论文摘要

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

论文目录

• 摘要
• Abstract
• 第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 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间承担的科研任务与主要成果
• 致谢
• 作者简介