设完全图Kn(n≥ 3)的顶点分别为v1,v2....vn问Kn中有多少条不同的哈密顿回路(这里认为,若在回路C1,C2中,顶点的排列顺序不同,就认为C1与C2是不同的回路)
第1题
问题描述:给定有向图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行开始,每行输出一条路径.文件的最后一行是最少路径数.
第2题
设二元树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的最优二元树.
第5题
Cs很大,对信号可视为短路。场效应管的VTS=0.8V,KN=1mA/V,输出电阻rds=∞。试求电路的小信号电压增益AF。
第6题
A.0 2 4 3 1 5 6
B.0 1 3 6 5 4 2
C.0 1 3 4 2 5 6
D.0 3 6 1 5 4 2
第8题
欧,Rm=1千欧,Rxi=10千欧。场效应管参数为VTS=1.5V,Kn=2mA/V2,λ=0。试求(1)静态工作点Q;(2)电压增益Ap和源电压增益Aex;(3)输入电阻Ri和输出电阻R0。
第9题
(a)证明有n个顶点的树,其顶点度数之和为2n-2.
(b)设d1,d2,···,dn是n个正整数,n≥2,且证明存在一棵顶点度数为d1,d2,···,dn的树。
第11题
设G=(X,Y,Z)=K5,5是一个完全二分图,其中X={x1,x2,...,x5},Y={y1,y2,...,y5}分别表示5个人和5件工作。边xiyj上的权w(xiyj)=wij。如下面的矩阵W所示,wij表示xi做工作yj的效率。求一个效率最高的工作分配方案。