2025年大学《数理基础科学》专业题库- 线性代数在图论中的应用

2025年大学《数理基础科学》专业题库——线性代数在图论中的应用考试时间：______分钟总分：______分姓名：______一、选择题1.设无向图G的邻接矩阵为A，则矩阵A中第i行（列）元素之和等于顶点i的()。A.度数B.边数C.链路数D.�环数2.若一个无向图G是树，则其邻接矩阵A满足的性质是()。A.A为对称矩阵，且A中存在且仅存在一个零元素。B.A为对称矩阵，且A的对角线元素均为2。C.A为对称矩阵，且A中不含环。D.A为对称矩阵，且A的秩为顶点数。3.设G为n阶无向简单图，其邻接矩阵A的特征值中，零度特征值的个数等于图G的()。A.顶点数B.边数C.连通分支数D.独立数4.若一个n阶方阵A可逆，则其对应的图（通常指无向简单连通图）具有()。A.无环B.至少一个环C.可能连通也可能不连通D.顶点数小于边数5.对于有向图G，其邻接矩阵A的幂A^k（k为正整数）中，a_ij（i≠j）表示()。A.从顶点i到顶点j长度为k的路径数B.从顶点i到顶点j长度为k的简单路径数C.从顶点i到顶点j长度为k的路径总数（含简单路径和非简单路径）D.顶点i和顶点j之间的距离二、填空题1.设G为n阶无向简单图，其邻接矩阵A为对称矩阵，若顶点i和顶点j之间存在边，则A中a_ij和a_ji的值为________。2.设G为n阶无向连通简单图，其邻接矩阵A的度矩阵D定义为D=dd_11+dd_22+...+dd_nn，其中d_ii表示顶点i的度数，则矩阵D是对角矩阵，其对角线元素d_ii=________。3.设G为n阶无向简单图，其邻接矩阵A的路径矩阵P=A+A^2+...+A^(n-1)，则矩阵P中p_ij（i≠j）表示从顶点i到顶点j长度为_______的路径数。4.设G为n阶无向简单图，其关联矩阵B的秩为n-1，则图G一定是_______。5.设n阶方阵A是某个无向简单图的拉普拉斯矩阵（L=D-A，其中D为度矩阵，A为邻接矩阵），则矩阵L的非零特征值个数等于图G的_______。6.设λ是n阶方阵A的特征值，x是相应的特征向量，若将A应用于以x为顶点的n维向量空间中的向量y，则结果为________。三、计算题1.设有向图G的邻接矩阵A如下：```A=|0100||0010||0001||1000|```计算矩阵A的平方A^2和立方A^3，并解释A^2中元素a_23的值以及A^3中元素a_14的值分别表示什么。2.设有n个顶点的无向完全图K_n，其邻接矩阵为A。证明：矩阵A的特征值包括0和n。(提示：考虑完全图的性质和全1向量)3.设无向图G的邻接矩阵A为：```A=|01100||10110||11011||01101||00110|```计算图G的度矩阵D、拉普拉斯矩阵L，并求出矩阵L的特征多项式（无需解出特征值）。四、证明题1.证明：一个无向图G是树，当且仅当其邻接矩阵A满足det(A-λI)=0对于所有λ≠0成立（即除了0以外的所有特征值都不是特征值）。(提示：考虑树的性质，如连通性、无环、n-1条边)2.设G为n阶无向简单图，其邻接矩阵为A。证明：矩阵A+A^T（其中A^T是A的转置矩阵）是对称矩阵，并且其秩等于图G的边数。(提示：考虑A+A^T的定义和对称性，以及图的边与矩阵中非零元素的关系)试卷答案一、选择题1.A2.D3.C4.C5.A二、填空题1.12.2*度数i3.k4.树5.n-16.λy三、计算题1.解：A^2=|1100||0110||0011||0001|A^3=|0111||0011||0001||0000|A^2中元素a_23=1，表示从顶点2到顶点3长度为2的路径有1条（例如：2-3-2-3）。A^3中元素a_14=1，表示从顶点1到顶点4长度为3的路径有1条（例如：1-2-3-4）。2.证明思路：（必要性）考虑向量v=(1,1,...,1)^T（全1向量）。计算Av=n*(1,1,...,1)^T。因此，n是A的一个特征值，对应的特征向量为v。考虑λ=0，计算Aw=0*w=0。因此，0也是A的一个特征值。完全图K_n的任何两个顶点间都有边，且边是无向的，所以它是连通的，且任何顶点都可以通过边到达其他所有顶点，意味着它也是强连通的（对于简单图），所以不存在孤立点，0是唯一的零度特征值。对于非零特征值，考虑K_n的补图是空图，其邻接矩阵全0，特征值全为0。利用谱的性质，K_n的邻接矩阵的特征值与补图邻接矩阵的特征值之和为n（对于任何k，K_n和其补图的邻接矩阵之和为n*J，J为全1矩阵，其特征值为n和0）。因此，K_n的邻接矩阵A的非零特征值之和为n。由于A是实对称矩阵，其特征值为实数且可重复，且至少一个特征值为0。设非零特征值为λ1,λ2,...,λ_k（可能有重复），则λ1+λ2+...+λ_k=n。因为λ_i≥0，所以λ_i=1（i=1,...,k）。由于K_n的连通性，其邻接矩阵至少有n-1个非零特征值（对应于从每个顶点到其他所有顶点的路径）。因此，所有非零特征值必须都是1。所以A的特征值为0和n。（充分性）略（通常证明反过来较难）3.解：度矩阵D：```D=|20000||02000||00200||00020||00002|```拉普拉斯矩阵L=D-A：```L=|2-1-100||-12-1-10||-1-12-1-1||0-1-12-1||00-1-12|```特征多项式：det(L-λI)=det```|2-λ-1-100||-12-λ-1-10||-1-12-λ-1-1||0-1-12-λ-1||00-1-12-λ|```利用行列式性质和按行（列）展开：=(2-λ)*det```|2-λ-1-1-1||-12-λ-1-1||-1-12-λ-1||-1-1-12-λ|```-(-1)*det```|-1-1-10||-12-λ-1-1||-1-12-λ-1||-1-1-12-λ|```第一个子行列式继续展开（按第一行）：=(2-λ)*[(2-λ)*det(3x3)-(-1)*(-1)*det(4x4)]-(-1)*[(-1)*det(4x4)-(-1)*(-1)*det(3x3)]（计算过程中det(3x3)和det(4x4)的表达式会涉及多项式，最终整理后得到特征多项式为-λ^5+10λ^4-35λ^3+50λ^2-24λ。）四、证明题1.证明思路：（必要性）假设G是树。树有n个顶点和n-1条边。邻接矩阵A是n阶方阵。根据线性代数理论，det(A-λI)=0对所有λ是A的特征值的充分必要条件是A-λI不可逆。A-λI不可逆意味着其行列式为0。对于树，A的特征值包括0和n-1个大于0的特征值（可以通过构造性证明或利用补图性质证明）。因此，存在λ=0是A的特征值。对于λ≠0，由于树是连通且无环的，A-λI不可逆。因此，det(A-λI)=0对于所有λ≠0成立。（充分性）假设det(A-λI)=0对于所有λ≠0成立。这意味着A的特征值只能是0。根据线性代数理论，det(A-λI)=0对于所有λ≠0意味着A-λI是奇异的（不可逆的）仅当λ=0。因此，A只有0这一个特征值。设G的顶点数为n。如果G不是树，则它不是连通的或包含环。如果G不连通，设其连通分支数为k(k>1)，则存在一个k阶连通分支和一个或多个1阶连通分支（孤立点）。孤立点的度数为0，其对应的邻接矩阵行和为0。包含环的连通图，其对应的邻接矩阵至少有一个非零特征值（环的存在意味着存在非平凡循环，对应的邻接矩阵乘幂有非零解，从而有非零特征值）。因此，如果G不是树，其邻接矩阵A至少有一个非零特征值。这与假设矛盾。因此，G必须是树。（另一种证明思路：利用邻接矩阵的秩。树n个顶点n-1条边，邻接矩阵A的秩为n-1。A的特征值中，0的特征重数为1（因为秩为n-1），其余特征值非零。如果A有非零特征值λ，则存在非零向量x使得Ax=λx。两边左乘x^T得x^TAx=λx^Tx。x^TAx=0（因为x^TAx是图的某种能量或迹的体现，对于树这种结构，该值为0），而x^Tx>0。因此λ=0。所以所有非零特征值必为0。这与树有n-1个正特征值矛盾。）2.证明思路：（对称性）A^T表示将邻接矩阵A的行变成列，列变成行得到的矩阵。对于无向图，如果存在边(i,j)，则存在边(j,i)，即a_ij=a_ji。因此，A^T中元素a_ij=a_ji。所以A+A^T中元素(i,j)=a_ij+a_ji=a_ji+a_ij=(i,j)中元素。因此，A+A^T