数据结构的一些问题~1、连通图含义?2、n个顶点的无向图、有向图,最少、最多边数?3、n个顶点的非连通图,最多边数?4、
来源:学生作业帮 编辑:大师作文网作业帮 分类:数学作业 时间:2024/09/23 07:20:19
数据结构的一些问题~
1、连通图含义?
2、n个顶点的无向图、有向图,最少、最多边数?
3、n个顶点的非连通图,最多边数?
4、n个顶点有向图,顶点的度最小?最大?
5、有向图顶点入度、出度关系?
6、邻接矩阵、邻接表看边的个数?空间复杂性分别为?
7、与邻接表表示相比,邻接矩阵表示更适合什么图?
1、连通图含义?
2、n个顶点的无向图、有向图,最少、最多边数?
3、n个顶点的非连通图,最多边数?
4、n个顶点有向图,顶点的度最小?最大?
5、有向图顶点入度、出度关系?
6、邻接矩阵、邻接表看边的个数?空间复杂性分别为?
7、与邻接表表示相比,邻接矩阵表示更适合什么图?
1、连通图
图内任意两个顶点均有可达路径,其中有向图的话,所有边都看作无向.满足这一性质的图为连通图
2、由于没说一定连通,所以有向图与无向图最少边数均为0
最多的话,有向图为n*(n-1),无向图为n*(n-1)/2
3、无向图,理论最多边数为(n^2-n)/4,其中点的数目平均分布在两个连通分量
假定一边为x,则边数为x*(x-1)/2,另一边就是(n-x)(n-x-1)/2,两项和取最大值.
4、由于没说一定连通,所以最小度为0
最大度,为n-1入度与n-1出度
5、所有顶点的入度之和等于所有顶点的出度之和
6、假定点数为n,边数为e.
邻接矩阵存储空间为n^2
邻接表存储空间为n+e(有向图),n+e*2(无向图,因为无向图一条边是拆成两条有向边来存)
7、矩阵适合稠密图,即边比较多的图~
图内任意两个顶点均有可达路径,其中有向图的话,所有边都看作无向.满足这一性质的图为连通图
2、由于没说一定连通,所以有向图与无向图最少边数均为0
最多的话,有向图为n*(n-1),无向图为n*(n-1)/2
3、无向图,理论最多边数为(n^2-n)/4,其中点的数目平均分布在两个连通分量
假定一边为x,则边数为x*(x-1)/2,另一边就是(n-x)(n-x-1)/2,两项和取最大值.
4、由于没说一定连通,所以最小度为0
最大度,为n-1入度与n-1出度
5、所有顶点的入度之和等于所有顶点的出度之和
6、假定点数为n,边数为e.
邻接矩阵存储空间为n^2
邻接表存储空间为n+e(有向图),n+e*2(无向图,因为无向图一条边是拆成两条有向边来存)
7、矩阵适合稠密图,即边比较多的图~
(72) n个顶点的强连通图的边数至少有______.(C)
设无向连通图G有n个顶点,证明G至少有(n-1)条边.
无向连通图的连通分量!
若G是一个具有36条边的非连通无向图(没有自回路和多重边),则G至少有____个顶点?
G是一个具有n个结点的无向连通图,证明G至少有n-1条边,并证明具有n-1条边的无向连通图是一棵树
对于一个非连通无向图,共有28条边,则该图至少有多少个顶点?
连通无向图G有k个奇顶点,如果把G变成无奇顶点的图,则在G中至少需要 加___ ___条边
数据结构 :假设图G采用邻接表存储,试设计一个算法,求不带权无向连通图G中距离顶点v的最远的顶点?
运筹学判断题:在所有顶点数相同的连通图中,树的边数最少
设G是n阶m条的无向连通图,证明m>=n-1
无向图G=,且|V|=n,|e|=m,试证明以下两个命题是等价命题:G中每对顶点间具有唯一的通路,G连通且n=m+1
离散数学判断题1.无向图中顶点间的连通关系是一种等价关系.2.“若2+3