请输入或粘贴题目内容
搜题
拍照、语音搜题，请扫码下载APP
题目内容
（请给出正确答案）
(a)证明有n个顶点的树，其顶点度数之和为2n-2.
(b)设d1,d2,···,dn是n个正整数，n≥2，且
证明存在一棵顶点度数为d1,d2,···,dn的树。
答案
更多“（a)证明有n个顶点的树，其顶点度数之和为2n-2. （b)设d1,d2,···,dn是n个正整数，n≥2”相关的问题
第1题
问题描述:给定一个赋权无向图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在最小权顶点覆盖中.
第2题
算法设计:对于给定的树T,以及障碍物在树T中的分布情况,计算机器人从起点s到终点t的最少移动次数.
数据输入:由文件input.txt提供输入数据.文件的第1行有3个正整数n,s和t,分别表示树T的顶点数,起点s的编号和终点t的编号.
接下来的n行分别对应于树T中编号为0,1,...,n-1的项点.每行的第1个整数h表示顶点的初始状态,当h+1时表示该顶点为空顶点,当h=0时表示该顶点为满顶点,其中已有一个障碍物.第2个数k表示有k个顶点与该项点相连.接下来的k个数是与该顶点相连的顶点编号.
结果输出:将计算出的机器人最少移动次数输出到文件output.txt.如果无法将机器人从起点s移动到终点t,则输出“NoSolution!"
第3题
考查采用DFS算法(教材162页代码6.4)遍历而生成的DFS树，试证明：
a)顶点v是u的祖先，当且仅当
b)v与u无承袭关系，当且仅当
第4题
第5题
问题描述:给定有向图G=(V,E).设P是G的一个简单路(顶点不相交)的集合.如果V中每个顶点恰好在P的条路上,则称P是G的一个路径覆盖.P中路径可以从V的任何一个项点开始,长度也是任意的,特别地,可以为0.G的最小路径覆盖是G的所含路径条数最少的路径覆盖.
设计一个有效算法求一个有向无环图G的最小路径覆盖.
[设V={1,2,...,n},如下构造网络G1=(V1,E1):
每条边的容量均为1.求网络G1的(x0,y0)最大流.]
算法设计:对于给定的有向无环图G,找出G的一个最小路径覆盖.
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和m.n是给定有向无环图G的顶点数,m是G的边数.接下来的m行,每行有2个正整数i和j,表示一条有向边(i,j).
结果输出:将最小路径覆盖输出到文件output.txt.从第1行开始,每行输出一条路径.文件的最后一行是最少路径数.
第7题
重G=1kN的货物挂在支架顶点的球铰D上，支架由杆AD，BD构成，用绳CD维持在题2-11图(a)所示位置平衡。若略去杆重，试求二杆和绳受到的力。
第8题
设二元树t有t片树叶,v1,v2...vt权分别为w1,w2,...wt层深(根到叶的路径长)分为
称
为T的权,权最小的二元树称为最优二元树.求最优二元树的夫曼算法如下:
给定实数w1,w2,...,wt且w1≤w2≤,...,wt.
(1)连接权为w1,w2的两片树叶,得-一个分支点,其权为w1+w2.
(2)在w1+w2,...,w3,...,wt中选出两个最小的权,连接它们对应的结点(不一定是树叶),得新支点及所带的权.
(3)重复(2),直到形成t-1个分支点,t片树叶为止.
使用哈夫曼算法求带权2,2,3,3,5的最优二元树.
第10题
试比较下列二重积分的大小:
(1)
与
其中D由x轴、y轴及直线x+y=1围成:
(2)
与
其中D是以A(1,0)，B(,1), C(2, 0)为顶点的三角形闭区域
第11题
