首页 > 考试题库

题目内容（请给出正确答案）

[主观题]

（a)证明有n个顶点的树，其顶点度数之和为2n-2. （b)设d₁,d₂,···,d_n是n个正整数，n≥2

(a)证明有n个顶点的树，其顶点度数之和为2n-2.

(b)设d₁,d₂,···,d_n是n个正整数，n≥2，且（a)证明有n个顶点的树，其顶点度数之和为2n-2. （b)设d1,d2,···,dn是n个正整数，证明存在一棵顶点度数为d₁,d₂,···,d_n的树。

查看答案

如果结果不匹配，请联系老师获取答案

您可能会需要：

重置密码查看订单联系客服

安装优题宝APP，拍照搜题省时又省心！

更多“（a)证明有n个顶点的树，其顶点度数之和为2n-2. （b)…”相关的问题

第1题

设图G是有n个顶点的连通图，试证明所有具有n个顶点和n-1条边的连通图是树图。

点击查看答案

第2题

设无向图G有16条边且每个顶点的度数都是2，则图G有（)个顶点。

A.10

B.4

C.8

D.16

点击查看答案

第3题

在无向图中定义顶点的度为与它相关联的(①)的数目，所有顶点的度数之和等于所有边数的(②)倍。

在无向图中定义顶点的度为与它相关联的（①)的数目，所有顶点的度数之和等于所有边数的（②)倍。

A、3

B、2

C、1

D、1/2

点击查看答案

第4题

设9阶图G中，每个顶点的度数不是5就是6,证明G中至少有5个6度顶点或至少有6个5度顶点

点击查看答案

第5题

设G是平面图有n个顶点m条边f个面，k个连通分支，证明：n- m+f=k+1。

点击查看答案

第6题

问题描述:给定一个赋权无向图G=（V,E),每个顶点都有权值w（v).如果,且对任意（u,V)∈E有u∈U或v∈U,

问题描述:给定一个赋权无向图G=(V,E),每个顶点都有权值w(v).如果,且对任意(u,V)∈E有u∈U或v∈U,就称U为图G的一个顶点覆盖.G的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖.

算法设计:对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最小权顶点覆盖.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,...,n.第2行有n个正整数表示n个顶点的权.接下来的m行中,每行有2个正整数u和v,表示图G的一条边(u,v).

结果输出:将计算的最小权顶点覆盖的顶点权值和以及最优解输出到文件output.txt.文件的第1行是最小权顶点覆盖顶点权之和;第2行是最优解xi(1≤i≤n),xi=0表示顶点i不在最小权顶点覆盖中,xi=1表示顶点i在最小权顶点覆盖中.

点击查看答案

第7题

用邻接矩阵A[n][n]存储有向图，其第i行的所有元素之和等于顶点i的()。

用邻接矩阵A[n][n]存储有向图，其第i行的所有元素之和等于顶点i的（)。

点击查看答案

第8题

若在图G中存在从顶点s通往顶点v的道路，则其中最短道路的长度称作s到v的(最小)距离，记作π(v);不存在道路时，取π(v)=+∞。试证明，在起始于s的广度优先搜索过程中：a)波峰集中的各顶点，始终按其在BFS树中的深度，在辅助队列中单调排列，且彼此相差不超过一;b)所有顶点按其在BFS树中的深度，以非降次序接受访问。c)所有顶点按其到s的距离，以非降次序接受访问。

若在图G中存在从顶点s通往顶点v的道路，则其中最短道路的长度称作s到v的（最小)距离，记作π（v);不存在道路时，取π（v)=+∞。试证明，在起始于s的广度优先搜索过程中：a)波峰集中的各顶点，始终按其在BFS树中的深度，在辅助队列中单调排列，且彼此相差不超过一;b)所有顶点按其在BFS树中的深度，以非降次序接受访问。c)所有顶点按其到s的距离，以非降次序接受访问。

点击查看答案

第9题

设G为9阶无向图，每个顶点度数不是5就是6，则G中至少有（)个5度顶点。

A.2

B.4

C.6

D.8

点击查看答案

第10题

关于解决最小代价生成树问题的Prim算法的下述说法，不正确的是（)。

A.优先队列Q中顶点的键值指这个顶点与A集合中点的最小权边的权重

B.从Q中取出一个顶点的实质是在应用MST性质选择连接A与VA的最小权边