计算机#2022考研究生计算机数据结构复习提纲#图G的顶点数n和边数e的关系

类目：三人行考研网>计算机>正文

时间：2020-12-0918:50:54

数据结构也是计算机考研常考的科目，部分院校会考试到这一专业课 ，本文三人行计算机考研小编整理分享“2022考研计算机数据结构复习提纲：图G的顶点数n和边数e的关系 ”相关内容，一起来看看吧 。

图G的顶点数n和边数e的关系

若G是无向图
，则0≤e≤n(n-1)/2

若G是有向图，则0≤e≤n(n-1)

无向图的度：无向图中顶点v的度(Degree)是关联于该顶点的边的数目 ，记为D(v)
，不分出度和入度

有向图的度：入度：以顶点v为终点的边的数目称为v的入度(Indegree)；出度：以顶点v为始点的边的数目

图的边数等于度之和除以2

连通图：若V(G)中任意两个不同的顶点vi和vj都连通

有向边也称为弧(Arc)，边的始点称为弧尾(Tail) ，终点称为弧头(Head)。

强连通图：有向图G中
，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径 ，则称G是强连通图
。

若将图的每条边都赋上一个权
，则称这种带权图为网络