图

编辑：世明

近3年初赛考察：

难易度：中等

有关图的定义

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

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

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

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

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

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

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

1/8单选题（1.5分）全站正确率 74% 无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图G有7个顶点，则它共有（）条边。

A. 7 B. 21 C. 42 D. 49

2/8单选题（1.5分）全站正确率 71% 对一个有向图而言，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。例如，下图就是一个强连通图。事实上，在删掉边（）后，它依然是强连通的。

A. a B. b C. c D. d

3/8单选题（1.5分）全站正确率 76% 在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有4个顶点、6条边的连通图。若要使它不再是连通图，至少要删去其中的（）条边。

A. 1 B. 2 C. 3 D. 4

解题思路：用最少的线条孤立出一个点
让一个点隔绝，每点有三条线，隔绝一点，需三条线，所以选C

4/8单选题（2分）全站正确率 61% 由四个没有区别的点构成的简单无向连通图的个数是（）。

A. 6 B. 7 C. 8 D. 9

每个节点都有三条边经过
4x3 = 12 
无向图 重复计算两次，所以 12 / 2 = 6
答案 A

5/8单选题（2分）全站正确率 74% 有 10 个顶点的无向图至少应该有（）条边才能确保是一个连通图。

A. 9 B. 10 C. 11 D. 12

|E| >= |v| -1
边数 大于等于 顶点数 -1 才能构成连通图
答案：A

6/8单选题（1.5分）全站正确率 62%

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

A. 10
B. 12
C. 8
D. 16

抓住结点度数之和为边数的两倍来解题：
设顶点个数x个：
所以：2*x=16*2
x=16
所以答案选：C

7/8单选题（1.5分）全站正确率 76%

n 个顶点，m 条边的全连通图，至少去掉几条边才能构成一棵树？ A. m-n B. m-n+1 C. m-n-1 D. m-2n

两种方法：
1. 因为是全连通图，其实m=n(n - 1) / 2，举个例子，4个顶点6条边，要得到(n - 1)即3即构成一棵树，代入答案中得B。
2. 要得到(n - 1)才能构成一棵树，m - x = n - 1，解得x = m - n + 1，选B。

8/8单选题（2分）全站正确率 70%