图
编辑:世明
近3年初赛考察:
题号 | 题型 | 分值 | |
---|---|---|---|
2020 | 第8题 | 单项选择 | 2分 |
2021 | 第6题 | 单项选择 | 2分 |
2022 | 第9题 | 单项选择 | 2分 |
难易度:中等
有关图的定义
图是由若干给定的顶点及连接两顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物,连接两顶点的边则用于表示两个事物间具有这种关系。图论起源于著名的柯尼斯堡七桥问题(下图所示),该问题于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/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%