数据结构-图论 经典选择题 解析
题目1：
若无向图G =（V，E）中含7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是：
A.6
B.15
C.16
D.21
参考答案：C
解析：
无向图的连通：图中任意两个顶点间都存在一条路。
要保证任意情况都连通（告诉点的个数，边的个数，形状无论怎么样怎么连都要是连通图），只要其中6个顶点连成一张完全图（任意两个顶点间都有一条边），然后第7个点再跟这张完全图有一条边连接即可。
有n个顶点的完全图的总边数：组合数n个里选2个，也就是n(n-1)/2
所以有6*（6-1）/2 + 1=16
题目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]都标记为1（1代表有边，0代表无边），所以最后得到的矩阵一定是对称的。
如果是有向图，那么比如有边A->B,则a[A][B]标记为1，如果再有边B->A，才会有a[B][A]也标记为1，但是l两个节点间是否有双向的边是不确定的，所以不一定是否对称。
因此按题目中所述，如果图的邻接矩阵不全为0，且矩阵主对角线以下全是0，那么说明该图不对称，所以不可能是无向图，一定只能是有向图。
综上，选择D选项。
题目3：
一个有N个顶点的强连通图至少有多少条边？
A.N-1
B.N
C.N+1
D.N(N-1)
参考答案：B
解析：
强连通图：有向图中任意两点互相可达（a可到b，b也可到a）。【顶点数≥2 的强连通图一定包含环】
一个有n个顶点的强连通图 至少 有多少条边？整个图所有顶点先连成一条链，再把头和尾连起来，形成一个大环即可，则有n条边。
题目4：
如果G是一个有36条边的非连通无向图，那么该图顶点个数最少为多少？
A.7
B.8
C.9
D.10
参考答案：D
解析：
要让 非连通 无向图 顶点最少，则应该 有1个孤立节点（满足非连通），然后剩下的节点构成一张完全图（同样顶点数目下，完全图是边数最多的形式；那么边数一定时，完全图对应顶点数目最少）.
n个顶点的完全图边数是 组合数n个中选2个，也就是n(n-1)/2 。 则有n(n-1)/2 = 36，得出n(n-1) = 72 = 9*8,则n=9。
再加上那1个孤立的节点，则总的顶点数是10.
题目5：
已知无向图G含有16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于3。图G所含的顶点个数至少是：
A.10
B.11
C.13
D.15
参考答案：B
解析：
无向图中，所有顶点的度数之和等于总边数的 2 倍(因为一条边对应两个度)；
图中有16条边，则度数为2*16=32。
可以设定度为x的节点为nx，则 n4=3 , n3=4，这些节点总共有度数：3*4+4*3=24，
还剩32-24=8个度，
要想总顶点数最少，来凑够剩下的这8个度，并且已知其他顶点的度均小于3，那么每个顶点的度都取大一点，就可以顶点数少一点，即取每个顶点的度均为2，则有8/2=4个顶点。
那么总共至少有4+3+4=11个顶点。