1. 学习内容

《信息学奥数一本通（初赛篇）》：2.6 图

3. 作业

1、

【CSP 2020 入门组第一轮 q08】有 10 个顶点的无向图至少应该有（ ）条边才能确保是一个连通图。
A. 9   B. 10   C. 11   D. 12  

2、

【NOIP 2018 普及组初赛 q11】由四个没有区别的点构成的简单无向连通图的个数是（ ）。
A. 6   B. 7   C. 8   D. 9  

3、

【NOIP 2017 普及组初赛 q10】设 G 是有 n 个结点、m 条边（n ≤ m）的连通图，必须删去 G 的（ ）条边，才能使得 G 变成一棵树。
A. m – n + 1   B. m - n  
C. m + n + 1   D. n – m + 1  

4、

【NOIP 2017 提高组初赛 q08】由四个不同的点构成的简单无向连通图的个数是（ ）。
A. 32   B. 35   C. 38   D. 41  

5、

【NOIP 2017 提高组初赛 q05】设 G 是有 n 个结点、m 条边（n ≤ m）的连通图，必须删去 G 的（ ）条边， 才能使得 G 变成一棵树。
A. m – n + 1   B. m - n  
C. m + n + 1   D. n – m + 1  

6、

【NOIP 2016 普及组初赛 q18】Lucia 和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他 们之间的关系图，两个人之间有边相连代表这两个人是朋友，没有边相连代 表不是朋友。这个社交网站的规则是：如果某人 A 向他（她）的朋友 B 分 享了某张照片，那么 B 就可以对该照片进行评论；如果 B 评论了该照片，那 么他（她）的所有朋友都可以看见这个评论以及被评论的照片，但是不能对 该照片进行评论（除非 A 也向他（她）分享了该照片）。现在 Lucia 已经上 传了一张照片，但是她不想让 Jacob 看见这张照片，那么她可以向以下朋友 （ ）分享该照片。

A. Dana, Michael, Eve   B. Dana, Eve, Monica  
C. Michael, Eve, Jacob   D. Micheal, Peter, Monica  

7、

【NOIP 2016 提高组初赛 q08】G是一个非连通简单无向图，共有28条边，则该图至少有（ ）个顶点。
A. 10   B. 9   C. 8   D. 7  

8、

【NOIP 2016 普及组初赛 q15】设简单无向图 G 有 16 条边且每个顶点的度数都是 2，则图 G 有()个顶点。
A. 10   B. 12   C. 8   D. 16  

9、

【NOIP 2015 普及组初赛 q12】6 个顶点的连通图的最小生成树，其边数为( )。
A. 6   B. 5   C. 7   D. 4  

10、

【NOIP 2014 普及组初赛 q22】如图所示，图中每条边上的数字表示该边的长度，则从A到E的最短距离是__。

11、

【NOIP 2014 普及组初赛 q17】有向图中每个顶点的度等于该顶点的( )。
A. 入度   B. 出度  
C. 入度和出度之和   D. 入度和出度之差  

12、

【NOIP 2013 普及组初赛 q12】以 A0 作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是（ ）。

A. A0, A1 , A2, A3   B. A0, A1, A3, A2  
C. A0, A2, A1, A3   D. A0, A3, A1, A2  

13、

【NOIP 2013 普及组初赛 q10】在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有4 个顶点、 6 条边的连通图。若要使它不再是连通图，至少要删去其中的（ ）条边。
A. 1   B. 2   C. 3   D. 4