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

《数学与应用数学毕业论文-关联矩阵的性质及应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、本科生毕业论文题目关联矩阵的性质及应用学院数理学院专业数学与应用数学班级084姓名学号指导教师职称助教2012年5月20日新疆农业大学教务处制新疆农业大学2012届毕业设计（论文）成绩表学号学生姓名魏美玉性别女专业名称数学与应用数学班级数学084毕业设计（论文）题目关联矩阵的性质及应用答辩时间2012年5月19日答辩小组成员答辩姓名职称学历从事专业组长努尔古丽讲师研究生数学教学成员教授研究生数学教学副教授本科数学教学副教授本科数学教学讲师研究生数学教学助教研究生数学教学秘书助教研究生数学教学小组意见组长签名：2012年5月2

2、0日答辩小组评分目录摘要…………………………………………………………………………11关联矩阵的基本概念……………………………………………21.1无向图的全关联矩阵的定义………………………………21.2图的关联矩阵和参考点的定义……………………………31.3大子阵的定义…………………………………………………31.4有向图的完全关联矩阵的定义…………………………42关联矩阵的性质…………………………………………………52.1无向图的关联矩阵的性质……………………………………52.2有向图的关联矩阵的性质…………………………………

3、…62.3关联矩阵和割矩阵、圈矩阵的关系………………………………83关联矩阵的应用……………………………………………………11结论………………………………………………………………11附录………………………………………………………………12参考文献…………………………………………………………13谢辞………………………………………………………………………14关联矩阵的性质及应用作者：指导老师：摘要：用关联矩阵来表示图，不仅在理论上便于利用代数知识研究图的性质，构造算法；而且也便于计算机处理，在实际应用中也具有重要作用。关联矩阵，

4、用它来解决数学中的建模问题能使得问题更直观，起到化繁为简的作用。对于关联矩阵的研究，以下陈述关联矩阵的性质，说明关联矩阵性质的应用。主要收集有关关联矩阵的性质的应用的资料，并就资料列出相对应的性质。关键词：关联矩阵；有向图；无向图；图的矩阵14在图论中，任给一个图（包括有向图和无向图），都可以根据其点与边的关联关系，作出图关联矩阵。一个图的完全关联矩阵的行刻画了该图的相应顶点的关联集，因此，完全关联矩阵的行，给出了一个图的全部关联集。一个图的完全关联矩阵，描述了这个图的全部顶点和边的关联关系，而一个图的最基本的内容就是这种关

5、联关系。因此，一个图的完全关联矩阵可以用来描述图的特征。1关联矩阵的基本概念1.1无向图的完全关联矩阵的定义给定无向图，令=则由元素构成的矩阵为图的完全关联矩阵（Completeincidencematrix）,记作。.例1求如图1-1所示的图的完全关联矩阵.。用行表示顶点，列表示边，由图1-1可知（图1-1）14.=矩阵记号左边的1,2,3,4,5表示图的顶点，矩阵记号上面的表示图的边。这样，第一行标有1的那些元素，表示与顶点1关联的边，即顶点1的关联集；第二行标有1的那些元素，表示与顶点2关联的所有边，即顶点2的关联集等

6、等。一个图的完全关联矩阵的行刻画了该图的相应顶点的关联集，因此，完全关联矩阵的行，给出了一个图的全部关联集。因为完全关联矩阵的列表示图的边，又每一条边有两个端点，所以，在完全关联矩阵的每一列中有两个1，其余的元素均为零。一个图的完全关联矩阵，描述了这个图的全部顶点和边的关联关系，而一个图的最基本的内容就是这种关联关系。因此，一个图的完全关联矩阵可以用来描述图的特征。1.2图的关联矩阵和参考点的定义在阶连通的完全关联矩阵中，划去任一行后得到的矩阵，称为图的关联矩阵（incidencematrix），记作。划去的行所对应的顶点称

7、为参考点（referencevertex）。例2在图1所示的图的完全关联矩阵中去掉最后一行即得图的一个关联矩阵：14顶点5是参考点。1.3大子阵的定义矩阵的一个阶为的方阵，称为矩阵的一个大子阵，大子阵定义的行列式称为大行列式。1.4有向图的完全关联矩阵的定义设是有个顶点，条弧的有向图，令则称元素构成的矩阵为有向图的完全关联矩阵，记作。从中去掉一行，且秩为的矩阵，称为的关联矩阵，记作。例3求如图1-2所示的有向图的完全关联矩阵。14（图1-2）的完全关联矩阵是的关联矩阵是定点5为参考点。2关联矩阵的性质2.1无向图的关联矩阵的

8、性质引理2.1.1阶图是连通的当且仅当的完全关联矩阵的秩是。证明：（1）阶连通图的完全关联矩阵的秩为。由线性代数知，一个矩阵的行向量组的秩就是这个矩阵的秩。把完全关联矩阵的行看作是一个向量，那么完全关联矩阵的行向量组就是图的全部关联集，由阶连通图恰有个线性无关的关联集可知，完全关联矩阵的秩