图

近4年初赛考察：

	题号	题型	分值
2020	第8题	单项选择	2分
2021	第6题
2022	第9题

难易度：中等

有关图的定义

图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。图论起源于著名的​柯尼斯堡七桥问题​(下图所示)，该问题于1736年被欧拉解决，因此普遍认为欧拉是图论的创始人。

边没有方向的图称为无向图。

边有方向，每条边只能从一端到另一端（单向性），的图称为有向图。

连通性

• ​连通​：在一个无向图 G 中，若从顶点i到顶点j有路径相连（当然从j到i也一定有路径），则称i和j是连通的。如果 G 是有向图，那么连接i和j的路径中所有的边都必须同向。
• ​连通图（无向图）​：如果图中​任意两点都是连通的​(可以不是直接连通，间接连通也可以，只要有路径连接就可以)，那么图被称作连通图。
• ​强联通（有向图）​：若一张有向图的节点两两互相可达，则称这张图是 ​强连通的​。
• ​弱连通（有向图）​：若一张有向图的边替换为无向边后可以得到一张连通图，则称原来这张有向图是 ​弱连通的​。

简单图与多重图

• ​自环​：若图中存在从顶点i出发并指向顶点i的边，则该边称作一个自环。
• ​重边​：若图中存在两条完全相同的边，则它们被称作（一组）重边。
• ​简单图​：若一张图中没有自环和重边，它被称为简单图。
• ​多重图​：若一张图中有自环或重边，它被称为多重图。

度

• ​度​：一个顶点在图中的度为与这个顶点相连接的边的数目。对于有向图，顶点的入度是指进入该顶点的边的条数，顶点的出度是指从该顶点出发的边的条数，有向图中顶点的度等于该顶点入度和出度之和。

邻接矩阵

邻接矩阵

​邻接矩阵​：存储图的常用方式之一，邻接矩阵只适用于​没有重边​（或重边可以忽略）的情况。其最显著的优点是可以O(1)查询一条边是否存在。

​实现方法​：使用一个二维数组a来存边，其中a[u][v]为1表示存在u到v的边，为0表示不存在。如果是带边权的图，可以在a[u][v]中存储u到v的边的边权。

历年真题

1、无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图G有7个顶点，则它共有（ ）条边。

A. 7

B. 21

C. 42

D. 49

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

A. a

B. b

C. c

D. d

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

A. 1

B. 2

C. 3

D. 4

4、由四个没有区别的点构成的简单无向连通图的个数是（ ）。

A. 6

B. 7

C. 8

D. 9

5、有 10 个顶点的无向图至少应该有（ ）条边才能确保是一个连通图。

A. 9

B. 10

C. 11

D. 12

6、设简单无向图 G 有 16 条边且每个顶点的度数都是 2，则图 G 有()个顶点。

A. 10

B. 12

C. 8

D. 16

7、设 G 是有 n 个结点、m 条边（n≤m）的连通图，必须删去 G 的（ ）条边，才能使得 G 变成一棵树。

A. m−n+1

B. m−n

C. m+n+1

D. n−m+1

8、对于有n个顶点、m条边的无向联通图（m>n），需要删掉（ ）条边才能使其成为一棵树。

A.n−1

B.m−n

C.m−n−1

D.m−n+1