首页 > 编程学习 > 【数据结构】图 常见题型汇总

【数据结构】图 常见题型汇总

发布时间:2022/11/13 18:57:15

数据结构 图

在这里插入图片描述

定义

无向图的连通分量是指无向图中的极大连通子图。

图的遍历是指从图中顶点出发,每个顶点只能被访问一次,如果图不是连通则从某一顶点出发无法访问到其他全部结点。

无向连通图的所有顶点度之和为偶数

邻接矩阵行对应入度列对应出度顶点的度对应入度+出度

习题

题型1

1.一个有28条边的非连通无向图至少有()个结点

假设一种情况 一个完全图+一个结点 设结点个数为n+1 有 n(n-1)/2=28 求出n为7所以至少有8个结点

2.对于一个有n个节点的图 连通无向图至少有n-1个边(至少构成一棵树) 强连通有向图至少n个边(至少构成一个环)

3.【2010】若无向图G =(V, E)中含7个顶点,则保证图G在任何连边方式下都是连通的,则需要的边数最少是( )

有6个顶点相互连接成环 另外一个顶点连接在其中一个顶点上
完全图边个数为 n(n-1)/2 加上单独的顶点那条边 代入为16条边

(个人理解的方法)

在这里插入图片描述
题型2

1.无向图G有23个边 度为4的顶点有5个 度为3的顶点有4个 其余都是度为2的顶点 则图G有()个顶点

在n个顶点 e条边的无向图中 顶点x对应度数之和为2e 故4*5+3*4+2*x=2*23 x=7 故一共16个顶点

2.【2014】无向图G有16个边,其中度为4的顶点个数为3,度为3的顶点个数为4,其他顶点度均小于3,则G所含顶点个数至少是(18)

在这里插入图片描述
题型3.

1.n个结点的有向图中,每个顶点的度最大为(2n-2)

(n-1)*2 (即入度+出度)

2.n个定点的图是一个环,则有n棵生成树

——————写在后面————————

考研对应的书题还是很不错的,做的头秃,总结出来了一些知识点后就很容易理解了。令人感慨。

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式