小测验-图

1、有向图中每个顶点的度等于该顶点的( )。  (2014年普及组)

2、有10个顶点的无向图至少应该有（   ）条边才能确保是一个连通图   (2020年真题)

3、已知 $n$ 个顶点的有向图，若该图是强连通的（从所有顶点都存在路径到达其他顶点），则该图中最少有多少条有向边？(2009年真题)

4、若 3 个顶点的无权图 G 的邻接矩阵用数组存储为 {{0,1,1},{1,0,1},{0,1,0}}，假定在具体存储中顶点依次为:  \(v_1​,v_2​,v_3\)​。关于该图，下面的说法哪些是正确的：多选 (2009年真题)

5、无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图 $G$ 有 $7$ 个顶点，则它共有（ ）条边。 (2011年普及组)

6、广度优先搜索时，需要用到的数据结构是（ ）。 (2011年普及组)

7、对一个有向图而言，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。例如，下图就是一个强连通图。事实上，在删掉边（ ）后，它依然是强连通的。 (2011年普及组)

9、平面图可以在画在平面上，且它的边仅在顶点上才能相交的简单无向图。4个顶点的平面图至少有6条边，如下图所示。那么，5个顶点的平面图至少有_____条边。(2011年提高组)

10、在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有 $4$ 个顶点、6 条边的连通图。若要使它不再是连通图，至少要删去其中的（ ）条边。(2013年普及组)

11、以 A0​ 作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是（ ）。 (2013年普及组)

12、在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有 $5$ 个顶点、$8$ 条边的连通图。若要使它不再是连通图，至少要删去其中的（ ）条边。  (2013年提高组)

13、在无向图中，所有顶点的度数之和是边数的(     )倍      (2014年提高组)

14、设G是有6个结点的完全图，要得到一棵生成树，需要从G中删去(    )条边。  (2014年提高组)

15、以下哪些结构可以用来存储图(     )  多选  (2014年提高组)