设有一个无向图具有8个顶点,其值分别为A,B,C,D,E,F,G,H,其邻接矩阵的存储结构如图8-39所示。基
A、ABCDGIFE
B、ABCDGFHE
C、ABGHFECD
D、ABFHEGDC
E、ABEHFGDC
F、ABEHGFCD
A、ABCDGIFE
B、ABCDGFHE
C、ABGHFECD
D、ABFHEGDC
E、ABEHFGDC
F、ABEHGFCD
第3题
A、n2
B、n(n-l
C、n(n+1)
D、n(n-I)/2
第4题
不相交的子集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不包含奇数条边的回路时.它是二部图。
第5题
A、无向完全图
B、无向连通图
C、无向强连通图
D、无向树图
第6题
点序列和按广度优先搜索遍历得到的顶点序列。
第7题
A.8
B.16
C.24
D.32
第9题
问题描述:给定一个无向图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中.
第11题
一次。
(l)试证明一个有向图存在欧拉回路的充要条件是该图必须是强连通的且每一个顶点有相同的人度与出度;
(2)设图中的顶点数为n,试描述有向图的数据结构并编写一个时间复杂性为O(n)的算法,在有向图中查找一条欧拉回路(如果它存在).