图论与符号模式矩阵的性质及其在智能系统中的应用研究

摘要

组合矩阵论是组合学、图论和线性代数的有机结合体。自上世纪80年代来，它作为兴起且快速发展的一个数学分支，利用矩阵论和线性代数对组合定理进行证明及分析，描述了一些定性组合性质。同时，运用组合方法分析和证明了一些代数问题，如经典的Cayley-Hamilton定理。许多科学领域所建立的模型系统与数学模型中的很多定性性质是一致的，所以组合矩阵理论不但与众多的数学领域有密切的联系，而且在信息科学、社会学、经济学、生物学、化学、计算机科学理论和控制论等领域都有具体而实际的应用背景，因此组合矩阵理论是一个研究非常活跃且重要的领域。自Brualdi和Ryser的《组合矩阵论》问世以来，推动了组合矩阵理论深入研究和广泛的应用。
　　作为组合矩阵理论的重要组成部分——图论与符号模式矩阵，其研究是当前国际上组合矩阵论中一个年轻而又十分活跃的研究课题。图论主要研究图的拓扑性质，可以为任何一个包含了某种二元关系的系统提供一种分析和描述的模型。符号模式矩阵主要研究其定性类的组合结构，即研究其定性类中实矩阵的仅与其元素的符号以及零-非零结构有关而与其元素大小无关的组合性质。众所周知，智能体系统的通信结构图确定了其个体间信息交流和共享的方式，而且通信链的状态在系统稳定性方面和任务完成中具有决定性的作用，因此本文致力于以下两个问题的研究：一是在什么样的通信链条件下，网络化系统能够获得所要求的状态，例如达到智能系统的稳定状态；二是怎样设计智能体各元件之间的衔接来满足特定的实践任务中所需要的通信条件。用关联矩阵及其符号模式矩阵的一些性质作为理论基础，来说明所提出的条件与有向图中的环路之间的密切关系，且能够用来研究一些其它的网络问题，如有向网络的边一致问题等。而广义scrambling指数与广义μ-scrambling指数在通信系统中具有重要作用，因此本文应用符号模式矩阵研究了一类特殊图形的广义scrambling指数与广义μ-scrambling指数；同时研究了在什么样的条件下一个有向图可以转化为平衡图，以及符号模式矩阵的组合性质在智能系统中的应用。本文的主要研究工作如下：
　　（1）介绍了本文的研究背景与意义以及图论、符号模式矩阵基本概念，及图论和符号模式矩阵在机械器件、智能系统中的应用。
　　（2）研究了图理论在机械器件中的应用，利用图形的拓扑与几何特性，运用定性与定量的分析方法，设计出变节距滚子链，从而达到对多边形效应的补偿作用。正是新方法解决旧问题，是对学科融合的完美诠释。
　　（3）将智能系统各元件之间的相互联系，以及它们之间的影响程度用边连接起来，正相关元件之间的边用“1”或“+”标识，负相关元件之间的边用“-1”或“-”号标识，就组成了一个定号图。将智能系统与通信系统中的各元件之间的相互联系与影响程度抽象为图模型。利用图论与符号模式矩阵的相关知识对图形进行研究，计算出相关的指数与参数从而使系统达到稳定平衡的运行，如计算证明特殊图形的本原指数。然后再根据各元件之间影响程度列出函数，根据其相关性与系统运行时间的关系来判断元件按以上序列排列是否能够达到智能系统的稳定性。
　　（4）阐述了本原定号有向图的广义scrambling指数与广义μ-scrambling指数的研究进展，研究了一类本原定号有向图的广义μ-scrambling指数，分别得到了这一类图的?重下μ-scrambling指数和?重上μ-scrambling指数的界。同时给出了两个特殊图的广义scrambling指数与广义μ-scrambling指数。
　　（5）运用图理论中的加权图及其它知识，对Dijkstra算法进行优化。解决了几乎无不同权值的单源最短路径的Dijkstra算法的实现，以及混合权值的Dijkstra算法的实现。提出了基于Dijkstra算法考虑多个权值来计算最短路径，即基于Dijkstra算法混合权图的最短路径动态搜索数学模型。

目录

封面

声明

中文摘要

英文摘要

目录

1 引 言

1.1 研究背景和意义

1.2图论与符号模式矩阵的相关概念

1.3 图理论在机械器件中的应用

1.4 符号模式矩阵在智能控制中的应用

1.5 Dijkstra算法

1.6 论文的内容与安排

2 图理论在机械器件中的应用

2.1 链传动简介

2.2 多边形效应的补偿措施

2.3 实例计算与对比结果

2.4 本章小结

3 符号模式矩阵在智能控制中的应用

3.1引言

3.2 预备知识

3.3 有向图转平衡图的条件

3.4智能控制系统的数学模型

3.5一类本原有向图的本原指数及应用说明

3.6 本章小结

4 两类本原有向图的广义scrambling指数

与广义μ-scrambling指数

4.1 预备知识

4.2 广义scrambling指数与广义μ-scrambling指数的研究进展

4.3 一类特殊本原有向图的广义μ-scrambling指数

4.4 一个特殊本原有向图的广义scrambling指数与广义 scrambling?? 指数

4.5 两个本原有向图的广义scrambling指数与广义μ-scrambling指数

5 Dijkstra算法的一些优化及应用

5.1 Dijkstra算法原理及其优缺点

5.2 几乎无不同权值的单源最短路径的Dijkstra算法的实现

5.3 Dijkstra算法 ?

5.4 K为变量时的一个快速算法

5.5 最短路径动态搜索数学模型

5.6 本章小结

6 结论与展望

附 录

参考文献

攻读博士期间发表的论文及已取得的研究成果

致谢