完全二元树T有n个结点m条边.
(1)设其树叶数为l,证明m=2(l-1).
(2)设其分支结点数(含树根)为树叶数为l,证明l=k+1.
设G是一个有n个顶点的有向图,从顶点i发出的边的最小费用记为min(i).
(1)证明图G的所有前缀为x[1,i]的旅行售货员问路的费用至少为:
式中,a(u,v)是边(u,v)的费用.
(2)利用上述结论设计一个高效的上界函数,重写旅行售货员问题的回溯法,并与主教材中的算法进行比较.
A.N(N>=2)个主用设备共享一个异地冗余设备,同时只允许一个主用设备故障
B.主用网络设备可用时,所有业务都由主用网络设备处理,备用网络设备无负荷;主用网络不可用时,由异地备用网络设备接管业务
C.处于不同地理位置的两个网络设备分别作为预先划分范围内的主用网络设备,正常情况下,两套IMSCore设备分别处理当前接入的各种信令和各项业务,当其中任一地理位置的网络不可用时,所有网络业务都可由另一地理位置的网络设备接管
D.指N(N>=2)个位于不同地理位置,提供相同网络服务的实体构成资源池,当资源池内的任一实体故障或不可达,其网络负荷由资源池内的其他实体共同分担的容灾模式
不相交的子集A和B=V-A,并且这两个子集具有下列性质:
(a)A中任何两个顶点在G中都不是相互邻接的;(b)B中任何两个顶点在G中都不是相互邻接的。例如,图8-34就是二部图。对V(G)的一个划分可能是A=(0,3,4,6)和B=(1,2,5,7).
(1)试编写一个算法,判断图G是否是二部图。如果图G是二部图,则你的算法应当把项点划分成为具有上述性质的两个互不相交的子集A和B。证明:当用邻接表表示图G时,这个算法的复杂度可以做到O(n+e)。其中n是图G的顶点个数,e是边数。
(2)证明:任何-棵树都是二部图
(3)证明:当且仅当图G不包含奇数条边的回路时.它是二部图。
A.处于不同地理位置的两个网络设备分别作为预先划分范围内的主用网络设备,正常情况下,两套IMSCore设备分别处理当前接入的各种信令和各项业务,当其中任一地理位置的网络不可用时,所有网络业务都可由另一地理位置的网络设备接管
B.N(N>=2)个主用设备共享一个异地冗余设备,同时只允许一个主用设备故障
C.指N(N>=2)个位于不同地理位置,提供相同网络服务的实体构成资源池,当资源池内的任一实体故障或不可达,其网络负荷由资源池内的其他实体共同分担的容灾模式
D.主用网络设备可用时,所有业务都由主用网络设备处理,备用网络设备无负荷;主用网络不可用时,由异地备用网络设备接管业务
设某班车起点站上客人数X服从多数为(>0)的泊松分布,每位乘客在中途下车的概率为p(0<p<1),且中途下车与否相互独立,以Y表示在中逸下车的人数,求:(1)在发车时有n个乘客的条件下,中途有m人下车的概率:(2)二维随机变量(X,Y)的概率分布.