线性代数.doc

矿井通风网络图的矩阵表示
对任一矿井通风系统,如果不考虑各风流交汇点和通风巷道的位置、长度、形状及断面大小等情况,仅以单线表示各交汇点与风流的联结关系,那么,这种只用点的集合和线的集合来表示的通风系统图以及各线所联系得通风参数所组成的系统称为矿井通风网络。矿井通风网络图属于图论的范畴,是对矿井通风系统的抽象。它不仅有利于
分析、研究矿井通风系统的合理性,而且也是矿井通风系统模拟、网络解算、优化等的基础资料。
一个实际的矿井通风网络图往往是由数百条分支和数百个节点组成的,因而其分析与解算的工作量往往很大,计算机技术的应用在很大程度上提高了网络分析与解算的效率。但是,如果通风网络仅仅以几何形式来表示,则运用计算机来进行网络分析与解算也并非方便。如果将通风网络用矩阵的形式来表示,并将其输入到计算机中,则使用计算机进行网络分析与解算的工作变得十分的方便。因此,研究用矩阵的形式来表示通风网络,具有十分重要的意义。。
(1)通风网络拓扑关系的矩阵表示
矿井通风系统图是用点的集合和线的集合表示其图形的,记为G=(V,E)为节点的集合,它所包含节点数为m=|V|;而E为边(对应通风巷道)的集合,边数为n=|E|。即为。若不考虑各节点的位置,按通风巷道与各交汇点之间的联结关系,连接边,而且矿井通风系统是一个有向的连通体系,所以图G=(V,E)是一个有向连通图,其中的各有向边称为弧。若以通风巷道中的有关通风参数如风阻、风量、阻力等对应的边赋权,则图G=(V,E)
就是一个有向连通赋权图。
下面以某矿井的部分通风网络图为例,来说明常用到的表示网络拓扑关系
。
①节点邻接矩阵
对图,构造m阶方阵其中
称矩阵A是图G的节点邻接矩阵。
有向图的节点邻接矩阵的元素为

式中,第i行元素之和等于节点的出度,即以为尾的弧的数目,
,所以节点邻接矩阵A为9阶方阵:
m个节点的图的邻接矩阵为m阶方阵,它的存储需要占用m ×m个整数存储位置,所以其空间复杂度为。这种存储结构用于表示稠密图能够充分利用存储空间,但若用于表示稀疏图,则将是邻接矩阵变为稀疏矩阵,从而造成存储空间的很大
②关联矩阵与基本关联矩阵
有向图,,,,构造一个节点和分支相互连接的矩阵,其中:
则矩阵B为有向图G的完全关联矩阵。
、14个分支,其关联矩阵B为:
关联矩阵的特点:关联矩阵中每一列的元素含有一个1,一个-1,其他均为0,如果网络中的弧赋有权,可以把关联矩阵增加一行,把每一条弧所对应的权存储在增加的行中。如果网络中的弧赋有多种权,可以把关联矩阵增加相应的行数,把每一条弧所对应的权存储在增加的行中。
关联矩阵B所对应的行向量不是线性独立的,其最大线性无关的向量数,也就是秩rank(B)=m-1。从图G的关联矩阵B中,去掉与节点对应的一行,得行向量的线性无关的(m-1)×n的矩阵,称
为对应于节点的基本关联矩阵。基本关联矩阵的秩与完全关联矩阵的秩相等,即也有(m-1)个列是线性无关的。
,去掉与节点9对应的一行,得到行向量的线性无关的8×14的矩阵,为对应于节点9的基本关联矩阵。
可以看出,,关联矩阵中非“0”元所占总的存储空间的比重为22%,无论图含有多少个