2025年大学《数理基础科学》专业题库- 图论与网络技术的数学分析

2025年大学《数理基础科学》专业题库——图论与网络技术的数学分析考试时间：______分钟总分：______分姓名：______一、1.设图G=(V,E)中有n个顶点，m条边。若G是连通图（无向）或强连通图（有向），证明m≥n-1。2.给定一个有向图G=(V,E)和一个顶点集S⊆V。定义G中从S到S的所有路径的长度（即路径上边的数目）的总和为π(G,S)。证明：对于任何顶点集S，π(G,S)≥|S|*min{d⁺(v)|v∈S}，其中d⁺(v)表示顶点v的出度。二、1.设G是一棵具有n个顶点的无向树。证明G中至少有两个度数为1的顶点。2.考虑Prim算法在求连通加权无向图G=(V,E,W)的最小生成树（MST）时的一个特定执行过程。假设在算法执行到某一时刻，已经选择了一部分边U⊆E，这些边组成的子图T=(V',E')满足V'={v∈V|存在边e∈U且e⊆{v,u}∈E}，并且T是无环的。证明：存在v'∈V\V'和u'∈V'，使得(v',u')∈E且w(v',u')≤w(e)对于所有e∈U都成立。（提示：考虑T∪{(v',u')}形成的图）三、1.在一个容量为C的有向图中，设s和t是源点和汇点。Ford-Fulkerson算法使用增广路径来寻找增广流量。证明：如果在某一步，算法找到的增广路径P的容量（即P上所有边的最小容量）为c_P，那么通过P可以增加的流量Δf最多为c_P。2.考虑二分图B=(X∪Y,E)。定义X中顶点的匹配覆盖是指X中一个子集S_X，使得对于每个y∈Y，存在x∈S_X使得(x,y)∈E。证明：二分图B中存在匹配覆盖S_X的充分必要条件是对于任意S⊆X，|N(S)|≥|S|，其中N(S)是S的邻接集。四、1.给定一个有向无环图（DAG）G=(V,E)和每个顶点v∈V的权重w(v)。拓扑排序是一种将V中的顶点排成线性序列<v₁,v₂,...,v_n>，使得对于所有(u,v)∈E，都有u在v之前（即v₁<v₂<...<v_n）。证明：任何DAG都存在拓扑排序。2.考虑使用Dijkstra算法求解带权无向图G=(V,E,W)中顶点s到所有其他顶点的最短路径。假设算法在执行过程中，顶点集合S包含了顶点s和顶点t（s≠t），且已经确定从s到t的最短路径上的所有顶点都已被包含在S中。证明：此时s到t的最短路径距离就是Dijkstra算法为顶点t计算出的距离d(s,t)。五、1.证明：任何包含n个顶点的简单无向图G中，要么存在一个度数至少为⌊n/2⌋的顶点，要么存在一个大小至少为⌈n/2⌉的独立集。2.设G是一个具有n个顶点（n≥3）的简单无向图。证明：如果G中每个顶点的度数都至少为n/2，那么G是连通的。试卷答案一、1.证明：采用数学归纳法。当n=1时，m=0，显然0≥1-1=0。假设结论对n=k(k≥1)成立，即连通图（无向）或强连通图（有向）满足m≥k-1。考虑n=k+1的情况。对于连通图（无向），添加一个顶点v_(k+1)和至少一条连接v_(k+1)与已有图G'=(V',E')（其中V'=V-{v_(k+1)}）的边e，得到新的连通图G=(V,E)。此时m'=m+1≥k-1+1=k。对于强连通图（有向），添加一个顶点v_(k+1)和至少两条边e1=(v,v_(k+1))∈E'和e2=(v_(k+1),v)∈E'（v∈V'），得到新的强连通图G=(V,E)。此时m'=m+2≥k-1+2=k+1。因此结论对n=k+1成立。由归纳法原理，结论对任意n≥1成立。2.证明：考虑所有从S中顶点出发，经过任意路径，最终到达S中另一个顶点的路径。设P是其中一条这样的路径。P必定包含至少一个离开S的边和一个进入S的边。设P从S中的顶点v_s出发，离开S经过边f进入非S的顶点集合N，再经过一系列边（可能经过S中其他顶点）最终到达S中的顶点v_t。路径P的长度是所有这些边的总数。边f对应的出度d⁺(v_s)被计算了一次。路径P中离开S的边总数量记为k。由于每个离开S的顶点至少被一条从S出发的路径访问（否则G中存在不连通的S子图），且每条访问一个离开S的顶点的路径至少贡献一条离开S的边，所以k≤|S|*min{d⁺(v)|v∈S}。因此，所有这类路径P的长度总和π(G,S)≥1*k≥|S|*min{d⁺(v)|v∈S}。二、1.证明：设T是G的任意生成树，T有n-1条边。设T'是T中度数为1的顶点集合。由于T是树，其任何非叶顶点度数≥2。因此T中所有非叶顶点都连接在T'中顶点（叶节点）和T的其余部分之间。这意味着T'中的顶点数量至少为T的顶点总数减去T的非叶顶点数。即|T'|≥n-(n-|T'|)=2|T'|-n≥n-(n-1)=1。因为T是任意的生成树，所以存在至少一个生成树T_0使得|T_0'|≥1。设v_0∈T_0'为其中任意一个度数为1的顶点。考虑删除v_0及其关联的唯一边e_0，得到子图T_1=(V,E\{e_0})。由于T_0是生成树，T_1包含n-2个顶点，至少存在一条边（否则图不连通），因此T_1必定存在至少一个叶节点v_1。再删除v_1及其关联的唯一边e_1，得到T_2=(V,E\{e_0,e_1})。依此类推，可以构造出一个顶点序列v_0,v_1,...,v_k，其中v_i∈T_i'且v_i是T_i的叶节点。当达到某个k时，T_k变为空图或只剩一个顶点，此时v_k-1即为所求的另一个度数为1的顶点。因此，任何一棵具有n个顶点的无向树至少有两个度数为1的顶点。2.证明：设A=V\V'。我们要证明存在v'∈A和u'∈V'，使得(v',u')∈E且w(v',u')≤w(e)对于所有e∈U。假设结论不成立。即对于任意v'∈A和u'∈V'，存在边(v',u')∈E使得w(v',u')<w(e)对于某个e∈U。考虑构造一个新的边集U'=U∪{(v',u')|v'∈A,u'∈V',(v',u')∈E,w(v',u')<w(e)对所有e∈U成立}。显然U'仍然满足U'中的边组成的子图T'=(V',E')是无环的（因为U⊆E'且E'无环，添加的边(v',u')如果形成环，则v'或u'必须在U诱导的子图中，这与假设矛盾）。但是，根据假设，对于任意v'∈A和u'∈V'，w(v',u')<w(e)对所有e∈U。这意味着存在一条从V'到A的边(u',v')，其权重严格小于U中所有边的权重。这与Prim算法的贪心选择性质（每次选择连接V'和A中顶点权重最小的边）相矛盾，因为如果存在这样的边(u',v')，它应该在算法的某个阶段被选中。因此，假设不成立，必然存在v'∈A和u'∈V'，使得(v',u')∈E且w(v',u')≤w(e)对于所有e∈U成立。三、1.证明：设P是Ford-Fulkerson算法在某一步找到的增广路径。P的容量定义为P上所有边的最小容量，记为c_P。在算法的增广阶段，将从源点s沿着路径P的方向，对P上的每条边(u,v)上的流量f(u,v)增加Δf。对于P上的每条边(u,v)，流量增加Δf后变为f(u,v)+Δf。为了保持容量约束，必须满足f(u,v)+Δf≤c_P。由于初始流量f(u,v)=0，所以必须满足0+Δf≤c_P，即Δf≤c_P。同时，为了保持流量守恒，在路径P的汇点t处，流入t的流量总和必须等于Δf，而在路径P的起点s处，流出s的流量总和也必须等于Δf。由于P的容量c_P限制了Δf的最大可能值，所以算法能够通过路径P增加的最大流量Δf不会超过P的容量c_P。即Δf≤c_P。2.证明：必要性：假设存在匹配覆盖S_X，但存在S⊆X使得|N(S)|<|S|。考虑在二分图B中，将S中的顶点都染成红色，N(S)中的顶点都染成蓝色。根据Hall定理，S中顶点与N(S)中顶点之间存在一个匹配，使得每个红色顶点都匹配到唯一的蓝色顶点。设这个匹配为M。考虑所有与S中顶点匹配的蓝色顶点构成的集合T。由于S⊆X，T⊆Y。根据匹配的定义，T中顶点数等于S中顶点数，即|T|=|S|。但是，由于|N(S)|<|S|，T中顶点数|T|必定小于N(S)中顶点数|N(S)|。这意味着在N(S)中存在一些蓝色顶点不包含在T中。设U=N(S)\T，则|U|=|N(S)|-|T|>0。对于U中的任何一个蓝色顶点u，它不能与S中的任何顶点匹配（否则T中顶点数会增加或不变，但U非空，矛盾），也不能与T中的顶点匹配（因为T中的顶点已经被S中的顶点匹配）。因此，U中的每个顶点都是独立的。但是，S中的每个顶点都与N(S)中的顶点相邻（定义N(S)），因此S中的每个顶点都与U中的顶点相邻。这与U是独立集矛盾。因此，不存在S⊆X使得|N(S)|<|S|。必要性得证。充分性：采用反证法。假设不存在匹配覆盖S_X，即存在S⊆X使得|N(S)|<|S|。我们需要证明此时不存在任何匹配M。假设存在一个匹配M。根据匹配的定义，M中每个X集合中的顶点都恰好匹配到Y集合中的一个顶点。设S是X中未被M匹配的顶点集合（可能为空），T是Y中被M匹配到S中顶点的顶点集合。显然S⊆X，T⊆Y。对于S中的任意顶点s，它不能被M匹配到T中的顶点，因为T中的顶点已经被S中的其他顶点（如果存在）或未被考虑的X中顶点匹配。所以S中顶点不与T中顶点相邻。因此N(S)中的顶点只能与S中顶点相邻（如果S非空）或与X中未被S和T覆盖的顶点相邻。由于T是被S中顶点匹配的顶点集合，所以N(S)中的顶点不能与T中的顶点相邻。这意味着N(S)中的顶点要么在S中（如果S非空），要么在X中S和T之外的部分。因此N(S)中的顶点数量最多等于S中未被匹配的顶点数量加上X中S和T之外的部分的顶点数。如果S非空，则|N(S)|≤|S|。如果S为空（即X中所有顶点都被M匹配），则N(S)应该是空集（因为Y中所有被匹配的顶点都在T中，而T是空的），此时|N(S)|=0。无论哪种情况，如果存在S⊆X使得|N(S)|<|S|，那么S中的顶点无法被完全匹配到Y中足够的顶点，这与假设存在匹配M矛盾。因此，不存在S⊆X使得|N(S)|<|S|。由反证法，如果对于任意S⊆X都有|N(S)|≥|S|，则必然存在匹配覆盖S_X。充分性得证。四、1.证明：采用数学归纳法。当n=1时，DAGG只有一个顶点，不存在有向边，任何顶点序列都是拓扑排序。结论成立。假设结论对n=k(k≥1)成立。考虑n=k+1的情况。设v是G中度出为0的顶点（如果不存在，则G是由环组成的集合，每个集合内部有拓扑顺序，整体可以通过选择一个顺序拼接）。考虑G'=G-{v}（删除顶点v及其所有出边）。G'仍然是一个DAG。根据归纳假设，G'存在拓扑排序<v_1',v_2',...,v_{k'}'>。将顶点v添加到排序的末尾，得到<v_1',v_2',...,v_{k'}',v>。这个序列<v_1',v_2',...,v_{k'}',v>也是G的一个拓扑排序。因为对于G'中的任何边(u',v')∈E'，在G中对应的边(u,v)满足u≠v且v≠v（因为v是出度为0的顶点），所以(u',v')仍然满足u'<v'。对于G中任何以v为尾部的边(u,v)，u必定在G'中，且v'=v不在G'中，所以u<v'。因此，整个序列仍然满足拓扑排序的定义。由归纳法原理，结论对任意n≥1成立。2.证明：设S是Dijkstra算法执行到某一时刻包含的顶点集合，且s∈S,t∈S。根据Dijkstra算法的执行规则，当顶点t被加入集合S时，意味着已经找到了从s到t的最短路径P。此时，顶点t的距离d(s,t)已经被正确计算并确定。即d(s,t)=min{w(s,u)+d(s,u)|u∈V\S}。其中，u是S的补集V\S中的顶点。因为t∈S，所以此处的u≠t。对于任何u∈V\S，d(s,u)是Dijkstra算法在计算到u时得到的最短路径距离。根据算法的性质，这个距离是s到u的真实最短路径距离（因为S中的顶点已经确认为最短路径上的顶点）。因此，d(s,t)的计算只依赖于S中顶点的最短路径距离以及S与V\S之间边的权重。当t被加入S后，这些值不再改变。所以，d(s,t)就是s到t的最短路径距离。五、1.证明：设G中没有度数至少为⌊n/2⌋的顶点。即对于所有v∈V，d(v)<⌊n/2⌋。这意味着每个顶点的度数至多为⌊n/2⌋-1。由于G是简单图，任何两个顶点之间最多有一条边。考虑G中所有顶点组成的集合V。将V分成两个大小尽可能相等的集合A和B，使得A中的顶点之间无边相连（即A是一个独立集），B中的顶点之间无边相连（即B是一个独立集）。由于没有度数至少为⌊n/2⌋的顶点，每个顶点最多与⌊n/2⌋-1个其他顶点相邻。这意味着任何顶点所在的独立集的大小（即集合中顶点数）至少为n-(⌊n/2⌋-1)=n-⌊n/2⌋+1。由于⌊n/2⌋≤n/2<n-⌊n/2⌋+1，所以独立集的大小至少为⌈n/2⌉。因此，如果G中没有度数至少为⌊n/2⌋的顶点，那么G中存在大小至少为⌈n/2⌉的独立集。反之，如果G中存在大小至少为⌈n/2⌉的独立集A，设A的大小为k≥⌈n/2⌉。由于A是独立集，A中任何两个顶点不邻接。这意味着A中的顶点最多与V\A中的⌊(n-k)/2⌋个顶点邻接（每个顶点至多与V\A中的一半顶点邻接）。因此，V\A中每个顶点的度数至多为⌊(n-k)/2⌋。由于k≥⌈n/2⌉，即k≤n-⌊n/2⌋，所以n-k≤⌊n/2⌋。因此，(n-k)/2≤⌊n/2⌋/2≤⌊n/2⌋-1。这意味着V\A中每个顶点的度数至多为⌊n/2⌋-1。即G中没有度数至少为⌊n/2⌋的顶点。由反证法，G中要么存在一个度数至少为⌊n/2⌋的