学位论文 > 优秀研究生学位论文题录展示

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

作　者: 王莉莉
导　师: 郭希娟
学　校: 燕山大学
专　业: 计算机软件与理论
关键词: 逆M矩阵完备路径n-弦图回路n-弦图模型
分类号: TP301.6
类　型: 硕士论文
年　份: 2007年
下　载: 47次
引　用: 0次
阅　读: 论文下载

内容摘要

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

全文目录

摘要  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

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

内容摘要

全文目录

相似论文