试证明:对于一个无向图G=(V,E),若G中各顶点的度均大于或等于2,则G中必有回路。
第1题
问题描述:给定一个无向图G=(V.E),设是G的顶点集.对任意,若u∈U且v∈V-U,就称(u,1)为关于顶点集U的条割边.顶点集U的所有割边构成图G的一个割.G的最大割是指G中所含边数最多的割.
算法设计:对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最大割.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,...,n.接下来的m行中,每行有2个正整数u和y,表示图G的一条边(u,v).
结果输出:将计算的最大割的边数和顶点集U输出到文件output.txt.文件的第1行是最大割的边数;第2行是表示顶点集U的向量x(1≤i≤n),x=0表示顶点i不在项点集U中,x=1表示顶点i在顶点集U中.
第2题
证明定理15.8.
定理15.8:设u,v为n阶无向图简单图G中两个不相邻的顶点,且d(u)+d(v)≥n,则G为哈密顿图GU(u,v)为哈密顿图((u,v)是加的新边.
第7题
设G为n个结点的无向简单图,若x(G)≥k,则称G是k-连通图,k为非负整数.证明以下结论:
(1)当时,正明G连通.
(2)当时,证明G是k-连通图.
第9题
设G是一个有n个顶点的有向图,从顶点i发出的边的最小费用记为min(i).
(1)证明图G的所有前缀为x[1,i]的旅行售货员问路的费用至少为:
式中,a(u,v)是边(u,v)的费用.
(2)利用上述结论设计一个高效的上界函数,重写旅行售货员问题的回溯法,并与主教材中的算法进行比较.
第10题
在图G=(V,E)中,从给定的结点v出发,若中每一结点都是从v可达、而V-S中的每个结点都从v不可达,则称S为v的可达集合,记为d(v)=S。集合称为V’的可达集合,记为d(V')=T,这里.试在图8.13中,求出.
第11题
试证明图5-16所示之系统可以产生单边带信号.图中,信号g(t)之频谱G(w)受限于之间,.设v(t)之频谱为V(w),写出V(w)表示式,并画出图形.