2025年大学《数理基础科学》专业题库-大学数理基础科学的拓扑图理论

2025年大学《数理基础科学》专业题库——大学数理基础科学的拓扑图理论考试时间：______分钟总分：______分姓名：______一、填空题（每空3分，共30分）1.连通无向图中，若去掉任意一条边后图不再连通，则该边称为__________。2.一个简单无向图中有n个顶点e条边，若它是欧拉图，则其所有顶点的度数之和为__________。3.设G是n阶无向简单图，其最大度Δ(G)为k，则G中任意两个不相邻的顶点度数之和至少为__________。4.欧拉公式V-E+F=2适用于连通的平面图，其中V、E、F分别表示平面图的__________、__________和__________。5.设T是树，n为顶点数，则T的边数为__________。6.一个图G能够嵌入到一个曲面S上，使得图中的边在S上不相交，则称G是S上的__________。7.若一个图G的同胚像是完全图K₃，则G是__________。8.设G₁和G₂是两个n阶无向简单图，|V(G₁)|=|V(G₂)|=n。若G₁和G₂同构，则它们的边数__________（填相等或不等）。9.对于一个连通图G，其点连通度k(G)是指使G变为不连通所需删除的最少顶点数，k(G)__________（填小于或等于）边连通度λ(G)。10.一个无向图是平面图，当且仅当它不包含__________和__________的子图。二、判断题（每题3分，共30分，请在括号内打√或×）1.在有向图中，如果从顶点u到顶点v存在路径，那么从顶点v到顶点u也一定存在路径。（）2.完全图Kₙ（n≥3）是欧拉图。（）3.任何平面图至少有一个度数为5的顶点。（）4.树是连通的、无环的图。（）5.如果一个图是正则图，那么它是可平面嵌入的。（）6.任何图的基本群都是阿贝尔群。（）7.如果一个图是哈密顿图，那么它也是欧拉图。（）8.任何包含n个顶点的无向图至少有n-1条边。（）9.如果图G₁同构于图G₂，那么它们的邻接矩阵经过行和列的初等交换后是相同的。（）10.欧拉公式V-E+F=2不仅适用于平面图，也适用于所有曲面上的可嵌入图。（）三、计算题（每题10分，共40分）1.给定无向图G的邻接矩阵如下：```A=[[0,1,1,0,0],[1,0,1,1,0],[1,1,0,1,0],[0,1,1,0,1],[0,0,0,1,0]]```（1）求图G中顶点1和顶点4之间的所有简单路径。（2）判断图G是否是哈密顿图，并说明理由。2.求图G（顶点集V={a,b,c,d,e},边集E={ab,ac,bd,be,cd,ce}）的最小生成树，要求列出所有生成树并选择其中一棵按顶点顺序给出边的排列。3.设有n个城市，城市i和城市j之间的直接道路长度为c(i,j)。请用Dijkstra算法求从城市1到其他所有城市的最短路径长度，假设c(i,j)=∞表示城市i和j之间没有直接道路。给出算法执行的关键步骤。4.证明：任何具有奇数个顶点的简单无向图至少有一个顶点的度数为奇数。四、证明题（每题15分，共30分）1.证明：如果一个连通无向图是平面图，那么它的任何顶点的度数都小于或等于6。2.设G是n阶（n≥3）无向简单图。证明：如果G中每个顶点的度数都至少为n/2，那么G是连通的。---试卷答案一、填空题1.极大连通分支2.2e3.k+14.顶点数，边数，面数5.n-16.嵌入7.完全二部图8.相等9.小于或等于10.K₅，K₃,3二、判断题1.×2.×3.×4.√5.×6.×7.×8.√9.√10.×三、计算题1.（1）*路径1-4：1-2-4*路径1-4：1-3-4*路径1-4：1-2-3-4*路径1-4：1-3-2-4*（注：可能存在其他更长的路径，此为所有长度不大于3的路径）（2）*图G是哈密顿图。理由：图G是连通的。删除任意一条边后，图仍然连通（观察邻接矩阵，任何两个顶点之间仍存在路径），因此G是哈密顿图（满足哈密顿定理的必要条件之一）。2.生成树1：{ab,ac,bd,cd}生成树2：{ab,ac,bd,ce}生成树3：{ab,ac,be,cd}生成树4：{ab,ac,be,ce}生成树5：{ab,bd,cd,ce}生成树6：{ac,bd,cd,ce}（选择其中一棵，例如：{ab,ac,bd,cd}）3.Dijkstra算法关键步骤（以从顶点1出发为例）：*初始化：dist[1]=0,dist[i]=∞(i≠1),S={},T=V-{1}。*选取T中dist值最小的顶点u（首次为顶点1）。*更新：对T中每个顶点v，若c(u,v)<∞且dist[u]+c(u,v)<dist[v]，则dist[v]=dist[u]+c(u,v)。*将u加入S，T=T-{u}。*重复步骤2-4，直到T为空集。*输出dist数组，即为从顶点1到其他所有顶点的最短路径长度。4.证明：设G有n个顶点，度数之和为Σd(v)=2e。若所有顶点的度数都是偶数，则Σd(v)是偶数。但根据握手定理，Σd(v)=n*(奇数)。因为n为奇数，所以n*(奇数)为奇数。这与Σd(v)为偶数矛盾。因此，G中至少有一个顶点的度数为奇数。四、证明题1.证明：设G是n阶连通平面图。根据欧拉公式，V-E+F=2。设G有k个面，其中r个面是内部面，(k-r)个面是外部面（无限面）。每个内部面的度数至少为3，每个外部面的度数至少为3。因此，所有面的度数之和Δ≥3r+3(k-r)=3k。根据面度数和公式（所有面的度数和等于2倍边数），3k=2e。所以k=2e/3。代入欧拉公式V-2e/3+k=2，得到V-2e/3+2e/3=2，即V=2。这与n≥3矛盾（因为n=2时，只能是单个顶点或环，度数和为偶数，但n=3时，三角形度数和为6，至少有一个顶点度数≥3）。因此，n≥3的连通平面图中，任何顶点的度数都小于或等于6。2.证明：反证法。假设G不是连通的，则G至少有两个连通分支，不妨设为G₁和G₂。设|G₁|=n₁，|G₂|=n₂，且n₁+n₂=n。因为G₁和G₂是G的连通分支，它们内部是连通的。选择G₁中的一个顶点u，G₂中的一个顶点v。因为G₁和G₂不相连，不存在从u到v的路径。根据假设，每个顶点的度数至少为n/2。对于顶点u，其度数至少为n₁/2。u只能与G₁内部的顶点相邻，因为如果u与G₂中的顶点v相邻，