数学与应用数学毕业论文-关联矩阵地性质及应用

关联矩阵的性质及应用作者：魏美玉指导老师：刘春奇摘要：用关联矩阵来表示图，不仅在理论上便于利用代数知识研究图的性质，构造算法；而且也便于计算机处理，在实际应用中也具有重要作用。关联矩阵，用它来解决数学中的建模问题能使得问题更直观，起到化繁为简的作用。对于关联矩阵的研究，以下陈述关联矩阵的性质，说明关联矩阵性质的应用。主要收集有关关联矩阵的性质的应用的资料，并就资料列出相对应的性质。关键词：关联矩阵；有向图；无向图；图的矩阵在图论中，任给一个图（包括有向图和无向图），都可以根据其点与边的关联关系，作出图关联矩阵。一个图的完全关联矩阵的行刻画了该图的相应顶点的关联集，因此，完全关联矩阵的行，给出了一个图的全部关联集。一个图的完全关联矩阵，描述了这个图的全部顶点和边的关联关系，而一个图的最基本的内容就是这种关联关系。因此，一个图的完全关联矩阵可以用来描述图的特征。1关联矩阵的基本概念1.1无向图的完全关联矩阵的定义给定无向图，令=则由元素构成的矩阵为图的完全关联矩阵（Completeincidencematrix）,记作。.例1求如图1-1所示的图的完全关联矩阵.。用行表示顶点，列表示边，由图1-1可知（图1-1）.=矩阵记号左边的1,2,3,4,5表示图的顶点，矩阵记号上面的表示图的边。这样，第一行标有1的那些元素，表示与顶点1关联的边，即顶点1的关联集；第二行标有1的那些元素，表示与顶点2关联的所有边，即顶点2的关联集等等。一个图的完全关联矩阵的行刻画了该图的相应顶点的关联集，因此，完全关联矩阵的行，给出了一个图的全部关联集。因为完全关联矩阵的列表示图的边，又每一条边有两个端点，所以，在完全关联矩阵的每一列中有两个1，其余的元素均为零。一个图的完全关联矩阵，描述了这个图的全部顶点和边的关联关系，而一个图的最基本的内容就是这种关联关系。因此，一个图的完全关联矩阵可以用来描述图的特征。1.2图的关联矩阵和参考点的定义在阶连通的完全关联矩阵中，划去任一行后得到的矩阵，称为图的关联矩阵（incidencematrix），记作。划去的行所对应的顶点称为参考点（referencevertex）。例2在图1所示的图的完全关联矩阵中去掉最后一行即得图的一个关联矩阵：顶点5是参考点。1.3大子阵的定义矩阵的一个阶为的方阵，称为矩阵的一个大子阵，大子阵定义的行列式称为大行列式。1.4有向图的完全关联矩阵的定义设是有个顶点，条弧的有向图，令则称元素构成的矩阵为有向图的完全关联矩阵，记作。从中去掉一行，且秩为的矩阵，称为的关联矩阵，记作。例3求如图1-2所示的有向图的完全关联矩阵。（图1-2）的完全关联矩阵是的关联矩阵是定点5为参考点。2关联矩阵的性质2.1无向图的关联矩阵的性质引理2.1.1阶图是连通的当且仅当的完全关联矩阵的秩是。证明：（1）阶连通图的完全关联矩阵的秩为。由线性代数知，一个矩阵的行向量组的秩就是这个矩阵的秩。把完全关联矩阵的行看作是一个向量，那么完全关联矩阵的行向量组就是图的全部关联集，由阶连通图恰有个线性无关的关联集可知，完全关联矩阵的秩为。（2）图的完全关联矩阵的秩等于的秩。设图是由个分支组成的分离图，的顶点数和边数分别为和。调整的行和列的次序，使它满足：最上面的行表示的顶点，接着的行表示的顶点，直到最下面的行表示的顶点；最左边的列表示的边，接着的列表示的边，知道最右边的列表示的边。这样把写成如下形式的分块矩阵：=其中是分支的完全关联矩阵。因为是连通的，所以的秩是，因此分块矩阵的秩是，即的秩等于图的秩。（3）因为完全关联矩阵的所有的行表示了图全部关联集，故由图中任意顶点的关联集等于其余顶点关联集的环合可知，矩阵的任一行，都可以表示成其余行的线性组合。因此，把矩阵的任意行划掉后，所得的矩阵，实际上仍然包含了的全部内容，也就是仍然可以描述图的全部特征。引理2.1.2连通图的关联矩阵的一个大子阵是非奇异的充要条件为与这个大子阵的列相应的边，组成的一颗生成树。证明：设是的一个大子阵，显然是一个阶方阵。如果是非奇异的，设与的列相应的边组成的子图为.因为有行，故应有个顶点（包括参考点），有列，则有条边。又因是非奇异的，即的秩是，所以是连通的，这就是说，是有个顶点，条的连通图。因此是一颗生成树。必要性得证。反之，如果的列所对应的边，组成的一颗生成树。因为树是连通的，由定理1知，的秩是，故为非奇异。根据引理，连通图中必存在生成树与关联矩阵的非奇异大子阵有一一对应的关系。由此可以得出求图的全部生成树的一种方法：找出图的关联矩阵的全部非奇异大子阵，每一个大子阵的列所对应的边就组成的一颗生成树。2.2有向图的关联矩阵的性质引理2.2.1设有向图有个顶点，那么的完全关联矩阵的秩是。引理2.2.2阶有向连通图的关联矩阵的一个大子阵是非奇异的充要条件为此大子阵的列对应的一颗生成树的树枝。引理2.2.3设是有向图的关联矩阵的一非奇异大子阵，那么的行列式的值为1或-1。证明：由假设中至少有一列仅有一个非零元素。假如不然，的每一列均有两个非零元素，则一个为1，另一个为-1。把的前行都加到最后一行，那么最后一行的元素均为零，这与是非奇异的假设矛盾。设中第列的元素除外，其余的元素均为零。把按第列展开，有（*）其中是中的余子式。子阵至少有一列仅有一个非零元素，否则可以推出，从而由（*），有，这与假设矛盾。设中第列除第行的元素为1或-1，其余元素均为零，则有其中是中元素的余子式。依此类推，可知。引理2.2.4毕内-柯西定理设分别是矩阵则乘积的行列式是的所有对应的大行列式乘积的和，即这里所谓的对应大行列式分别是由得第列和的行组成，即若取的大行列式为列，则的对应大行列式为行。引理2.2.5连通图的全部生成树的数目是其中为的关联矩阵。证明：显然，关联矩阵满足毕内-柯西定理的条件，故由毕内-柯西定理有（**）因为当且仅当的大子阵的列对应的一颗生成树时，此大子阵才是非奇异的。再由引理2.3.3知，的非奇异大子阵的行列式的值为1或-1，于是由（**）式有生成树的数目。例4求如图2-1所示的有向图的生成树的数目。（图2-2）的关联矩阵是而于是顺便指出，图所示的基础图的生成树的数目也是24。因此，对无向图来说，只要对任意定向，再利用引理2.2.4可求出的生成树的数目。2.3关联矩阵和割矩阵、圈矩阵的关系引理2.3.1设，分别是图的关联矩阵和割集矩阵，那么存在一个非奇异矩阵使引理2.3.2连通图的关联矩阵和完全圈矩阵满足,，其中，分别是，的转置矩阵。证明：调整，的列的次序，使得和的列按相同的边的次序排列。把，按行分块，写成列矩阵：，其中。根据分块矩阵的乘法，有其中（***）我们来考察（***）式。显然，当,只有当表示边与顶点关联,表示边在第个环路中。于是表示顶点在第个环路中，从而顶点的度为偶数。又顶点在环路中的度就是等式（***）右端的非零项项数。因而有（模2加法)这就是说，的每一个元素均为零，于是从而又有引理2.3.3设分别是图的关联矩阵和圈矩阵，则,证明：调整完全圈矩阵的行的次序，使由定理6，有引理2.3.4设图的关联矩阵和基本圈矩阵分别写成证明：其中对应生成树的连枝，那么由定理6，有于是因为是非奇异的，故有从而有3关联矩阵的应用利用关联矩阵解决一些数学方面的和实际应用方面的问题，能使纷繁复杂的数量关系有条不紊的摆在人们面前，将问题化繁为简，帮助人们找到解决问题的正确途径。比如，关联矩阵在解决数学方面的应用中利用关联矩阵来求出图的全部生成树。找出图的关联矩阵的全部非奇异大子阵，每一个大子阵的列所对应的边就组成的一颗生成树。设计关联矩阵智能分解方法，基于问题分解实现原理是将设计关联矩阵，分解成块状对角阵，然后根据对较块来分解设计问题。由图的关联矩阵，通过逐次极大全1子矩阵序列或元素全为1的极大对角块矩阵，给出了物品分区的代数求法，关联矩阵法等实际问题方面，关联矩阵的应用也很广泛。结论：关联矩阵的性质及应用还有很多，比如关联矩阵和割集矩阵，圈矩阵间的关系，关联矩阵在电学、计算机、和集合相容性检验等方面和实际生活中应用很广泛。总之，关联矩阵的作用作为数学基础有很广泛的用途，在不同的领域都能发挥其独特的作用，只要应用得好，肯定可以使原有的问题简单切易于解决。参考文献：[1]王朝阳.图论.北京理工大学出版社（北京）.ISBN7-81045-245-2[2]管梅谷.有趣的图论.山东科学技术出版社.1986（6）.[3]戴一齐，胡冠章，陈卫.图论与代数结构[M].北京清华大学出版社.1995[4]卢开澄，卢华明.图论及其应用[M].2版.北京清华大学出版社.1995[5]寿纪麟.数学建模[M].西安交通大学出版社.1996[6]胡慧蓉，王周敏.一种基于关系矩阵的关联规则快速挖掘算法[J].计算机应用.2005，（7）.1577-1579[7]陈树柏.网络图论及其应用.科学出版社.1982[8]孙慧泉.图论及其应用[M].北京科学出版社.2004[9]王与龙.等价关系与等价关系矩阵[J].兰州工业高等专科学校学报.2005.3（1）.39-42[10]戴本祁，雷良钦.由基本割集矩阵实现关联矩阵的代数方法.江西工业大学学报.1990（4）谢辞光阴似箭，日月如棱。四年的时间，在我们漫长的人生旅途中是那么的短暂，但是，这短短的四年是最真诚的青春，是最纯真的岁月，是最美丽的大学生活……我们的自学能力在这里得提升，我感谢所有的恩师：是您赋予我们最有意义的收获；是您带领我们走进知识殿堂，使我们不但丰富了知识；是您给我们一个全新的角度去发现美、创造美、欣赏美，给我们美的眼睛去发现世界的美，感悟生活的美；是你教会我们珍惜友谊和时间；是您给了我们看世界的眼睛，是你们用博大的胸怀，给予我们最无私的关怀和奉献。感谢各位老师在这几年一直在生活中、组织上给予我的教导和无私的帮助，让我在新疆农业大学这个大舞台上有锻炼的能力、自我完善的平台；感谢他们的教诲，让我知道在社会上懂得怎样去做好自己，端正自己的位置，为社会贡献出我自己的力量。同时，经过一个多