题目1若无向图G VE中含7个顶点要保证图G在任何情况下都是连通的则需要的边数最少是A.6B.15C.16D.21参考答案C解析无向图的连通图中任意两个顶点间都存在一条路。要保证任意情况都连通告诉点的个数边的个数形状无论怎么样怎么连都要是连通图只要其中6个顶点连成一张完全图任意两个顶点间都有一条边然后第7个点再跟这张完全图有一条边连接即可。有n个顶点的完全图的总边数组合数n个里选2个也就是n(n-1)/2所以有6*6-1/2 116题目2下列有关图的叙述中有几句是对的如果e是有权无向图G唯一的一条最短边那么边e一定会在该图的最小生成树上。如果无向图的宽度优先搜索的结果为1234....且顶点1与顶点4之间存在一条边相连那么顶点1与顶点3之间也一定有边相连。如果从有向图G至少有2个顶点的每一点均能通过深度优先搜索遍历到所有其它顶点那么该图一定不存在拓扑序列。若图采用邻接矩阵表示如果该矩阵不全为0且矩阵主对角线以下全是0那么说明该图一定是有向图。A.1句B.2句C.3句D.4句参考答案D解析第1句正确生成树包含原图所有点边数最少的连通无环子图顶点为n个则边数为n-1。一张图可以有多种生成树。最小生成树一张连通图的所有生成树里边权累加总和最小的那一棵就是最小生成树。最小生成树的形态可能不唯一但是那个最小总权值一定唯一构造最小生成树 的经典方式有一个 Kruskal 克鲁斯卡尔算法 所有边按权值从小到大排序依次选边加入后不形成环就保留凑够 n−1条边停止。由这个算法易知唯一最短边一定会在最小生成树上。第2句正确由宽度优先搜索知1是第1层234是1下面的层级可能是第2层第3层......由于顶点1与顶点4之间存在一条边相连说明4是第2层的那么2,3当然也是第2层的所以顶点1与顶点3之间也一定有边相连。第3句正确从有向图G至少有2个顶点的每一点均能通过深度优先搜索遍历到所有其它顶点可知这个图一定存在环如果没有环那么图中一定有顶点 只有进的 或者 只有出的 箭头那就没办法 去遍历别的顶点 或 被别的顶点遍历到 拓扑序列在一个有向无环图中将所有顶点排成一个线性序列使得对于图中任意一条有向边 (u,v) 顶点u在序列中都排在顶点v的前面由拓扑序列定义易知有环图不存在拓扑序列。第4句正确邻接矩阵存储图的一种方式用二维数组设图有n个顶点就开n*n的方阵行号、列号都对应顶点编号矩阵元素表示两点之间有没有边、边的权值。对于无向图邻接矩阵 一定 是对称的。对于有向图邻接矩阵 不一定 对称。例如一张无权图有节点ABCD那么邻接矩阵a[ ][ ]为如果是无向图那么比如有边A-B则a[A][B]和a[B][A]都标记为11代表有边0代表无边所以最后得到的矩阵一定是对称的。如果是有向图那么比如有边A-B,则a[A][B]标记为1如果再有边B-A才会有a[B][A]也标记为1但是l两个节点间是否有双向的边是不确定的所以不一定是否对称。因此按题目中所述如果图的邻接矩阵不全为0且矩阵主对角线以下全是0那么说明该图不对称所以不可能是无向图一定只能是有向图。综上选择D选项。题目3一个有N个顶点的强连通图至少有多少条边A.N-1B.NC.N1D.N(N-1)参考答案B解析强连通图有向图中任意两点互相可达a可到bb也可到a。【顶点数≥2 的强连通图一定包含环】一个有n个顶点的强连通图 至少 有多少条边整个图所有顶点先连成一条链再把头和尾连起来形成一个大环即可则有n条边。题目4如果G是一个有36条边的非连通无向图那么该图顶点个数最少为多少A.7B.8C.9D.10参考答案D解析要让 非连通 无向图 顶点最少则应该 有1个孤立节点满足非连通然后剩下的节点构成一张完全图同样顶点数目下完全图是边数最多的形式那么边数一定时完全图对应顶点数目最少.n个顶点的完全图边数是 组合数n个中选2个也就是n(n-1)/2 。 则有n(n-1)/2 36得出n(n-1) 72 9*8,则n9。再加上那1个孤立的节点则总的顶点数是10.题目5已知无向图G含有16条边其中度为4的顶点个数为3度为3的顶点个数为4其他顶点的度均小于3。图G所含的顶点个数至少是A.10B.11C.13D.15参考答案B解析无向图中所有顶点的度数之和等于总边数的 2 倍(因为一条边对应两个度)图中有16条边则度数为2*1632。可以设定度为x的节点为nx则 n43 , n34这些节点总共有度数3*44*324还剩32-248个度要想总顶点数最少来凑够剩下的这8个度并且已知其他顶点的度均小于3那么每个顶点的度都取大一点就可以顶点数少一点即取每个顶点的度均为2则有8/24个顶点。那么总共至少有43411个顶点。
